8.19 美团 a4题

1.简单取余

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int q = in.nextInt();
        for(int i=0;i<q;++i){
            int m = in.nextInt();
            int x = in.nextInt();
            System.out.println((x-1)%m+1);
        }
    }

2.遍历即可

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        long sum = 0;
        for(int i=0;i<n;++i){
            arr[i] = in.nextInt();
            sum+=arr[i];
        }
        long maxm = sum;
        for(int i=1;i<n;++i){
            //不强转long 只能过50%
            maxm = Math.max(maxm,sum-arr[i]-arr[i-1]+(long)arr[i]*arr[i-1]);
        }
        System.out.println(maxm);
    }

3.无脑动规了，还有很多优化空间，但是懒得想了。

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int n = s.length();
        long sum = 0;
        for (int i = 0; i < n; ++i) {
            int[][] dp = new int[n][2];
            if (s.charAt(i) == '0') {
                dp[i][0] = 0;
                dp[i][1] = 1;
            } else {
                dp[i][0] = 1;
                dp[i][1] = 0;
            }
            for (int j = i + 1; j < n; ++j) {
                if (s.charAt(j) == '0') {
                    dp[j][0] = dp[j - 1][1];
                    dp[j][1] = dp[j - 1][0] + 1;
                } else {
                    dp[j][0] = dp[j - 1][1] + 1;
                    dp[j][1] = dp[j - 1][0];
                }
                sum += Math.min(dp[j][0], dp[j][1]);
            }
        }
        System.out.println(sum);
    }

4.背包问题

public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            a[i] = in.nextInt();
            sum += a[i];
        }
        if (n == 1 || sum == n) {
            System.out.println(0);
            return;
        }
        long[][] dp = new long[n][sum + 1];
        for (int i = 1; i <= sum; ++i) {
            dp[0][i] = 1;
        }
        dp[0][a[0]] = 0;
        int mod = 1000000007;
        for (int i = 1; i < n; ++i) {
            for (int j = 1; j < sum; ++j) {
			  //不得与原位置的数相同
                if (j == a[i]) continue;
                for (int k = i; k < sum && j + k <= sum; ++k) {
                    dp[i][j + k] = (dp[i][j + k] + dp[i - 1][k]) % mod;
                }
            }
        }
        System.out.println(dp[n - 1][sum]);
    }

5.第五题看题目意思是存在多个众数，实在不会做，就按照只有一个众数骗分也是0