1.一个长为n的正整数数组，里面的每个元素不是0就是5。从数组中选出若干数字组成一个数字，要求能整除90。求满足条件的最大的数字，不存在就输出-1。

1
2
3
4
5
输入：
12
5 5 5 5 5 5 0 0 5 5 5 5
输出：
55555555500

  • 数字能整除90—>能整除10，结果还能整除9

  • 一个数字能整除9—>每位之和能整除90

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public class One {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int fiveNum = 0;
        int zeroNum = 0;
        for(int i = 0; i < n; i++){
            if(scan.nextInt() == 5){
                fiveNum++;
            }
            else{
                zeroNum++;
            }
        }

        // 一个0都不存在时
        if(zeroNum == 0){
            System.out.println(-1);
            return;
        }

        // 5可以最多出现几次
        while(fiveNum > 0){
            if((fiveNum * 5) % 9 == 0){
                break;
            }
            fiveNum--;
        }

        // 5一次都没有
        if(fiveNum == 0){
            System.out.println("0");
            return;
        }

        // 可以有fiveNum个5，zeroNum个0，毫无疑问5在前0在后
        String s = new String("");
        while(fiveNum > 0){
            s += "5";
            fiveNum--;
        }
        while(zeroNum > 0){
            s += "0";
            zeroNum--;
        }

        System.out.println(s);

    }
}

2.有n头奶牛，每头奶牛进行m项测评，所有测评都通过的是优质奶牛。

注意区间的重合问题。但是不知道什么原因一直超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Two {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();

        while(T-- > 0){
            int n = scan.nextInt(), m = scan.nextInt();   // 奶牛数，资质数
            int[] ct = new int[n+1];
            boolean[] visited = new boolean[n+1];
            for(int i = 1; i <= m; i++){   // 每种资质下有k个区间满足
                Arrays.fill(visited, false);
                int k = scan.nextInt();   // 区间数
                while(k-- > 0){
                    int l = scan.nextInt(), r = scan.nextInt();  // 区间开始结束
                    while(l <= r){
                        if(visited[l]){   // 去重
                            continue;
                        }
                        ct[l]++;
                        visited[l] = true;
                        l++;
                    }
                }
            }

            List<String> list = new ArrayList<>();
            for(int i = 1; i <= n; i++){
                if(ct[i] == m){
                    list.add(i+"");
                }
            }

            Collections.sort(list);
            System.out.println(list.size());
            for(String s : list){
                System.out.print(s + " ");
            }

        }

    }
}

3.有n阶台阶，每次可以跨1-m步，要求每次跨的步数与前两次都不同。求登顶的次数

还有一种解法dp[i][j][k]表示到达k前两步分别为j,k的方案数，用动态规划解决。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public class Three {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(), m = scan.nextInt();

        Map<String, Integer> map = new HashMap<>();


        int ct = backtracking(0, -1, -1, n, m, map);

        System.out.println(ct);
    }

    private static int backtracking(int lastLast, int last, int cur, int n, int m, Map<String, Integer> map) {

        if(cur == n){
            return 1;
        }
        if(cur > n){
            return 0;
        }

        String str = lastLast + "-" + last + "_" + cur;
        if(map.containsKey(str)){
            return map.get(str);
        }

        int ct = 0;
        for(int i = 1; i <= m; i++){
            ct += backtracking(last, i, cur+i, n, m, map);
        }

        ct %=1000000007;

        map.put(str, ct);
        return ct;
    }


}