ARTICLE · 1205905
洛谷 2026 第二轮(复赛 J 组)模拟题解
一本书共有 n 面。第 i 张 A4 纸的正面印第 2i-1 面，反面印第 2i 面；如果书没有这一面，就留空。
A4 纸共有 k 张。装订时，第 1 张和第 k 张 A4 的内容合并到第 1 张 A3 纸上，第 2 张和第 k-1 张合并到第 2 张 A3 纸上，依此类推。
如果 k 是奇数，最中间那张 A4 纸没有配对，会单独使用一张 A4 纸。
现在给定 m，求第 m 面最终印在哪里：
• 如果印在 A3 纸上，输出对应的 A3 纸编号；
• 如果单独印在 A4 纸上，输出 0。
每张 A4 纸放两面，所以：
i = (m + 1) / 2
这里的除法是向下取整。
k = (n + 1) / 2
第 i 张 A4 纸和第 k + 1 - i 张 A4 纸会被合并到同一张 A3 纸上。
因此，这一对对应的 A3 纸编号是：
min(i, k + 1 - i)
当 k 为奇数时，最中间的 A4 纸编号为：
(k + 1) / 2
它没有配对的 A4 纸，所以答案为 0。
1. 计算 k = (n + 1) / 2。
2. 计算 i = (m + 1) / 2。
3. 令 ans = min(i, k + 1 - i)。
4. 如果 k 是奇数且 i == (k + 1) / 2，则令 ans = 0。
5. 输出 ans。
• 时间复杂度：O(1)
• 空间复杂度：O(1)
给定一个长度为 n 的正整数数组 A。把每个元素染成红色或蓝色。
对于第 i 个元素：
• 如果它左边没有与它同色的元素，则 C[i] = 0；
• 否则，设它左边最近的同色元素为 A[j]，则 C[i] = A[i] - A[j]。
求 C[1] + C[2] + ... + C[n] 的最大值。
对于同一种颜色，假设它的元素出现位置为：
p1 < p2 < ... < pm
那么这种颜色产生的分数为：
• 第 p1 个位置：0
• 第 p2 个位置：A[p2] - A[p1]
• 第 p3 个位置：A[p3] - A[p2]
• ……
• 第 pm 个位置：A[pm] - A[pm-1]
全部相加后，中间项会全部抵消，只剩下：
A[pm] - A[p1]
也就是说：
一种颜色的总贡献 = 这种颜色最后一个元素的值 - 这种颜色第一个元素的值。
因此总分为：
红色最后一个值 - 红色第一个值
+ 蓝色最后一个值 - 蓝色第一个值
下标 1 一定是某种颜色的第一个元素，下标 n 一定是某种颜色的最后一个元素。
假设它们都是红色，那么红色的贡献固定为：
A[n] - A[1]
蓝色只能出现在 2 到 n-1 之间。
• 如果蓝色的贡献小于等于 0，那么不使用蓝色，或者只放一个蓝色元素即可，总分仍然是 A[n] - A[1]。
• 如果蓝色的贡献大于 0，设蓝色第一次出现在 p，最后一次出现在 q，则贡献为 A[q] - A[p]。把 n 改染成蓝色，并让红色最后出现在 q，可以构造一个 1 和 n 异色的方案，得到同样的总分，因此这种情况会被下面的情况包含。
假设 1 是红色，n 是蓝色。
设：
• i 为红色最后出现的位置；
• j 为蓝色第一次出现的位置。
因为 j 是第一次出现的蓝色，所以 j 之前必须全是红色；因为 i 是最后一次出现的红色，所以 i 之后必须全是蓝色。
因此必须满足：
j <= i + 1
此时总分为：
(A[i] - A[1]) + (A[n] - A[j])
也就是：
A[n] - A[1] + (A[i] - A[j])
为了让分数最大，对于每个 i，只需要让 A[j] 尽可能小，其中：
2 <= j <= i + 1
所以答案为：
A[n] - A[1] + max(0, max(A[i] - min(A[2..i+1])))
其中 1 <= i < n，2 <= j <= i + 1。
其中 max(0, ...) 表示如果使用第二种颜色不会让答案更大，就保持全染同色的方案。
1. 令 mn 表示 A[2] 到 A[i+1] 的最小值。
2. 从左到右枚举 i = 1 ... n-1。
3. 每次把 A[i+1] 加入 mn。
4. 用 A[i] - mn 更新 best。
5. 最终答案为 A[n] - A[1] + best。
• 时间复杂度：O(n)
• 空间复杂度：O(n)
A = [1, 2, 1]
• 基础贡献：A[3] - A[1] = 0
• 扫描得到的最优差值：2 - 1 = 1
• 答案：0 + 1 = 1
A = [3, 4, 9, 8, 2, 4]
• 基础贡献：4 - 3 = 1
• 扫描得到的最优差值：8 - 2 = 6
• 答案：1 + 6 = 7
对应的一种染色方案是：前四个元素染成红色，后两个元素染成蓝色。
红色贡献：8 - 3 = 5
蓝色贡献：4 - 2 = 2
总分：5 + 2 = 7
• 最大得分可能为负数。例如 A = [3, 2, 1] 时，最优得分是 -1，代码不能默认答案一定大于等于 0。
