本文最后更新于2021年8月3日,已超过 1 个月没更新!

👩‍🏫每日一题·夏季

3732. 矩阵复原

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

public class Main{
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        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[] s = br.readLine().split(" ");
            int n = Integer.parseInt(s[0]), m = Integer.parseInt(s[1]);
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < n; ++ i) {
                s = br.readLine().split(" ");
                for (int j = 0; j < m; ++ j)
                    map.put(Integer.parseInt(s[j]), j); // key为元素的值 value为对应的列
            }
            int[][] ans = new int[n][m];
            int p;
            for (int i = 0; i < m; ++ i) {
                s = br.readLine().split(" ");
                p = map.get(Integer.parseInt(s[0]));
                for (int j = 0; j < n; ++ j)
                    ans[j][p] = Integer.parseInt(s[j]);
            }

            for (int i = 0; i < n; ++ i) {
                for (int j = 0; j < m; ++ j)
                    bw.write(ans[i][j] + " ");
                bw.write("\n");
            }
        }
        br.close();
        bw.close();
    }
}

3731. 序列凑零

🧩 思维题

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
            int[] b = work(a);
            for (int i = 0; i < n; ++ i)
                System.out.print(b[i] + " ");
            System.out.println();
        }
    }

    // 令
    // b[i] = -a[i + 1];
    // b[i + 1] = a[i];
    // 即可
    private static int[] work(int[] a) {
        int n = a.length;
        int[] b = new int[n];
        for (int i = 0; i < n; i += 2) {
            b[i] = -a[i + 1];
            b[i + 1] = a[i];
        }
        return b;
    }
}

3730. 寻找序列

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            int[] b = new int[n];
            int[] c = new int[n];
            for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
            for (int i = 0; i < n; ++ i) b[i] = sc.nextInt();
            for (int i = 0; i < n; ++ i) c[i] = sc.nextInt();
            int[] p = new int[n];
            p[0] = a[0];
            for (int i = 1; i < n - 1; ++ i) {
                if (a[i] != p[i - 1]) p[i] = a[i];
                else if (b[i] != p[i - 1]) p[i] = b[i];
                else p[i] = c[i];
            }

            if (a[n - 1] != p[n - 2] && a[n - 1] != p[0]) p[n - 1] = a[n - 1];
            else if (b[n - 1] != p[n - 2] && b[n - 1] != p[0]) p[n - 1] = b[n - 1];
            else p[n - 1] = c[n - 1];

            for (int i = 0; i < n; ++ i) {
                System.out.print(p[i] + " ");
            }
            System.out.println();
        }
    }
}

3725. 卖罐头

🧩 思维题

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int l = sc.nextInt(), r = sc.nextInt();
            if (r < 2 * l) System.out.println("YES");
            else System.out.println("NO");
        }
    }
}

3729. 改变数组元素

🧩 差分

import java.util.*;

public class Main {
    static int[] p;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            p = new int[n + 2];
            for (int i = 1; i <= n; ++ i) {
                int x = sc.nextInt();
                insert(Math.max(1, i - x + 1), i, 1);
            }
            for (int i = 1; i <= n; ++ i) {
                p[i] += p[i - 1];
                if (p[i] == 0) System.out.print("0 ");
                else System.out.print("1 ");
            }
            System.out.println();
        }
    }

    private static void insert (int l, int r, int x) {
        p[l] += x;
        p[r + 1] -= x;
    }
}

3720. 数组重排

🧩 枚举

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt(), x = sc.nextInt();
            int[] a = new int[n];
            int[] b = new int[n];
            for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
            for (int i = 0; i < n; ++ i) b[i] = sc.nextInt();

            boolean flag = true;
            for (int i = 0; i < n; ++ i) {
                if (a[i] + b[n - 1 - i] > x) {
                    flag = false;
                    break;
                }
            }
            System.out.println(flag ? "Yes" : "No");
        }
    }
}

3711. 方格涂色

🧩 枚举

import java.util.*;

public class Main{
    static int n;
    static int u, r, p, l;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            n = sc.nextInt();
            u = sc.nextInt(); r = sc.nextInt();
            p = sc.nextInt(); l = sc.nextInt();
            boolean flag = false;
            for (int i = 0; i < 1 << 4; ++ i) {
                if (check(i)) {
                    flag = true;
                    break;
                }
            }
            System.out.println(flag ? "YES" : "NO");
        }
    }

    private static boolean check(int state) {
        int a = (state >> 0) & 1, b = (state >> 1) & 1;
        int c = (state >> 2) & 1, d = (state >> 3) & 1;
        if (!(a + b <= u && u <= a + b + n - 2)) return false;
        if (!(b + c <= r && r <= b + c + n - 2)) return false;
        if (!(c + d <= p && p <= c + d + n - 2)) return false;
        if (!(d + a <= l && l <= d + a + n - 2)) return false;
        return true;
    }
}

3705. 子集mex值

import java.util.*;

public class Main{
    public static void main (String[] args) {
        int N = 100;
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            boolean[] a = new boolean[N + 1];
            boolean[] b = new boolean[N + 1];
            for (int i = 0; i < n; ++ i) {
                int num = sc.nextInt();
                if (a[num]) b[num] = true;
                else a[num] = true;
            }
            int x = 0, y = 0;
            for (x = 0; x <= N && a[x]; ++ x);
            for (y = 0; y <= N && b[y]; ++ y);
            System.out.println(x + y);
        }
    }
}

3697. 回文子序列

🧩 注意子串和子序列的区别

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t =  sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
            if (work(a)) System.out.println("YES");
            else System.out.println("NO");
        }
    }

    private static boolean work(int[] a) {
        int n = a.length;
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; ++ i) {
            int idx = map.getOrDefault(a[i], -1);
            if (idx != -1) {
                if (i - idx >= 2) {
                    return true;
                }
            } else map.put(a[i], i);
        }
        return false;
    }
}

3686. 移动序列

import java.util.*;

// 移动的次数就是第一个 1 和最后 1 个 1 中间 0 的个数
public class Main{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            int cnt1 = 0; // 1 的个数
            for (int i = 0; i < n; ++ i) {
                a[i] = sc.nextInt();
                if (a[i] == 1) ++ cnt1;
            }
            int i = 0, j = n - 1;
            while (a[i] == 0) ++ i;
            while (a[j] == 0) -- j;
            System.out.println(j - i + 1 - cnt1);
        }
    }
}

3682. 素数矩阵

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt();
            for (int i = 0; i < n; ++ i) {
                for (int j = 0; j < n; ++ j) {
                    if (i == j || j == (i + 1) % n)
                        System.out.print("1 ");
                    else 
                        System.out.print("0 ");
                }
                System.out.println();
            }
        }
    }
}

3664. 数组补全

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt(), p = sc.nextInt(), x = sc.nextInt(), y = sc.nextInt();
        int sum = 0, lt = 0, ge = 0; // lt为小于中位数y的数, ge为大于等于y的数
        for (int i = 0; i < k; ++ i) {
            int num = sc.nextInt();
            sum += num;
            if (num < y) lt ++;
            else ge ++;
        }

        int r = Math.max(n / 2 + 1, ge), l = n - r;
        if (lt > l)
            System.out.println("-1");
        else {
            sum += (l - lt) * 1 + (r - ge) * y;
            if (sum > x) System.out.println("-1");
            else {
                for (int i = lt; i < l; ++ i)
                    System.out.print("1 ");
                for (int i = ge; i < r; ++ i)
                    System.out.print(y + " ");
            }
        }
    }
}

3663. 打印数字菱形

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        // 根据坐标
        for (int i = 0; i < n * 2 + 1; i ++ ) {
            for (int j = 0; j < n * 2 + 1; j ++ ) {
                int d = Math.abs(i - n) + Math.abs(j - n);
                // 当(i, j) 和 (n, n) 坐标差之和大于 n 即为打印域外,应打空格
                if (d > n) System.out.print("  ");
                else System.out.print(n - d + " ");
            }
            System.out.println();
        }
    }
}

3655. 楼层

🧩 上取整公式

import java.util.*;

// a / b 上取整数 = (a + b - 1) / b 下取整
public class Main{
    public static void main(String[] args) {
        Scanner sc= new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt(), x = sc.nextInt();
            System.out.println(n <= 2 ? 1 : (n - 2 + x - 1) / x + 1);
        }
    }
}

3646. 分水果

🧩 位枚举

import java.util.*;

public class Main {
    static int[][] p = {
        {0, 0, 1},
        {0, 1, 0},
        {1, 0, 0},
        {0, 1, 1},
        {1, 0, 1},
        {1, 1, 0},
        {1, 1, 1}
    };
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int x = sc.nextInt(), y = sc.nextInt(), z = sc.nextInt();
            int ans = 0;
            for (int i = 0; i < 1 << 7; ++ i) {
                int sx = 0, sy = 0, sz = 0;
                int cnt = 0;
                for (int j = 0; j < 7; ++ j) {
                    if (((i >> j) & 1) == 1) {
                        sx += p[j][0];
                        sy += p[j][1];
                        sz += p[j][2];
                        ++ cnt;
                    }
                    if (sx <= x && sy <= y && sz <= z) {
                        ans = Math.max(ans, cnt);
                    }
                }
            }
            System.out.println(ans);
        }
    }
}

3636. 数组延伸

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t -- > 0) {
            int n = sc.nextInt(), x = sc.nextInt();
            long sum = 0, psum = 0, cnt = Long.MAX_VALUE;
            for (int i = 0; i < n; ++ i) {
                int num = sc.nextInt();
                sum += num;

                int c = 1, tmp = num;
                while (tmp % x == 0) {
                    ++ c;
                    tmp /= x;
                }
                if (c < cnt) {
                    cnt = c;
                    psum = sum - num;
                }
            }
            System.out.println((long)(sum * cnt + psum));
        }
    }
}

3624. 三值字符串

🧩 双指针

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 s = br.readLine();
            int[] cur = {-1, -1, -1};
            int ans = Integer.MAX_VALUE;
            for (int i = 0; i < s.length(); ++ i) {
                int num = s.charAt(i) - '0';
                if (num >= 1 && num <= 3) {
                    cur[num - 1] = i;
                }
                if (cur[0] != -1 && cur[1] != -1 && cur[2] != -1) {
                    ans = Math.min(ans, Arrays.stream(cur).max().getAsInt() - Arrays.stream(cur).min().getAsInt() + 1);
                }
            }
            System.out.println(ans == Integer.MAX_VALUE ? 0 : ans);
        }
    }
}

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");
        }
    }
}

3489. 星期几🤓

import java.util.*;

public class Main {
    int[] mouths;
    String[] week_name;
    HashMap<String, Integer> mouth_name;

    public Main () {
        mouths = new int[]{
                0, 31, 28, 31, 30, 31, 30, 31, 31,
                30, 31, 30, 31
        };
        mouth_name = new HashMap<String, Integer>(){{
            put("January", 1);
            put("February", 2);
            put("March", 3);
            put("April", 4);
            put("May", 5);
            put("June", 6);
            put("July", 7);
            put("August", 8);
            put("September", 9);
            put("October", 10);
            put("November", 11);
            put("December", 12);
        }};
        week_name = new String[]{
                "Monday", "Tuesday", "Wednesday",
                "Thursday", "Friday", "Saturday",
                "Sunday"
        };
    }

    boolean is_leap (int year) {
        return year % 4 == 0 && year % 100 != 0 || year % 400 == 0;
    }

    int get_days (int year, int mouth) {
        int days = mouths[mouth];
        if (mouth == 2 && is_leap(year)) ++ days;
        return days;
    }

    public static void main (String[] args) {
        Main sol = new Main();
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String[] strs = sc.nextLine().split(" ");
            int day = Integer.parseInt(strs[0]), mouth = sol.mouth_name.get(strs[1]), year = Integer.parseInt(strs[2]);
            int d = 1, m = 1, y = 1;
            int days = 0;
            while (d < day || m < mouth || y < year) {
                ++ days;
                ++ d;
                if (d > sol.get_days(y , m)) {
                    d = 1;
                    ++ m;
                    if (m > 12) {
                        m = 1;
                        ++ y;
                    }
                }
            }
            System.out.println(sol.week_name[days % 7]);
        }
    }
}

3510. 最长公共子序列😳

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] u = br.readLine().split(" ");
        String[] v = br.readLine().split(" ");
        int[] a = new int[n];
        int[] b = new int[n];
        for(int i = 0; i < n; i++) a[i] = Integer.parseInt(u[i]);
        for(int i = 0; i < n; i++) b[i] = Integer.parseInt(v[i]);

        int[] id = new int[1000010];
        for (int i = 0; i < n; ++ i) id[a[i]] = i;
        int[] q = new int[n + 1];
        int tt = 0;
        q[0] = 0;
        for (int i = 0; i < n; ++ i) {
            int k = id[b[i]];
            if (k == 0) continue;
            int l = 0, r = tt;
            while (l < r) {
                int mid = (l + r + 1) / 2;
                if (q[mid] < k) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            q[r + 1] = k;
            tt = Math.max(tt, r + 1);
        }
        System.out.println(tt);
    }
}

最长递增子序列

3502. 不同路径数🥳

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 k = sc.nextInt();

        int[][] w = new int[n][m];
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++j) {
                w[i][j] = sc.nextInt();
            }
        }

        Set<String> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();

        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                dfs(i, j, k, w, list, set);
            }
        }
        System.out.println(set.size());
    }

    private static void dfs(int x, int y, int k, int[][] w, List<Integer> list, Set<String> set) {
        list.add(w[x][y]);
        if (k <= 0) {
            set.add(list.toString());
            list.remove(list.size() - 1); // 删除添加的元素,关键
            return;
        }
        if (x < w.length - 1) dfs(x + 1, y, k - 1, w, list, set);
        if (y < w[0].length - 1) dfs(x, y + 1, k - 1, w, list, set);
        if (x > 0) dfs(x - 1, y, k - 1, w, list, set);
        if (y > 0) dfs(x, y - 1, k - 1, w, list, set);
        list.remove(list.size() - 1);
    }
}

3499. 序列最大收益🤒

🧩 动态规划

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int m = sc.nextInt();
        int[] a = new int[m + 1];
        for (int i = 1; i <= m; ++i) {
            a[i] = sc.nextInt();
        }
        int[][] w = new int[n + 1][n + 1];
        for (int i = 1; i <= n; ++ i) {
            for (int j = 1; j <= n; ++j) {
                w[i][j] = sc.nextInt();
            }
        }

        // dp[i][j] 表示前i个点删除j个数 保留i的最大收益
        int[][] dp = new int[m + 1][k + 1];
        for (int i = 0; i <= m; ++ i) {
            Arrays.fill(dp[i], -1);
        }
        dp[1][0] = 0;
        for (int i = 2; i <= m; ++ i) {
            for (int j = 0; j <= k; ++ j) {
                for (int u = 1; u < i; ++ u) {
                    int tmp = i - u - 1; //
                    if (j >= tmp)
                        dp[i][j] = Math.max(dp[i][j], dp[u][j - tmp] + w[a[u]][a[i]]);
                }
            }
        }

        int ans = 0;
        for (int num : dp[m]) {
            ans = Math.max(ans, num);
        }

        System.out.println(ans);
    }
}

3493. 最大的和😜

import java.util.*;

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        int[] a = new int[n];
        int[] state = new int[n];
        for (int i = 0; i < n; ++ i) a[i] = sc.nextInt();
        for (int i = 0; i < n; ++ i) state[i] = sc.nextInt();
        // 求出状态为1的和
        long sum = 0;
        for (int i = 0; i < n; ++ i) {
            if (state[i] == 1) sum += a[i];
        }
        // 求连续k个位置状态为0的最大值
        long v = 0, s = 0;
        for (int i = 0; i < n; ++ i) {
            if (state[i] == 0) s += a[i];
            if (i >= k && state[i - k] == 0) s -= a[i - k];
            v = Math.max(v, s);
        }
        // 相加即为答案
        System.out.println(sum + v);
    }
}

3485. 最大异或和🤪

🧩 字典树 & 前缀和

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int M = scanner.nextInt();
        int[] nums = new int[N];
        for (int i = 0; i < N; ++ i) {
            nums[i] = scanner.nextInt();
        }
        System.out.println(maxXORSum(N, M, nums));
        scanner.close();
    }

    /**
     * Description: 字典树 + 贪心
     */
    private static int maxXORSum (int n, int m, int[] nums) {
        // 求前缀异或和
        int[] sum = new int[n + 1];
        for (int i = 1; i <= n; ++ i) {
            sum[i] = sum[i - 1] ^ nums[i - 1];
        }

        Trie trie = new Trie();
        trie.insert(sum[0], 1);
        int ans = 0;
        for (int i = 1; i <= n; ++ i) {
            if (i > m) trie.insert(sum[i - m - 1], -1);
            trie.insert(sum[i], 1);
            ans = Math.max(ans, trie.get(sum[i]));
        }
        return ans;
    }
}

/**
 * Description: Tire树结点定义
 */
class TrieNode {
    TrieNode[] sub = new TrieNode[2];
    int count = 0;
}

/**
 * Description: 字典树
 */
class Trie{
    TrieNode root;
    public Trie(){
        root = new TrieNode();
    }

    // 插入
    public void insert(int x, int v){
        TrieNode cur = root;
        for(int i = 30; i >= 0; i--){
            int d = (x >> i) & 1;
            if(cur.sub[d] == null){
                cur.sub[d] = new TrieNode();
            }
            cur = cur.sub[d];
            cur.count += v;
        }
    }

    //获得 x 的最大异或值
    public int get(int x){
        int sum = 0;
        TrieNode cur = root;
        for(int i = 30; i >= 0; i--){
            int d = (x >> i) & 1;
            if(cur.sub[d ^ 1] != null && cur.sub[d ^ 1].count > 0){
                sum = sum * 2 + 1;
                cur = cur.sub[d ^ 1];
            }else if(cur.sub[d] != null && cur.sub[d].count > 0){
                sum = sum * 2;
                cur = cur.sub[d];
            }
        }
        return sum;
    }
}

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