本文最后更新于2021年10月4日,已超过 2 个月没更新!

3617. 子矩形计数

🧩 差分

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[m];
        int[] s1 = new int[n + 2];
        int[] s2 = new int[m + 2];
        for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
        for (int i = 0; i < m; ++ i) b[i] = sc.nextInt();
        work(a, s1);
        work(b, s2);

        long ans = 0;
        for (int i = 1; i <= n; ++ i) {
            if (k % i == 0) {
                int j = k / i;
                if (j <= m) ans += s1[i] * s2[j];
            }
        }
        System.out.println(ans);
    }

    public static void work (int[] nums, int[] s) {
        int n = nums.length;
        for (int i = 0, j = 0; i < n; ++ i) {
            if (nums[i] != 0) {
                ++ j;
                s[1] ++;
                s[j + 1] --;
            } else j = 0;
        }

        for (int i = 1; i <= n; ++ i)
            s[i] += s[i - 1];
    }
}

3583. 整数分组

🧩 动态规划

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; ++ i) a[i] = sc.nextInt();
        Arrays.sort(a);
        // f[i][j] 表示在前[1, i]中选 j 组的最大选择数
        int[][] f = new int[n + 1][m + 1];

        for (int i = 1, k = 1; i <= n; ++ i) {
            while (a[i] - a[k] > 5) ++ k;
            for (int j = 1; j <= m; ++ j) {
                f[i][j] = Math.max(f[i - 1][j], f[k - 1][j - 1] + i - k + 1);
            }
        }
        System.out.println(f[n][m]);
    }
}

🍹y总笔记🍹

3580. 整数配对🥰

🧩 贪心 证明是重点

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for (int i = 0;i < n; ++ i) nums[i] = sc.nextInt();
        Arrays.sort(nums);
        int ans = 0;
        for (int i = 1; i < n; i += 2) {
            ans += nums[i] - nums[i - 1];
        }
        System.out.println(ans);
    }
}

3574. 乘积数量

🧩 前缀和

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // Positive and Negative
        long rp = 0, rn = 0;
        int sp = 1, sn = 0, s = 1;
        for (int i = 1; i <= n; ++ i) {
            int a = sc.nextInt();
            if (a < 0) s *= -1;
            if (s > 0) {
                rp += sp;
                rn += sn;
                ++ sp;
            }
            else {
                rp += sn;
                rn += sp;
                ++ sn;
            }
        }
        System.out.println(rn + " " + rp);
    }
}

3565. 完美矩阵🧐

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        while (t -- > 0) {
            String[] s1 = br.readLine().split(" ");
            int n = Integer.parseInt(s1[0]);
            int m = Integer.parseInt(s1[1]);
            int[][] arr = new int[n][m];
            for (int j = 0; j < n; ++ j) {
                String[] s2 = br.readLine().split(" ");
                for (int k = 0; k < m; ++ k) {
                    arr[j][k] = Integer.parseInt(s2[k]);
                }
            }

            long ans = 0;
            for (int i = 0; i < n; ++ i) {
                for (int j = 0; j < m; ++ j) {
                    int a = arr[i][j];
                    int b = arr[n - i - 1][j];
                    int c = arr[i][m - j - 1];
                    int d = arr[n - i - 1][m - j - 1];
                    int mid = Math.min(Math.max(a, b), Math.max(c, d));
                    ans += Math.abs(a - mid) + Math.abs(b - mid) + Math.abs(c - mid) + Math.abs(d - mid);
                }
            }
            bw.write(ans / 4 + "\n");
        }
        bw.close();
        br.close();
    }
}

类似题型: 货仓选址

3554. 二进制🥰

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());
        for (int j = 0; j < t; ++ j) {
            String s = br.readLine();
            StringBuilder str1 = new StringBuilder(s);
            boolean flag = true;
            for (int i = 31; i >= 0 && flag; -- i) {
                if (str1.charAt(i) == '1') str1.setCharAt(i, '0');
                else {
                    str1.setCharAt(i, '1');
                    flag = false;
                }
            }
            if (flag) str1.insert(0, '1');
            StringBuilder str2 = new StringBuilder(str1);

            bw.write(str1.toString() + "\n");
            flag = true;
            for (int i = str2.length() - 2; i >= 0 && flag; -- i) {
                if (str2.charAt(i) == '1') str2.setCharAt(i, '0');
                else {
                    str2.setCharAt(i, '1');
                    flag = false;
                }
            }
            if (flag) str2.insert(0, '1');
            bw.write(str2.toString() + "\n");
        }
        bw.close();
        br.close();
    }
}

3333. K-优字符串🥰

import java.util.*;
import java.io.*;

public class Main{
    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int t = Integer.parseInt(br.readLine());

        for (int i = 1; i <= t; ++ i) {
            String[] strs = br.readLine().split(" ");
            int n = Integer.parseInt(strs[0]);
            int k = Integer.parseInt(strs[1]);
            String s = br.readLine();
            int len = s.length();
            int count = 0, ans = 0;
            for (int j = 0; j < len / 2; ++ j) {
                if (s.charAt(j) != s.charAt(len - 1 - j)) {
                    count ++;
                }
            }
            ans = Math.abs(count - k);
            bw.write("Case #" + i + ": " + ans + "\n");
        }
        bw.close();
        br.close();
    }
}

3483. 2的幂次方🤠

🧩 递归

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String s;
        while ((s = br.readLine()) != null) {
            int n = Integer.parseInt(s);
            bw.write(dfs(n) + "\n");
        }
        bw.close();
        br.close();
    }

    private static String dfs (int num) {
        StringBuilder str = new StringBuilder();
        for (int i = 14; i >= 0; -- i) {
            if (((num >> i) & 1) == 1) {
                if (str.length() != 0) str.append("+");
                if (i == 0) str.append("2(0)");
                else if (i == 1) str.append("2");
                else str.append("2(").append(dfs(i)).append(")");
            }
        }
        return str.toString();
    }
}

3404. 谁是你的潜在朋友

import java.util.*;
import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int m = Integer.parseInt(s[1]);

        int[] readers = new int[n];
        HashMap<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < n; ++ i) {
            readers[i] = Integer.parseInt(br.readLine());
            map.put(readers[i], map.getOrDefault(readers[i], 0) + 1);
        }

        for (int i = 0; i < n; ++ i) {
            int num = map.getOrDefault(readers[i], 0);
            if (num == 1) {
                bw.write("BeiJu\n");
            } else {
                bw.write(num - 1 + "\n");
            }
        }
        bw.close();
        br.close();
    }
}

3516. 最大面积🤯

import java.util.*;
import java.io.*;

public class Main {
    static int N = 2010;
    static int[][] matrix = new int[N][N];
    static int[][] sum = new int[N][N];
    static int[] u = new int[N];
    static int[] d = new int[N];
    static int[] l = new int[N];
    static int[] r = new int[N];

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        String[] strs = br.readLine().split(" ");
        int n = Integer.parseInt(strs[0]);
        int m = Integer.parseInt(strs[1]);

        for (int i = 1; i <= n; ++ i) {
            String s = br.readLine();
            for (int j = 1; j <= m; ++ j) {
                matrix[i][j] = s.charAt(j - 1) - '0';
            }
        }

        // 自顶向下
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= m; ++ j) {
                if (matrix[i][j] == 1) sum[i][j] = sum[i - 1][j] + 1;
                else sum[i][j] = 0;
            }
            u[i] = Math.max(u[i - 1], calc(sum[i], m));
        }

        // 清空
        for (int i = 0; i < N; ++ i) Arrays.fill(sum[i], 0);

        // 自底向上
        for (int i = n; i >= 1; -- i) {
            for (int j = 1; j <= m; ++ j) {
                if (matrix[i][j] == 1) sum[i][j] = sum[i + 1][j] + 1;
                else sum[i][j] = 0;
            }
            d[i] = Math.max(d[i + 1], calc(sum[i], m));
        }

        // 清空
        for (int i = 0; i < N; ++ i) Arrays.fill(sum[i], 0);

        // 自左向右
        for (int i = 1; i <= m; ++ i) {
            for (int j = 1; j <= n; ++ j) {
                if (matrix[j][i] == 1) sum[i][j] = sum[i - 1][j] + 1;
                else sum[i][j] = 0;
            }
            l[i] = Math.max(l[i - 1], calc(sum[i], n));
        }

        // 清空
        for (int i = 0; i < N; ++ i) Arrays.fill(sum[i], 0);

        // 自右向左
        for (int i = m; i >= 1; -- i) {
            for (int j = 1; j <= n; ++ j) {
                if (matrix[j][i] == 1) sum[i][j] = sum[i + 1][j] + 1;
                else sum[i][j] = 0;
            }
            r[i] = Math.max(r[i + 1], calc(sum[i], n));
        }

        int q = Integer.parseInt(br.readLine());

        for (int i = 0; i < q; ++ i) {
            String[] s = br.readLine().split(" ");
            int x = Integer.parseInt(s[0]) + 1;
            int y = Integer.parseInt(s[1]) + 1;
            int ans = Math.max(Math.max(u[x - 1], d[x + 1]), Math.max(l[y - 1], r[y + 1]));
            bw.write(ans + "\n");
        }

        bw.close();
        br.close();
    }

    // 单调栈求最大面积
    public static int calc (int[] nums, int n) {

        Deque<Integer> stack = new LinkedList<>();
        int[] left = new int[n + 1];
        int[] right = new int[n + 1];
        Arrays.fill(left, 0);
        Arrays.fill(right, n + 1);
        for (int i = 1; i <= n; ++ i) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                right[stack.pop()] = i;
            }
            stack.push(i);
        }

        stack.clear();
        for (int i = n; i >= 1; -- i) {
            while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
                left[stack.pop()] = i;
            }
            stack.push(i);
        }

        int ans = 0;
        for (int i = 1; i <= n; ++ i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * nums[i]);
        }
        return ans;
    }
}

830.单调栈 -> 131.直方图中最大的矩形 -> 152.城市游戏 -> 3516.最大面积

🧩 calc另一写法

public static int calc(int[] nums, int n){
    nums[0] = -1;
    nums[n + 1] = -1;
    int ans = 0;
    int[] left = new int[n + 1];
    int[] right = new int[n + 1];
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(0);
    for(int i = 1; i <= n; i ++){
        while(nums[i] <= nums[stack.peek()]){
            stack.pop();
        }
        left[i] = stack.peek();
        stack.push(i);
    }
    stack.clear();
    stack.push(n + 1);
    for(int i = n; i >= 1; i --){
        while(nums[i] <= nums[stack.peek()]){
            stack.pop();
        }
        right[i] = stack.peek();
        stack.push(i);
    }
    for(int i = 1; i <= n; i ++){
        ans = Math.max(ans, (right[i] - left[i] - 1) * nums[i]);
    }
    return ans;
}

3481. 阶乘的和🧐

🧩 爆搜

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] res = new int[10];
        res[0] = 1;
        for (int i = 1; i < 10; ++ i) {
            res[i] = res[i - 1] * i;
        }
        while (sc.hasNext()) {
            long n = sc.nextLong();
            if (n < 0) break;
            if (dfs(res, n, 0)) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    private static boolean dfs (int[] res, long n, int idx) {
        if (idx > 9) return false;
        long tmp = n - res[idx];
        if (tmp > 0) {
            return dfs(res, tmp, idx + 1) || dfs(res, n, idx + 1);
        }
        if (tmp == 0) return true;
        return false;
    }
}

🧩 位枚举📘

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        Set<Integer> set = new HashSet<>();

        int[] res = new int[10];
        res[0] = 1;
        for (int i = 1; i < 10; ++ i) {
            res[i] = res[i - 1] * i;
        }

        for (int i = 1; i < 1 << 10; ++ i) {
            int s = 0;
            for (int j = 0; j < 10; ++ j) {
                if ((i >> j & 1) == 1) {
                    s += res[j];
                }
            }
            set.add(s);
        }

        while (sc.hasNext()) {
            int num = sc.nextInt();
            if (num < 0) break;
            if (set.contains(num)) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

Try and fail, but don't fail to try.