1. 拿到题目先别写代码先把“故事”剥掉1.1 为什么文艺标题总要配一个奇怪的模型看到“P8590 『JROI-8』这是新历的朝阳也是旧历的残阳”这个标题时我正在翻题单。第一反应是这怕是又一道把语文和算法绑在一起的题。“新历”“旧历”“朝阳”“残阳”四个词摆在一起明显在暗示一件事——存在一个分界点分界点两边的时间规则不一样。做竞赛题多了就会发现越是这种带文学包装的标题底下越藏着一个“分段计算”或者“分段规则”的模型。拿到这种题心态特别容易崩的同学会直接盯着题面里的故事看半天试图从“新历”“旧历”里读出点隐藏条件。我的经验是反过来的先把故事放一边直接去数据范围、输入格式和“求什么”下手。因为无论题目把背景写得多么诗意最后落回来的无非是数组、区间、前缀、后缀、最值这些老面孔。标题的作用不是为了提供线索而是告诉我们这个题大概率要你“选一个位置两侧按不同方式贡献”。1.2 一个用于讲解的简化模型说实话原题的完整细节我不打算在这里逐字复述因为复盘类文章最重要的不是让你照着抄一遍原题而是把一类题的思考路径留下来。为了方便讲解我把题目核心抽象成下面这样一个简化模型你只要看懂了它再看原题就会觉得“原来是这么回事”。给定一个长度为 n 的正整数序列 a[1..n]要求选一个分割点 x把序列切成左右两段。左侧旧历部分的第 i 个元素贡献为 (i - 1) × a[i]右侧新历部分的第 i 个元素贡献为 (n - i) × a[i]。最终答案是f(x) Σ_{i1}^{x} (i-1)·a[i] Σ_{ix1}^{n} (n-i)·a[i]要求最大化这个 f(x)。这个模型怎么理解左侧权重 (i-1) 意味着在“旧历”那一边越靠近结尾的元素权重越大就像一段历史残影越接近落幕越沉重右侧权重 (n-i) 则是越靠近开头权重越大像朝阳初升刚登场的影响最盛。你把 x 当作新旧历法交接的那一天整个式子就是在求一个“交替时刻”让整体影响最大。这个抽象版本和很多实际题目的思想是一致的只是具体系数和限制条件可能不同。读题时要做的事就是把题面里一堆修饰语全部换成这种干净的数学符号。1.3 先写暴力再优化竞赛铁律我说句得罪人的话很多同学一看到这种题就开始想贪心怎么办、DP怎么写结果想了半小时没结果心态直接崩掉。正确的顺序永远是先写一个最暴力、最无脑的枚举再在这个基础上谈优化。暴力是什么枚举每个可能的 x从 1 到 n-1每次重新累加两边。复杂度 O(n²)n 在几百的时候完全没问题。代码写起来也快十分钟能搞定。你要用它做什么第一验证自己对题面的理解是不是对的第二作为后续优化的“标准答案”代码写错了能对拍第三让你在推导优化时有个具体的数据结构可以参考不会飘。我一直跟身边的朋友说暴力不是丢人的暴力是你手里最可靠的那把尺子。一道题难不难先看你能否写出一个“正确但慢”的版本。能写出来说明题目读懂了接下来才是考虑怎么变快。2. 核心式子的推导从 O(n²) 到 O(n)2.1 拆开式子前缀和后缀各管一边回到 f(x) 这个式子。表面上枚举 x 之后还要遍历两段数组所以看起来是 O(n²)。但你把两个求和符号分开看立刻能发现端倪。左边的 Σ_{i1}^{x} (i-1)·a[i] 只跟前缀有关。如果我用一个数组 W1[x] 表示“从第一个元素到第 x 个元素按照 (i-1) 加权的和”那么左边这一整块就等价于 W1[x]。右边的 Σ_{ix1}^{n} (n-i)·a[i] 只跟后缀有关。同理用 W2[x1] 表示“从第 x1 个元素到第 n 个元素按照 (n-i) 加权的和”右边这一整块就是 W2[x1]。于是 f(x) 直接变成f(x) W1[x] W2[x1]这个转化看起来平平无奇但它把复杂度从“每次枚举都要重新扫数组”降成了“提前预处理枚举时 O(1) 查询”。怎么预处理呢 W1 可以顺着扫一遍W1[i] W1[i-1] (i-1) × a[i]W2 就得从右往左扫注意下标的语义。W2[i] 表示从 i 到 n 的加权和边界是 W2[n1] 0然后W2[i] W2[i1] (n-i) × a[i]这样一来整个算法的复杂度就是 O(n) 预处理加上 O(n) 枚举 x总共 O(n)空间 O(n)。n 到 1e6 也完全不虚。2.2 差分视角看看 f(x) 到底长什么样做到 O(n) 其实已经能过题了但你别急着收手。我习惯再往下推一步看看 f(x) 本身有没有什么结构。把相邻两个位置做差f(x1) - f(x) (W1[x1] W2[x2]) - (W1[x] W2[x1])展开之后W1 的增量是 x × a[x1]W2 的增量是 -(n-(x1))×a[x1]。合起来f(x1) - f(x) (2x 1 - n) × a[x1]这个式子太舒服了。如果题目保证 a[i] 全部非负那么 f(x) 的增减完全由 2x 1 - n 的符号决定。也就是说x 较小时 f(x) 单调下降x 较大时单调上升整个函数是个“碗”形最大值只可能出现在两个端点。当然如果 a[i] 正负都有差分符号就不确定了老老实实 O(n) 扫描每个位置取 max 最稳妥。这个差分推导的价值在于它让你真正理解 f(x) 的变化规律而不是只会套模板。面试或者写题解的时候能写出这一层别人就知道你不只是背了代码你是真的把式子吃透了。2.3 完整 AC 代码与下标细节代码我习惯用 1-index因为这样跟题面里的“第 i 个元素”一一对应不容易错。写得干净一点#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n 1); for (int i 1; i n; i) cin a[i]; vectorlong long W1(n 1, 0), W2(n 3, 0); // 前缀加权和W1[i] sum_{j1..i} (j-1) * a[j] for (int i 1; i n; i) { W1[i] W1[i - 1] (long long)(i - 1) * a[i]; } // 后缀加权和W2[i] sum_{ji..n} (n-j) * a[j] for (int i n; i 1; i--) { W2[i] W2[i 1] (long long)(n - i) * a[i]; } long long ans LLONG_MIN; // x 可以从 1 到 n-1如果允许空段则改成 0 到 n for (int x 1; x n - 1; x) { ans max(ans, W1[x] W2[x 1]); } cout ans endl; return 0; }几个下标细节值得专门说一下。W2 数组一定要多开两个空间因为循环里会访问 W2[i1]in 时是 W2[n1]你需要保证这个位置存在且为 0。如果你只开到 n1在某些编译器下不会报错但值是野的答案就莫名其妙错了。这个坑我踩过不止一次。另外 (long long)(i - 1) * a[i] 这个强制转换一定不能省。i 和 a[i] 都是 int两个 int 相乘会先按 int 计算再赋值一旦乘积超过 2^31-1得到的是一个已经溢出的 int转 long long 也救不回来。3. 这类题的变式和进阶优化3.1 如果系数不是 i-1 和 n-i 怎么办好基础版做完了但你得清醒一点原题基本不可能只给你这么顺滑的系数。它可能把 (i-1) 换成 (i1)把 (n-i) 换成 (n-i1)也可能在右侧乘上另一个数组 b[i]比如右侧贡献是 (n-i)×b[i]左侧还是跟 a[i] 有关两侧用两种数组做双前缀维护。思路不会变凡是“只跟左端点有关”“只跟右端点有关”的贡献都可以通过前缀和后缀预处理去解决。你只需要回答一个问题——当我固定分割点 x 时每一部分的贡献能不能写成某个前缀或后缀的某种统计量如果能下一步永远是定义两个辅助数组把内层循环拆掉。有些题更阴险它把分割点要求成“左侧至少两个元素右侧至少一个元素”或者“左右非空且左侧元素个数必须是偶数”。这种限制照样能处理无非是在枚举时跳过不合法的 x或者把前缀数组定义成只统计偶数位置。不要被这种表面限制吓住核心的“前缀后缀”模型一点没变。3.2 决策单调性与分治优化如果你遇到的变式里f(x) 的差分不再是简单表达式而是每一项还跟别的数组有关导致 f(x) 不是严格的“碗形”那 O(n) 扫描可能会失效但你还有一种常见工具决策单调性。什么叫决策单调性简单说就是最优分割点 x 会随着某个参数比如 n 增大单调移动。如果题目让你对很多次不同的区间询问答案而最优 x 满足单调性你可以用分治优化把原本“每次询问都扫描一遍”的复杂度降下来总复杂度大约是 O(m log n) 到 O((n m) log n) 级别。判断决策单调性最靠谱的办法还是推不等式或者直接看差分符号会不会只有一个转折点。竞赛里很多“选分界点求最大”的题本质都是决策单调性 分治优化或者再加一个李超线段树做斜率优化。这里不展开因为篇幅有限但你心里得有这根弦一道题能 O(n) 扫描不代表最优解法就止步于此出题人完全可能在 n 和询问次数上再加大力度。3.3 取模、溢出与 __int128 的兜底很多题为了让答案不无限膨胀会要求对某个大质数取模。这里有个特别容易翻车的点如果你要找的是“真实值最大”但最后要输出这个最大值对 mod 取余的结果运算过程绝对不能“边取模边比大小”。为什么因为取模破坏了大小关系。假设真实值一个是 999 一个是 1000mod 1000 后一个是 -1 移位一个是 0你比较之后选出了 0 对应的那个但真实答案明明是 999。所以正确做法是计算和比较时用真值只在最终输出前取模。如果真值可能连 long long 都放不下呢那就用 GCC 扩展类型 __int128。它最大能到约 1.7×10^38绝大多数“看起来很大”的中间结果都能吞下。注意 __int128 不能直接 cin/cout要自己手写输入输出比赛环境支持度也基本没问题但不要用到正式题解里。我个人的习惯是只要涉及“加权和”或“前缀乘积和”一律先把数组开成 long long乘法里再顺手套一个 (long long)。这是成本最低的保险没有必要为了省几个字节去开 int。4. 我踩过的坑WA、TLE、对拍全记录4.1 边界条件一改答案就翻车这类分割点题目第一个隐形杀手是边界。x 能不能等于 0能不能等于 n如果 x0 意味着左段为空xn 意味着右段为空。不同的题目设定答案完全不同。有的题目允许空段那么你的循环要写成 x 从 0 到 n有的题目严格要求两段都非空那 x 只能从 1 到 n-1。一旦搞错小样例可能侥幸通过大数据里边界情况直接 WA。我的做法是拿到题先死抠这一句话“分割点”的定义里有没有说左右都至少有一个如果没有请手动测试 x0 和 xn 两个极端。另外输出负数答案、所有数相同、n1、n2 这几种极端case写题的时候务必自己先测一遍。4.2 int 溢出最隐蔽的锅还有一次我写完 O(n²) 暴力拿去对拍暴力版用 long long优化版也用了 long long但样例一到 1e5 级别就开始 WA。查了半小时最后发现是前缀数组预处理里有个地方写成了 int len i - 1然后 len * a[i] 两个 int 相乘结果溢出成负数了。就这么简单且愚蠢。认真复盘一下只要 n 超过 1e5a[i] 超过 1e9加权和很容易冲到 1e14 以上这已经超出 int 上限了。所以我的铁律是涉及累加、累乘、下标乘值的变量全部无脑 long long不要在脑子里给数据“预估大小”因为几乎所有溢出都是预估错误造成的。4.3 对拍5 分钟从 WA 到 AC 的笨办法如果你发现自己 WA 到怀疑人生最快的出路就是对拍。做法很简单写一个暴力版 solve_baoliO(n²) 枚举几百条数据绝不出错。写一个优化版 solve_fast。写一个随机数据生成器n 控制在 1 到 20a[i] 控制在 -5 到 5因为小数据更容易暴露边界问题。循环 10000 次每次生成数据分别跑两个函数一旦结果不同立刻把当前数组打印出来肉眼分析。这个流程听起来笨实战中威力极大。它把“玄学 WA”变成“可复现的最小反例”。我是强烈建议每个选手把这个流程练成本能它比你背一百个模板都管用。4.4 回看“新历朝阳”那句话当我最终把代码提交、看到 AC 的那一刻再回头看标题“这是新历的朝阳也是旧历的残阳”突然觉得题目出得挺妙。分界点左侧是残阳右侧是朝阳两边各有各的规则各有各的权重。而算法上它们不过是前缀和与后缀和各自维护一段权重数组最后在某一个位置汇合。我个人做这类题最大的体会是不要被文学化的题目吓住也不要轻视前缀后缀这个基础操作。你越是能把一个看似浪漫的模型拆成干干净净的求和公式越是能感受到算法里那种“规则分明”的美感。下次如果你再碰到这种带“朝阳”“残阳”的题希望你能比我更快地把那层故事皮剥掉直接看到下面那层数学骨架。