金山云10.19笔试
题目1，dfs，AC100%
public class Main {
/*
@金山云1
时间限制： 3000MS
内存限制： 589824KB
题目描述：
现在给你N个正整数，从中选取3个数字的和，刚好能够组成M的倍数。请问存在多少种不同的选取方案？
相同的一组数如果次序不同只能算做一种方案，不同位置的相同数字需当做同一个数字看待。
例如一组数字[2,3,3,4]，从中选取3个数字的和来组成3的倍数，只存在一种方案(2,3,4)。
输入描述
单组数据。 第1行输入两个正整数N和M，N<=20。 第2行输入N个正整数，两两之间用空格隔开。
输出描述
输出不同的选取方案的数量。
样例输入
4 3
2 3 3 4
样例输出
1
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
int[] arr = new int[N];
// 读取N个数据...
for (int i = 0; i < N; i++) {
arr[i] = scanner.nextInt();
}
long[] result = new long[1];
Set<String> set = new HashSet<>();
// dfs2(arr, set, new ArrayList<>(), 0);
dfs(arr, set, new ArrayList<>(), new boolean[arr.length]);
set.forEach(e -> {
int sum = Arrays.stream(e.split("_")).mapToInt(Integer::parseInt).sum();
if ((sum) % M == 0) {
result[0]++;
}
});
System.out.println(result[0]);
}
/**
* AC 100% 全排列---
*/
public static void dfs(int[] arr, Set<String> set, List<Integer> list, boolean[] visited) {
if (list.size() == 3) {
if (isValid(set, list)) {
set.add(getString(list, 0, 1, 2));
}
return;
}
for (int i = 0; i < arr.length; i++) {
if (visited[i]) {
continue;
}
visited[i] = true;
list.add(arr[i]);
dfs(arr, set, list, visited);
list.remove(list.size() - 1);
visited[i] = false;
}
}
/**
* 会TLE，AC82%，时间复杂度很高---遍历所有元素，可以选择可以不选择...
*/
public static void dfs2(int[] arr, Set<String> set, List<Integer> list, int index) {
if (list.size() == 3) {
if (isValid(set, list)) {
set.add(getString(list, 0, 1, 2));
}
return;
}
// 判断第i个元素要与不要...
for (int i = index; i < arr.length; i++) {
// 第一种选择是当前元素不要...
dfs2(arr, set, list, i + 1);
// 第二种选择是当前元素要...
list.add(arr[i]);
dfs2(arr, set, list, i + 1);
list.remove(list.size() - 1);
}
}
public static boolean isValid(Set<String> set, List<Integer> list) {
return !set.contains(getString(list, 0, 1, 2)) &&
!set.contains(getString(list, 0, 2, 1)) &&
!set.contains(getString(list, 1, 0, 2)) &&
!set.contains(getString(list, 1, 2, 0)) &&
!set.contains(getString(list, 2, 0, 1)) &&
!set.contains(getString(list, 2, 1, 0));
}
public static String getString(List<Integer> list, int... index) {
return list.get(index[0]) + "_" + list.get(index[1]) + "_" + list.get(index[2]);
}
} 题目2.也不太会做，简单dfs搜索去做的，能AC45%，然后TLE了。
public class Main {
/*
@金山云2
时间限制： 3000MS
内存限制： 589824KB
题目描述：
给出n个正整数，这n个正整数中可能存在一些相同的数。现在从这n个数中选取m个正整数，分别记为X1、X2、......、Xm，
使得这m个数满足如下公式： 1/X1 + 1/X2 + ...... + 1/Xm = 1 请问存在多少种不同的数字组合可以使得上述公式得以成立？
输入描述
单组输入。 第1行输入一个正整数n，表示输入的正整数个数。(n<=100) 第2行输入n个正整数，两两之间用空格隔开。
输出描述
输出满足要求的组合个数。如果一个组合都不存在，则输出“No solution!”。
样例输入
6
1 2 2 3 4 4
样例输出
3
提示
对于输入样例中的6个正整数，存在3种和为1的组合，分别是：1=1/1，1=1/2+1/2，1=1/2+1/4+1/4。
*/
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int[] arr = new int[N];
// 扫描N个数据...
for (int i = 0; i < arr.length; i++) {
arr[i] = scanner.nextInt();
}
long[] result = new long[1];
dfs(arr, new ArrayList<>(), 0, result, new HashSet<>());
System.out.println(result[0] == 0 ? "No solution!" : result[0]);
}
/**
* AC 45%测试用例，然后TLE了
*/
public static void dfs(int[] arr, List<Integer> list, int index, long[] result, Set<List<Integer>> set) {
int check = check(list);
if (check == 0) { // 如果符合，那么需要统计
if (!set.contains(list)) {
result[0]++;
set.add(list);
}
return;
}
if (check > 0) {
return;
}
for (int i = index; i < arr.length; i++) {
dfs(arr, list, i + 1, result, set);
list.add(arr[i]);
dfs(arr, list, i + 1, result, set);
list.remove(list.size() - 1);
}
}
public static int check(List<Integer> list) {
long multi = 1;
// 计算累乘和
for (int i = 0; i < list.size(); i++) {
multi *= list.get(i);
}
// 计算除去当前元素的所有元素的乘积之和...
long sum = 0;
for (int i = 0; i < list.size(); i++) {
sum += multi / list.get(i);
}
return Long.compare(sum, multi);
}
}
#金山云##笔经#
