题目

小蓝吃苹果

题目链接

解题思路（最少回文划分，区间dp）

小蓝面前有一排苹果，每个苹果上写了一个数字。他每次可以吃掉一段连续的苹果，但这段苹果上的数字必须构成一个回文序列（正着读和反着读一样）。吃完后，剩下的苹果会自动拼接成一整段，继续操作。问：最少吃几次能把所有苹果吃完？

这个问题等价于：把原数组划分成最少数量的连续子段，使得每一段都是回文。

我们用 区间动态规划（Interval DP） 来解决。

状态定义

设 dp[i][j] 表示将区间 [i, j]（闭区间，1-indexed）内的苹果全部吃完所需的最少次数。

• 最终答案就是 dp[1][n]。
• 初始时，单个苹果肯定是回文，所以 dp[i][i] = 1。

状态转移

考虑区间 [i, j]：

1. 如果 a[i] == a[j]：

   • 两端数字相等，说明有可能把整个区间“包”起来吃。
   • 特别地：
     • 如果 j == i + 1（只有两个相等的数），那么一次就能吃完 → dp[i][j] = 1。
     • 否则，dp[i][j] = dp[i+1][j-1]。

       为什么？因为中间部分 [i+1, j-1] 的最优解已经算好了，而加上两个相同的端点后，仍然可以用同样次数吃完（例如 [1,2,1] 和 [2] 都只需 1 次）。

2. 如果 a[i] != a[j]：

   • 整个区间不能作为一整段吃掉；
   • 必须在某个位置 k（i ≤ k < j）切开，分成 [i, k] 和 [k+1, j] 两部分；
   • 枚举所有可能的 k，取最小值：
     dp[i][j] = \min_{k=i}^{j-1} \left( dp[i][k] + dp[k+1][j] \right)

💡 为什么只切一刀就够了？
因为任何多段划分（比如三段、四段）都必然存在“第一刀”。而子区间的最优解已经在之前的 DP 中计算过了，所以我们只需枚举第一刀的位置即可覆盖所有情况。

为什么不是先吃中间某一段后，再吃两边？
因为 a[i] != a[j]，不能吃两边！

计算顺序

按区间长度从小到大枚举：

• 先算长度为 1 的区间；
• 再算长度为 2、3……直到 n；
• 这样能保证计算 dp[i][j] 时，所有更小区间的结果都已知。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 使用 1-indexed 数组，方便处理区间 [1, n]
        int[] a = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            a[i] = sc.nextInt();
        }

        // dp[i][j] 表示吃完区间 [i, j] 所需的最少次数
        int[][] dp = new int[n + 1][n + 1];

        // 初始化：每个单独的苹果都需要吃 1 次
        for (int i = 1; i <= n; i++) {
            dp[i][i] = 1;
        }

        // 枚举区间长度 len，从 2 到 n
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1; // 当前区间的右端点

                if (a[i] == a[j]) {
                    // 两端相等：可以利用对称性
                    if (len == 2) {
                        // 两个相邻且相等的数，如 [4,4]，一次吃完
                        dp[i][j] = 1;
                    } else {
                        // 如 [1, ..., 1]，最优次数等于中间部分的次数
                        // 例如 [1,2,1] -> 中间 [2] 需 1 次，整体也可 1 次
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                } else {
                    // 两端不等：必须分割成两部分
                    dp[i][j] = Integer.MAX_VALUE;
                    // 枚举分割点 k，将 [i, j] 分成 [i, k] 和 [k+1, j]
                    for (int k = i; k < j; k++) {
                        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j]);
                    }
                }
            }
        }

        // 输出整个序列的最少吃苹果次数
        System.out.println(dp[1][n]);
    }
}

复杂度分析

• 时间复杂度：​ O(n^3) ，三层循环（区间长度、起点、分割点）；
• 空间复杂度：​ O(n^2) ，用于存储 dp 表。

对于 ​ n \leq 500 的典型数据范围，完全可以通过。

总结

• 本题本质是最少回文划分数问题；
• 使用区间 DP，状态定义直观，转移逻辑严谨；
• 关键在于理解：当两端相等时可直接继承中间结果，不等时枚举分割点即可覆盖所有划分方式；

---

区间最大子序列和

题目链接

题目意思

给你一个数组，比如：
a = [1, -3, 8, -9, 2, -2, 1]

然后有若干次询问，每次问你：在区间 [l, r] 中，连续一段数的最大和是多少？

例如：

• 问 [1,5] → 子数组是 [1, -3, 8, -9, 2]，最大连续和是 8（只取第3个数）。
• 问 [5,7] → [2, -2, 1]，最大和是 2。

如果每次查询都暴力算，会超时。所以我们提前把所有区间的答案算好，查询时直接输出。

---

解题思路

对于任意一个区间 [l, r]，它的最大连续子段和只有三种可能：

1. 完全在左边（比如 [l, mid] 里）
2. 完全在右边（比如 [mid+1, r] 里）
3. 跨过中间（左边的一部分 + 右边的一部分）

所以，如果我们知道：

• 左边区间的最大后缀和（从右边往左能取到的最大和）
• 右边区间的最大前缀和（从左边往右能取到的最大和）

那么“跨中”的最大和 = 左边最大后缀 + 右边最大前缀。

因此，每个区间需要维护四个值：

名称	含义
total	整个区间的总和
maxPrefix	从左端点开始的最大连续和（前缀）
maxSuffix	到右端点结束的最大连续和（后缀）
maxSub	区间内任意位置的最大连续子段和（最终答案）

如何合并两个相邻区间？

假设我们有两个挨着的区间 A = [l, m] 和 B = [m+1, r]，它们的信息已知。

合并成 [l, r] 后：

total       = A.total + B.total
maxPrefix   = max(A.maxPrefix, A.total + B.maxPrefix)
maxSuffix   = max(B.maxSuffix, B.total + A.maxSuffix)
maxSub      = max(A.maxSub, B.maxSub, A.maxSuffix + B.maxPrefix)

✅ 这就是全部！

怎么预处理所有区间？

我们用区间 DP，按长度从小到大计算：

• 先处理所有长度为 1 的区间；
• 再处理长度为 2、3……直到 n；
• 对每个长度，枚举起点 i，终点 j = i + len - 1；
• 把 [i, j] 拆成 [i, k] 和 [k+1, j]，但为了简单，我们固定 k = j - 1，即每次只加一个元素。

为什么可以？因为 [i, j-1] 已经包含了完整信息，加上 a[j] 就能更新出 [i, j] 的四个值。

初始化（长度为 1）

对每个位置 i：

total[i][i] = a[i];
maxPrefix[i][i] = a[i];
maxSuffix[i][i] = a[i];
maxSub[i][i] = a[i];

转移（长度 ≥ 2）

对每个区间 [i, j]（j > i）：

// 把 [i, j] 看作 [i, j-1] + [j]
int left = i, right = j;
int prevEnd = j - 1;

total[left][right] = total[left][prevEnd] + a[right];

maxPrefix[left][right] = Math.max(
    maxPrefix[left][prevEnd],           // 不包含 a[j]
    total[left][prevEnd] + a[right]     // 包含 a[j]，把前面全加上
);

maxSuffix[left][right] = Math.max(
    (long) a[right],                    // 只取 a[j]
    maxSuffix[left][prevEnd] + a[right] // 接上前面的后缀
);

maxSub[left][right] = Math.max(
    maxSub[left][prevEnd],              // 最优在左边
    maxSuffix[left][prevEnd] + a[right] // 跨越 j-1 和 j
);
maxSub[left][right] = Math.max(maxSub[left][right], (long) a[right]); // 防止漏掉单个元素

注意：最后一步确保即使全是负数，也能取到最大的那个。

---

参考代码

import java.util.Scanner;

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

        // 四个二维数组，存储每个区间的四种信息
        long[][] total = new long[n + 1][n + 1];      // 区间总和
        long[][] maxPrefix = new long[n + 1][n + 1];  // 最大前缀和
        long[][] maxSuffix = new long[n + 1][n + 1];  // 最大后缀和
        long[][] maxSub = new long[n + 1][n + 1];     // 最大连续子段和

        // 初始化：单个元素
        for (int i = 1; i <= n; i++) {
            total[i][i] = a[i];
            maxPrefix[i][i] = a[i];
            maxSuffix[i][i] = a[i];
            maxSub[i][i] = a[i];
        }

        // 枚举区间长度，从 2 到 n
        for (int len = 2; len <= n; len++) {
            for (int i = 1; i + len - 1 <= n; i++) {
                int j = i + len - 1;

                // 合并 [i, j-1] 和 [j]
                total[i][j] = total[i][j - 1] + a[j];

                maxPrefix[i][j] = Math.max(
                    maxPrefix[i][j - 1],
                    total[i][j - 1] + a[j]
                );

                maxSuffix[i][j] = Math.max(
                    (long) a[j],
                    maxSuffix[i][j - 1] + a[j]
                );

                maxSub[i][j] = Math.max(
                    maxSub[i][j - 1],
                    maxSuffix[i][j - 1] + a[j]
                );
                // 确保不会比单个元素还小（应对全负情况）
                if (a[j] > maxSub[i][j]) {
                    maxSub[i][j] = a[j];
                }
            }
        }

        int q = sc.nextInt();
        while (q-- > 0) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            System.out.println(maxSub[l][r]);
        }
    }
}

总结

• 每个区间维护四个值：总和、最大前缀、最大后缀、最大子段和；
• 通过“逐步扩展右端点”来合并信息；
• 预处理 ​ O(n^2) ，查询 ​ O(1) ；

蓝桥村的真相

题目链接

解题思路

设说真话为 1，说假话为 0。

每个人说：“我后面的两个人中，一个说真话，一个说假话”。

我们假设第 ​ x 个人说的是真话（即 ​ x = 1 ），那么根据他说的内容，​ x+1 和 ​ x+2 必须一真一假。

对此分两种情况讨论：

• 情况一：​ x+1 是真话，​ x+2 是假话

  • 因为 ​ x+1 说真话，所以他的话成立：​ x+2 和 ​ x+3 一真一假；
  • 已知 ​ x+2 是假话，所以 ​ x+3 必须是真话。

• 情况二：​ x+1 是假话，​ x+2 是真话

  • 因为 ​ x+1 说假话，所以他的话不成立：​ x+2 和 ​ x+3 不是一真一假，即两者同真或同假；
  • 已知 ​ x+2 是真话，因此 ​ x+3 也必须是真话。

综上，只要 ​ x 说真话，则 ​ x+3 一定说真话。

由于村民围成一圈（下标模 ​ n ），若存在一个说真话的人，则每隔 3 人就必须再有一个说真话的人。这只有在 ​ n 是 3 的倍数时才可能成立。

当 ​ n \bmod 3 \ne 0 时，无法形成自洽的环，故所有人只能说假话。

当 ​ n \bmod 3 = 0 时，有以下四种合法方案：

1. 全部说假话 → 假话人数 = ​ n
2. 循环模式 110 → 每 3 人中有 1 个假话 → 假话人数 = ​ n/3
3. 循环模式 101 → 假话人数 = ​ n/3
4. 循环模式 011 → 假话人数 = ​ n/3

总假话人数 = ​ n + n/3 + n/3 + n/3 = 2n

---

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            long n = sc.nextLong();
            System.out.println(n % 3 == 0 ? 2 * n : n);
        }
    }
}

数字排列

题目链接

解题思路

这是一个经典的“分治构造”问题。我们从最大值 20 开始，逐步插入更小的数作为“分隔符”。

构造规则如下：

• 初始序列：[20]
• 第 1 步：在两侧保留 [20]，中间插入 19 → [20, 19, 20]（因为
• 第 2 步：在当前整个序列前后各放一份原序列，中间插入 18 →[20,19,20, 18, 20,19,20]
• 第 ​ k 步：新序列 = old + [20 - k] + old

这样构造保证：

• 所有相同的数之间夹着更小的数（因为每次插入的是当前最小值）；
• 序列长度呈指数增长：第 ​ k 步后长度为 ​ 2^{k+1} - 1

由于 ​ 2^{17} = 131072 > 10^5 ，只需构造 17 层即可覆盖最大需求。

---

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
  
        // 初始序列只有一个数：20
        String answer = "20";
  
        // 构造17层，每层将当前序列复制到两边，中间插入(20 - i)
        for (int i = 1; i <= 17; i++) {
            // 新序列 = 原序列 + 空格 + (20 - i) + 空格 + 原序列
            answer = answer + " " + (20 - i) + " " + answer;
        }
  
        // 按空格分割成数组
        String[] split = answer.split(" ");
  
        // 输出前n个数
        for (int i = 0; i < n; i++) {
            System.out.print(split[i] + " ");
        }
    }
}

选数异或

题目链接

线段树/st表，超纲暂时不讲

研发资源分配

题目链接

解题思路(枚举分割点贪心解法)

问题建模与关键观察

本题描述了一个 A、B 两部门在 ​N 天内提交需求等级的博弈过程：

• 每天编号为 ​1 到 ​N，当天资源量等于日期编号。
• A 和 B 各自使用 ​1 到 ​N 的整数各一次（不重复）作为提交等级。
• 若 A 提交等级 > B，则 A 获得当天资源；若 <，则 B 获得；若相等，双方都不得分。
• A 已知 B 的完整提交序列，目标是 最大化 A 总资源 - B 总资源。

关键在于：A 可以提前规划自己的数字分配策略。

最大等级不可胜

考虑 B 在某天提交等级 ​N。由于 A 的可用数字集合为 ​\{1,2,\dots,N\}，不存在大于 ​N 的数，因此 A 无法赢得该回合。此时 A 仅有两种可行选择：

• 选择 1（放弃）：提交一个小于 ​N 的数字，导致 B 赢得该天资源；
• 选择 2（平局）：提交 ​N，双方均不得分，问题转化成了规模更小的子问题：两个部门在1到​N-1中进行资源分配。

若选择平局，则数字 ​N 被消耗，无法用于其他回合；若选择放弃，则保留 ​N 可用于击败 B 的其他较小等级（如 ​N-1）。

策略结构：唯一自由度在于“牺牲哪一个等级”

进一步分析可知，A 最多能击败 B 的 ​N-1 个等级（因最大可胜等级为 ​N-1，需用 ​N 击败）。
但 A 共有 ​N 个数字，必须分配以覆盖 B 的全部 ​N 个等级。

因此，A 可以选择一个“分割点” ​k（​1 \leq k < N），采取如下策略：

• 赢下 B 的等级 ​1 到 ​k：对于B 的某个连续低等级区间 ​\{1, 2, \dots, k\}，使用 ​\{2, 3, \dots, k+1\}；
• 输掉 B 的等级 ​k+1：A 用最小的剩余数字（如 ​1）应对，B 获得该天资源；
• 对 B 的等级 ​k+2 到 ​N 全部打平：A 使用相同数字打平，双方不得分。

此时：

• A 总得分 = 所有等级 ​1 到 ​k 对应的日期之和；
• B 总得分 = 等级 ​k+1 对应的日期；
• 差值 = ​\sum_{i=1}^{k} \text{day}(i) - \text{day}(k+1)。

其中 ​\text{day}(x) 表示 B 提交等级 ​x 的那一天（即该回合的价值）。

枚举分割点求最优解

我们只需预处理出 value[x] = day，即等级 ​x 出现在第几天。
然后枚举所有可能的 ​k（从 ​1 到 ​N-1），计算对应差值，取最大值即可。

注意：当 ​k = N-1 时，A 赢了 ​1 \sim N-1，输掉 ​N，这是合法且常见的最优情形。

该策略覆盖了所有可能的最优情况，因为任何其他策略（如主动输掉多个等级）都会导致 A 得分减少或 B 得分增加，不会更优。

参考代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] value = new int[n + 5];
        for (int i = 1; i <= n; i++) {
            int p = sc.nextInt();
            // B 在第 i 天提交等级 p，该回合资源量为 i
            value[p] = i;
        }
        long sumA = 0, result = 0;
        // 枚举分割点 k：A 击败等级 1~k，牺牲等级 k+1，其余平局
        for (int k = 1; k < n; k++) {
            sumA += value[k];          // 累加 A 获得的资源
            long sumB = value[k + 1];  // B 获得的资源（仅等级 k+1）
            result = Math.max(result, sumA - sumB);
        }
        System.out.println(result);
    }
}

该算法时间复杂度为 ​O(N)，空间复杂度为 ​O(N)。

双子数

解题思路

题目链接

我们要找满足以下条件的数 x 的个数：

等价于：

• 枚举所有 不同的质数对 ​(p, q)，且 ​p > q（避免重复）
• 计算 ​x = p^2 \cdot q^2
• 检查是否 ​2333 \leq x \leq 233333333333

参考代码

import java.util.*;

public class Main {
    // 题目给定的范围
    static final long LOWER_BOUND = 2333L;
    static final long UPPER_BOUND = 23333333333333L;

    // 筛法上限：经估算，质数最大不超过 ~500,000，取 5e6 足够安全
    static final int SIEVE_LIMIT = 5_000_000;

    public static void main(String[] args) {
        // 筛出所有质数
        List<Integer> primes = eratosthenesSieve(SIEVE_LIMIT);

        // 枚举所有不同的质数对 (p, q)，其中 p > q
        int count = 0;
        int n = primes.size();

        for (int i = 0; i < n; i++) {
            long p = primes.get(i);
            // 优化：若最小的 x = p^2 * 2^2 已超过上限，则后续更大 p 无需考虑
            if (p * p * 4L > UPPER_BOUND) break;

            for (int j = 0; j < i; j++) {
                long q = primes.get(j);
                // 计算双子数 x = p^2 * q^2
                long x = p * p * q * q;

                // 由于 q 递增，x 也递增，一旦超出上限可提前终止内层循环
                if (x > UPPER_BOUND) {
                    break;
                }

                // 如果 x 在目标区间内，计数加一
                if (x >= LOWER_BOUND) {
                    count++;
                }
            }
        }

        System.out.println(count);
    }

    /**
     * 使用埃拉托斯特尼筛法（Eratosthenes Sieve）生成 [2, limit) 内的所有质数。
     * <p>
     * 算法思想：
     * - 初始化一个布尔数组 isPrime，假设所有数都是质数；
     * - 从 2 开始，将每个质数的倍数标记为合数；
     * - 最终未被标记的即为质数。
     * <p>
     * 时间复杂度：O(n log log n)
     * 空间复杂度：O(n)
     *
     * @param limit 筛选上界（不包含）
     * @return 按升序排列的质数列表
     */
    private static List<Integer> eratosthenesSieve(int limit) {
        boolean[] isPrime = new boolean[limit];
        Arrays.fill(isPrime, true); // 初始假设所有数都是质数
        isPrime[0] = false;
        if (limit > 1) isPrime[1] = false;

        // 从 2 开始筛
        for (int i = 2; i * i < limit; i++) {
            if (isPrime[i]) {
                // 将 i 的所有倍数（从 i*i 开始）标记为合数
                for (int j = i * i; j < limit; j += i) {
                    isPrime[j] = false;
                }
            }
        }

        // 收集所有质数
        List<Integer> primes = new ArrayList<>();
        for (int i = 2; i < limit; i++) {
            if (isPrime[i]) {
                primes.add(i);
            }
        }
        return primes;
    }
}