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

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.