金山云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);
    }
}