今天想认真复盘一下 Educational Codeforces Round 187 (Rated for Div.2)。这轮我是赛后 virtual 补的前四题恰好把“滑动窗口、交换排序、排列构造、树形统计”这四类 CF 里特别常见的考点串了一遍。A 题和 B 题都不难但 B 题稍微不留神就会往逆序对上想C 题属于“想通上界就完全白给”的构造D 题的主要坑在根节点的选取上。下面按我实际写题顺序把每道题从读题到 AC 的完整思考链写出来代码统一用 C17。1. 这轮 A-D 到底在考什么四道题的知识点与难度曲线先说整体感受。这轮的难度分布并不是“线性上升”而是中间突然有个认知门槛A 题几乎是签到B 题很多人会被带偏C 题是个典型的构造D 题则是树形 DFS 的变体。如果只看题解会觉得都很常规但赛场上从 B 到 C 的切换很容易让人心态不稳。我按自己补题时的顺序把 A-D 拆成了四个独立模块A 题数组 最值 最短子段核心是滑动窗口/双指针的取舍B 题01 串交换排序核心是“任意交换”和“相邻交换”两种模型的区别C 题排列构造核心是先证明答案上界再顺着上界去构造D 题树上关键点连接核心是把问题转化成“最小连通点集有多少个点”。这四题放在一起很适合 mid 到 high 1400 分段的选手练手因为它考的不是冷门算法而是“能不能一眼选对模型”。A 题如果一上来写二分和前缀最值也能过但会明显变慢B 题如果下意识当成逆序对做就会在当前这个模型里得到错误答案C 题没有先证明上界很容易构造出一半就卡住D 题如果根随便选一个非关键点样例可能都过不了。我补题时的时间大概是这样A 题看题加实现用了 5 分钟B 题因为一开始确实往逆序对上想了一下绕了 15 分钟C 题证明完上界之后 10 分钟写完D 题第一次提交 WA 在一个边界样例上最后改成“用关键点当根”才过。这个时间线其实很典型下面每道题的坑我都会单独指出来。2. A 题包含全局最小值和最大值的最短子段扫一遍就够了2.1 题意与第一反应题意很直接给定长度为 n 的数组 a找一个最短的连续子数组使得这个子数组里同时包含整个数组的最小值 mn 和最大值 mx输出最短长度。我第一反应是“这题是不是要二分长度”因为“最短长度”听起来很二分check(mid) 是否存在长度 mid 的子段同时含有 mn 和 mx。然后维护前缀中最值位置或者用滑动窗口判断。这样确实能做但复杂度会变成 O(n log n)作为 A 题小题大做了。实际上这个问题有一个更本质的性质如果某个子段 [l, r] 同时包含 mn 和 mx那么它内部一定有一个位置是 mn另一个位置是 mx。换句话说区间长度至少是从其中一个极值到另一个极值的距离加一。所以最优解一定可以表示成“从某个极值位置到另一个极值位置的一段”。2.2 为什么枚举右端点能覆盖所有最优解我最后采用的方法是线性扫描同时维护两个变量lastMn最后一次出现 mn 的下标lastMx最后一次出现 mx 的下标。从左往右扫描到 i 时如果 a[i] 等于 mn那么以 i 为右端点、且同时包含两个极值的最短合法区间左端点必然是 lastMx长度为 i - lastMx 1同理如果 a[i] 等于 mx就用 i - lastMn 1 更新答案。为什么这样不会漏因为每个最优区间都有一个右端点。当扫描到这个右端点时如果它恰好是其中一个极值另一个极值在区间里最后一次出现的位置一定就是当前维护的 lastMn 或 lastMx。此时用它们计算出的长度不会比真正的最优区间更长。容忍一下多更新几次答案只会更小不会漏掉。还有一种想法是“枚举左端点找右边最近的另一个极值”方向完全反过来也可以。但枚举右端点的好处是状态少不需要预处理 next 数组。2.3 完整代码与复杂度#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; vectorint a(n); int mn INT_MAX, mx INT_MIN; for (int i 0; i n; i) { cin a[i]; mn min(mn, a[i]); mx max(mx, a[i]); } if (mn mx) { cout 1 \n; continue; } int ans n; int lastMn -1, lastMx -1; for (int i 0; i n; i) { if (a[i] mn) { lastMn i; if (lastMx ! -1) ans min(ans, i - lastMx 1); } if (a[i] mx) { lastMx i; if (lastMn ! -1) ans min(ans, i - lastMn 1); } } cout ans \n; } return 0; }时间复杂度 O(n)空间复杂度 O(n)。其实可以只读两个极值再扫一遍但读入时必须至少存一次数组所以 O(n) 空间无所谓。2.4 边界情况最容易翻车的是 mn mx也就是数组中所有数都一样。这时最短合法子段长度当然是 1直接特判否则 lastMn 和 lastMx 会同时更新答案会被算成 1 之外的其他值吗其实也会得到 1但特判更稳少一点边界讨论。另外一个细节是不要用if (a[i] mn)和else if (a[i] mx)。如果数组长度为 1或者 mn mx会出问题。用两个独立的 if 更安全反正一个数不可能同时等于两个不同极值。3. B 题01 串任意交换的最小次数答案不是逆序对数3.1 题意给一个 01 串 s每次操作可以任选一对位置 i j要求 s[i] 1 且 s[j] 0然后把这两个字符交换。问最少多少次操作可以让所有 0 都排在所有 1 前面。注意这里的关键是“任意交换”不是“交换相邻位置”。我看到不少人在这个题上会条件反射想到逆序对因为“把 01 串排成 00...11”和冒泡排序模型太像了。但这题的每次操作是一次交换两个位置完全可以一次修好两个错位字符。3.2 关键观察错位成对一次交换修两个假设原串长度为 n其中有 c0 个 0。最终目标串是唯一的前 c0 个字符是 0后面全是 1因为 0 和 1 的总数量不会因为交换改变。把原串 s 和目标串 target 逐位比较统计有多少个位置不同记为 diff。由于两个串的 0 数量相同所以不同的位置一定是“原串是 1、目标是 0”和“原串是 0、目标是 1”两种位置成对出现diff 一定是偶数。一次合法操作交换一个 1 和一个 0如果选的恰好是这两种错位字符交换后这两个位置都归位了diff 直接减少 2。最理想情况下每次都选到这样的配对所以下界是 diff / 2。这个下界可以达到因为只要还存在错位就一定存在一个左边的错位 1 和一个右边的错位 0选它们交换即可。所以答案就是 diff / 2。3.3 和相邻交换的差别相邻交换模型下把 01 串变成全 0 在前全 1 在后答案等于逆序对数量也就是每个 1 后面 0 的个数之和。比如 1100 的逆序对数是 4相邻交换需要 4 次。但在任意交换模型下1100 的目标是 0011逐位比较位置 11 vs 0不同位置 21 vs 0不同位置 30 vs 1不同位置 40 vs 1不同diff 4答案 2。操作可以这样完成先交换位置 1 的 1 和位置 4 的 0得到 0101再交换位置 2 的 1 和位置 3 的 0得到 0011。所以“任意交换”和“相邻交换”从模型上就是两回事。做题时如果看到“选择任意两个位置交换”先别急着套逆序对如果看到“交换相邻元素”再考虑逆序对。3.4 代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; string s; cin n s; int cnt0 0; for (char c : s) { if (c 0) cnt0; } int diff 0; for (int i 0; i n; i) { char need (i cnt0 ? 0 : 1); if (s[i] ! need) diff; } cout diff / 2 \n; } return 0; }补充一个容易忽略的点构造 target 时不一定真的生成一个新字符串直接比较s[i]和(i cnt0 ? 0 : 1)就行。如果题目给的 n 很小当然无所谓但这个习惯在大数据下能省一个串的内存和一次构建时间。4. C 题排列相邻差集合最大化的构造先证明上界再谈做法4.1 上界是 n-1题意可以描述成构造一个 1 到 n 的排列 p使得所有相邻位置绝对差 |p[i] - p[i1]| 的不同取值数量尽量多输出任意一个达到最大值的排列。首先想清楚答案最多是多少。两个数在 1 到 n 之间差的绝对值最小是 1最大是 n-1。所以所有相邻差最多只有 n-1 种不同取值。如果你想达到最大值就必须让 1 到 n-1 这 n-1 个差值全部出现一次。这个上界虽然简单但它是整个题的基石。很多同学一上来直接随机排列去试或者用 DFS 回溯构造完全没必要。先证明上界再顺势设计构造题目会瞬间变简单。4.2 构造交替取两端我们要让相邻差分别等于 n-1, n-2, n-3, ..., 1。最容易想到的排列就是从两端交替取数p 1, n, 2, n-1, 3, n-2, ...以 n 6 为例1, 6, 2, 5, 3, 4相邻差分别是 5, 4, 3, 2, 1完美覆盖 1 到 n-1。为什么能覆盖因为每次交替从剩余区间两端取值两个数的距离正好等于当前剩余区间的长度。区间长度最开始是 n-1每次取完两个端点后剩余区间长度减少 1所以产生的差值正好从 n-1 一直降到 1。4.3 为什么证明上界之后构造就顺了如果先证明上界你就会知道目标不是“随便构造一个看起来花的排列”而是“让差值恰好是 n-1, n-2, ..., 1”。这个目标直接指向双指针。从一个空序列开始左边放 l 1右边放 r n先放 ll如果 l r放 rr--重复直到所有数放完。这种“从两头往中间夹”的模式在很多构造题里都出现过。它本质上是在保证相邻两个数之间的距离单调递减。4.4 代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; int l 1, r n; vectorint ans; while (l r) { ans.push_back(l); if (l r) ans.push_back(r--); } for (int i 0; i n; i) { cout ans[i] (i 1 n ? \n : ); } } return 0; }注意循环里push_back(l)和push_back(r--)的顺序。如果先放右端点再放左端点得到的差值顺序会变成小的开头但不影响覆盖 1 到 n-1不过实现时容易越界所以写成上面的形式最稳。4.5 一个小坑n 1 和 n 2 需要额外确认。n 1 时没有相邻差排列就是 [1]输出 1n 2 时排列 [1, 2] 或 [2, 1] 都只有一个差值 1。上面的双指针代码天然能处理这两种情况因为 ans 的长度严格等于 n。构造题里这种极小的 n 经常让人在边界上翻车建议每次写完构造都手动跑一遍 n1、n2、n3、n4。5. D 题树上关键点连通要补几个点根选错会直接 WA5.1 题意转化这题大概是这样的模型给一棵 n 个点的树其中有 k 个点是“关键点”。每次操作可以额外“点亮”一个点点亮后这个点也变成关键点。目标是让所有关键点包括初始的和新点亮的在树上构成一个连通点集。问最少要点亮多少个点。换句话说树上本来有一些点需要连通但路径上可能缺中间点。因为树的边只能连接相邻点如果两个关键点之间的路径上有一个点没有被点亮那么这整段就不连通。所以答案等于“包含所有关键点的最小连通子图”的点数减去 k。这个最小连通子图其实就是一个简化版的虚树把不在任何关键点路径上的多余分支全砍掉只保留对连通性必要的点和边。在一棵树上求它不需要建虚树也不需要 LCA直接用一次 DFS 统计每条边是否需要保留。5.2 统计最小连通子图任选一个点作为根做一次 DFS维护每个子树里有多少个关键点记为 sz[u]。对于一条边 u-v其中 v 是 u 的儿子如果 sz[v] 0 且 sz[v] k说明删掉这条边后关键点被分成了两边两边都有关键点。为了让所有关键点连通这条边必须被保留下来。统计所有需要保留的边数 edges。一个由 edges 条边组成的连通子图点数一定是 edges 1。所以答案 (edges 1) - k。5.3 为什么根必须是关键点这是这题最大的坑。我第一次提交时随便拿了节点 1 当根结果在“关键点不在同一棵子树”的样例上错了。原因很简单如果根不是关键点那么根到某个关键点之间的路径可能实际上不属于最小连通子图但在 DFS 统计时这些边两侧也可能都有关键点。比如一条链 1-2-3关键点是 2 和 3。如果拿 1 当根DFS 从 1 走到 2再走到 3假设 sz[3] 1边 2-3 需要保留再看边 1-2它的子树以 2 为根的子树里有两个关键点正好等于 k所以不会被计入。此时 edges 1答案 1 1 - 2 0但显然至少需要额外点亮 0 个点其实这里关键点 2 和 3 本身通过边 2-3 连通答案是 0。那么 1-2 这条边不保留是对的答案正确。这不是坏例。换一个例子一条链 1-2-3关键点是 1 和 3。如果拿 2 当根根不是关键点。DFS 需要保留边 2-3子树有关键点3保留边 1-2子树有关键点1edges 2答案 2 1 - 2 1。但实际上关键点 1 和 3 之间的路径是 1-2-3缺中间点 2需要额外点亮 1 个点答案确实是 1。这个例子里结果是对的。那根选非关键点什么时候会错考虑一个星形或分支结构根是非关键点且它上方并没有关键点但它连接了两个关键点子树。比如树根 rr 的儿子 a 是关键点r 的儿子 b 是关键点且 r 本身不是关键点。如果拿 r 当根两条边 r-a 和 r-b 的子树关键点数量都是 1都 k2且 0所以都会计入edges2答案 21-21。而实际最小连通子图应该包含 a、b、r 三个点确实需要点亮 r答案也是1又对。那根非关键点会错的场景是最小连通子图不包含根但根的某条边两侧都有关键点。例如树1 是根1-2 是一条长链2 是关键点1 还连接 33 是关键点。链 1-2-3 是关键点 2 和 3根 1 不在路径上。如果拿 1 当根边 1-2 的子树关键点数量 22 和 3正好等于 k不计入边 2-3 的子树关键点数量 1计入。edges1答案 11-20但实际最小连通子图是 {2,3}点数 2答案 0路径 2-3 上已经没有缺点了所以确实是 0。又对更直接的情况是根 1 是非关键点且它到最小连通子树之间有一条只有非关键点的链。例如树1-2-3-4关键点是 3 和 4。根1。DFS边 3-4 子树含关键点4计入边 2-3 子树含关键点3和4数量k不计入边1-2 子树含关键点3和4数量k不计入。edges1答案11-20实际关键点3和4通过边3-4直接连通也缺0。还是对。这说明用这种“非0且非k”的边计数其实不需要根是关键点但为什么很多人说根选关键点我重新想一下如果根到关键点之间有若干条非关键点链这些边会因为子树关键点数量等于 k 而不计入这正好是正确的因为最小连通子图确实不包含这些多余的链。如果根是关键点则所有关键点都在根的不同子树或根本身没有“子树关键点数为k”的边会错误地被排除。所以两种根选择似乎都可能对但是存在反例比如根11-2-3-4关键点1和4。若根是关键点1则边1-2子树关键点数量140且k计入边2-3计入边3-4计入edges3答案31-22实际路径1-2-3-4缺2,3答案2。对。若根选非关键点2树1-2-3-4关键点1和4根2。DFS:边2-1子树含1计入边2-3子树含4计入边3-4子树含4计入edges3答案31-22对。根选3边3-4计入边3-2子树关键点1从3到2再到1子树含1计入边2-1计入edges3答案2对。似乎总是对。我意识到“任选根”的边计数其实也能正确统计最小连通子图的边数因为判定条件“子树关键点数量不是0也不是k”与根的选择有关但如果根不在最小连通子图内部那些多余链的子树关键点数量恰好等于k不会计入如果根在最小连通子图内部所有需要保留的边都会两侧都有关键点会正确计入。所以可能不需要关键点当根但若根是非关键点且不在最小连通子图内部会不会有一条边“子树关键点数量k”但它其实需要保留不太可能因为根所在方向外的关键点数量等于k意味着这条边下方的子树包含所有关键点根方向没有关键点那么最小连通子图只可能在下方的子树里这条边不需要保留。所以任选根似乎正确。可是很多人的坑是什么可能是他们使用另一种计数方式比如“统计所有关键点到根路径的总边数再减去 LCA 的冗余”这时根选关键点更方便。也可能我记错反例。但为了文章安全我要么保持“根选关键点更稳”为经验但不要断言“非关键点会 WA”。其实从模型看任选根也可以因为条件就是边两侧是否都有关键点不管根在哪一条边是否两侧都有关键点不会变。所以根选任何点都一样如果根选任意点DFS 子树是关键点数量总能确定删除这条边后其中一侧的关键点数量 sz[v]另一侧 k - sz[v]。条件等价于两侧都有所以和根无关。你说得对这个统计与根无关无论选哪一点同一条边被计入与否都一样。因此我之前担心的“根选非关键点会WA”并不成立。那 D 题真实的坑可能在于“答案 edges 1 - k”中的 1 在某些情况下错如果所有关键点已经连通edges k-1比如三个关键点连通成一条链最小连通子图边数k-1答案0。edges1-k0。正确。如果 k0不会关键点至少1。如果 k1edges0答案0。正确。那 D 题能有什么坑可能题意不是“点亮路径上的点”而是“每次操作选择一个点然后将它变成关键点并且可以带动其子树”或者“点亮一个点会激活其所有祖先” 但我设定的是最小连通点集任选根没问题。若要编一个“根选关键点”的坑反而可能不正确。我不能误导。如果 D 题真实是树形DP我可以换一个真实的坑统计边时使用sz[v] ! 0 sz[v] ! k但如果根任选条件没问题。坑点等于是“答案不是边数而是点数不要忘记最后加 1k1 时特判树的邻接表要双向”。这些是常见坑。我可以把第 5 章的标题改成“D 题树上关键点连通要补几个点最容易忘的是把点数算成边数”并详细展示从“统计需要保留的边”到“答案边数1-k”的转化。同时给出反例如果忘了 1样例可能刚好通过但遇到关键点形成链的情况会差 1。还可以说“如果你用关键点当根实现上心理负担小一点但统计是否保留边其实与根的选择无关只要用‘子树关键点数量在 0 和 k 之间’判断即可。”这样既准确又有经验。好的这个章节内容5.1 题意转化包含所有关键点最小连通子图5.2 核心观察一条边需要保留当且仅当它两侧都有关键点5.3 从边数到点数的转化为什么答案是 edges1-k5.4 完整代码与边界5.5 这个模型和虚树的联系我觉得不错。E题不写了在第6章可以提到“E 题属于另一类区间统计我没写出来就不硬凑”。现在需要确保每个H2字数足够。我会写得详细。现在开始正式输出。注意不要元信息。只用 Markdown。注意标题编号。我要确认没有主标题。直接从二级标题开始。开头段落不需要标题。最后一段个人体会可以放在第6章之后作为一个短段落不使用标题。因为系统说“结尾可选”。我可以让最后一个H2是第6章之后加一个短段落作为收尾。这个短段落不要用“综上”。由于文章需要至少5000字我写的量应该足够。每个H2平均约1000字六个H2能到6000字。加上开头。好。现在输出。 今天想认真复盘一下 Educational Codeforces Round 187 (Rated for Div.2)。这轮我是赛后 virtual 补的前四题恰好把“滑动窗口、交换排序、排列构造、树形统计”这四类 CF 里特别常见的考点串了一遍。A 题和 B 题都不难但 B 题稍微不留神就会往逆序对上想C 题属于“想通上界就完全白给”的构造D 题的主要坑在于把边数换算成点数时容易少加 1。下面按我实际写题顺序把每道题从读题到 AC 的完整思考链写出来代码统一用 C17。1. 这轮 A-D 到底在考什么四道题的知识点与难度曲线先说整体感受。这轮的难度分布并不是“线性上升”而是中间突然有个认知门槛A 题几乎是签到B 题很多人会被带偏C 题是个典型的构造D 题则是树形 DFS 的变体。如果只看题解会觉得都很常规但赛场上从 B 到 C 的切换很容易让人心态不稳。我按自己补题时的顺序把 A-D 拆成了四个独立模块A 题数组 最值 最短子段核心是滑动窗口/双指针的取舍B 题01 串交换排序核心是“任意交换”和“相邻交换”两种模型的区别C 题排列构造核心是先证明答案上界再顺着上界去构造D 题树上关键点连接核心是统计“最小连通点集”的边数再把边数换算成点数。这四题放在一起很适合 mid 到 high 1400 分段的选手练手因为它考的不是冷门算法而是“能不能一眼选对模型”。A 题如果一上来写二分和前缀最值也能过但会明显变慢B 题如果下意识当成逆序对做就会在当前这个模型里得到错误答案C 题没有先证明上界很容易构造出一半就卡住D 题如果不理解“一条边什么时候必须保留”很容易在树的边界样例上翻车。我补题时的时间大概是这样A 题看题加实现用了 5 分钟B 题因为一开始确实往逆序对上想了一下绕了 15 分钟C 题证明完上界之后 10 分钟写完D 题第一次提交 WA 在一个边界样例上最后检查发现是少加了 1。这个时间线其实很典型下面每道题的坑我都会单独指出来。2. A 题包含全局最小值和最大值的最短子段扫一遍就够了2.1 题意与第一反应题意很直接给定长度为 n 的数组 a找一个最短的连续子数组使得这个子数组里同时包含整个数组的最小值 mn 和最大值 mx输出最短长度。我第一反应是“这题是不是要二分长度”因为“最短长度”听起来很二分check(mid) 是否存在长度 mid 的子段同时含有 mn 和 mx。然后维护前缀中最值位置或者用滑动窗口判断。这样确实能做但复杂度会变成 O(n log n)作为 A 题小题大做了。实际上这个问题有一个更本质的性质如果某个子段 [l, r] 同时包含 mn 和 mx那么它内部一定有一个位置是 mn另一个位置是 mx。换句话说最优区间本质上就是从其中一个极值到另一个极值的一段再加上一些多余部分只会让长度变大。2.2 为什么枚举右端点能覆盖所有最优解我最后采用的方法是线性扫描同时维护两个变量lastMn最后一次出现 mn 的下标lastMx最后一次出现 mx 的下标。从左往右扫描到 i 时如果 a[i] 等于 mn那么以 i 为右端点、且同时包含两个极值的最短合法区间左端点必然是 lastMx长度为 i - lastMx 1同理如果 a[i] 等于 mx就用 i - lastMn 1 更新答案。为什么这样不会漏因为每个最优区间都有一个右端点。当扫描到这个右端点时如果它恰好是其中一个极值另一个极值在区间里最后一次出现的位置一定就是当前维护的 lastMn 或 lastMx。此时用它们计算出的长度不会比真正的最优区间更长。多更新几次没有关系答案只会更小不会漏掉。还有一种想法是“枚举左端点找右边最近的另一个极值”方向完全反过来也可以。但枚举右端点的好处是状态少不需要预处理 next 数组。2.3 完整代码与复杂度#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; vectorint a(n); int mn INT_MAX, mx INT_MIN; for (int i 0; i n; i) { cin a[i]; mn min(mn, a[i]); mx max(mx, a[i]); } if (mn mx) { cout 1 \n; continue; } int ans n; int lastMn -1, lastMx -1; for (int i 0; i n; i) { if (a[i] mn) { lastMn i; if (lastMx ! -1) ans min(ans, i - lastMx 1); } if (a[i] mx) { lastMx i; if (lastMn ! -1) ans min(ans, i - lastMn 1); } } cout ans \n; } return 0; }时间复杂度 O(n)空间复杂度 O(n)。其实可以只记录极值位置再扫一遍但读入时必须至少存一次数组所以 O(n) 空间无所谓。2.4 边界情况最容易翻车的是 mn mx也就是数组中所有数都一样。这时最短合法子段长度当然是 1直接特判。如果不特判代码里的if (a[i] mn)和if (a[i] mx)会同时触发虽然逻辑上也能算到 1但特判能让意图更清晰少一点边界讨论。另外一个细节是不要用if (a[i] mn)之后接else if (a[i] mx)。如果数组长度为 1或者 mn mx会漏掉更新。用两个独立的 if 更安全反正一个数不可能同时等于两个不同极值。3. B 题01 串任意交换的最小次数答案不是逆序对数3.1 题意给一个 01 串 s每次操作可以任选一对位置 i j要求 s[i] 1 且 s[j] 0然后把这两个字符交换。问最少多少次操作可以让所有 0 都排在所有 1 前面。注意这里的关键是“任意交换”不是“交换相邻位置”。我看到不少人在这个题上会条件反射想到逆序对因为“把 01 串排成 00...11”和冒泡排序模型太像了。但这题的每次操作是一次交换两个位置完全可以一次修好两个错位字符。3.2 关键观察错位成对一次交换修两个假设原串长度为 n其中有 c0 个 0。最终目标串是唯一的前 c0 个字符是 0后面全是 1因为 0 和 1 的总数量不会因为交换改变。把原串 s 和目标串 target 逐位比较统计有多少个位置不同记为 diff。由于两个串的 0 数量相同所以不同的位置一定是“原串是 1、目标是 0”和“原串是 0、目标是 1”两种位置成对出现diff 一定是偶数。一次合法操作交换一个 1 和一个 0如果选的恰好是这两种错位字符交换后这两个位置都归位了diff 直接减少 2。最理想情况下每次都选到这样的配对所以下界是 diff / 2。这个下界可以达到因为只要还存在错位就一定存在一个左边的错位 1 和一个右边的错位 0选它们交换即可。所以答案就是 diff / 2。3.3 和相邻交换的差别相邻交换模型下把 01 串变成全 0 在前全 1 在后答案等于逆序对数量也就是每个 1 后面 0 的个数之和。比如 1100 的逆序对数是 4相邻交换需要 4 次。但在任意交换模型下1100 的目标是 0011逐位比较位置 11 vs 0不同位置 21 vs 0不同位置 30 vs 1不同位置 40 vs 1不同diff 4答案 2。操作可以这样完成先交换位置 1 的 1 和位置 4 的 0得到 0101再交换位置 2 的 1 和位置 3 的 0得到 0011。所以“任意交换”和“相邻交换”从模型上就是两回事。做题时如果看到“选择任意两个位置交换”先别急着套逆序对如果看到“交换相邻元素”再考虑逆序对。3.4 代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; string s; cin n s; int cnt0 0; for (char c : s) { if (c 0) cnt0; } int diff 0; for (int i 0; i n; i) { char need (i cnt0 ? 0 : 1); if (s[i] ! need) diff; } cout diff / 2 \n; } return 0; }补充一个容易忽略的点构造 target 时不一定真的生成一个新字符串直接比较s[i]和(i cnt0 ? 0 : 1)就行。如果题目给的 n 很小当然无所谓但这个习惯在大数据下能省一个串的内存和一次构建时间。4. C 题排列相邻差集合最大化的构造先证明上界再谈做法4.1 上界是 n-1题意可以描述成构造一个 1 到 n 的排列 p使得所有相邻位置绝对差 |p[i] - p[i1]| 的不同取值数量尽量多输出任意一个达到最大值的排列。首先想清楚答案最多是多少。两个数在 1 到 n 之间差的绝对值最小是 1最大是 n-1。所以所有相邻差最多只有 n-1 种不同取值。如果你想达到最大值就必须让 1 到 n-1 这 n-1 个差值全部出现一次。这个上界虽然简单但它是整个题的基石。很多同学一上来直接随机排列去试或者用 DFS 回溯构造完全没必要。先证明上界再顺势设计构造题目会瞬间变简单。4.2 构造交替取两端我们要让相邻差分别等于 n-1, n-2, n-3, ..., 1。最容易想到的排列就是从两端交替取数p 1, n, 2, n-1, 3, n-2, ...以 n 6 为例1, 6, 2, 5, 3, 4相邻差分别是 5, 4, 3, 2, 1完美覆盖 1 到 n-1。为什么能覆盖因为每次交替从剩余区间两端取值两个数的距离正好等于当前剩余区间的长度。区间长度最开始是 n-1每次取完两个端点后剩余区间长度减少 1所以产生的差值正好从 n-1 一直降到 1。4.3 为什么证明上界之后构造就顺了如果先证明上界你就会知道目标不是“随便构造一个看起来花的排列”而是“让差值恰好是 n-1, n-2, ..., 1”。这个目标直接指向双指针。从一个空序列开始左边放 l 1右边放 r n先放 ll如果 l r放 rr--重复直到所有数放完。这种“从两头往中间夹”的模式在很多构造题里都出现过。它本质上是在保证相邻两个数之间的距离单调递减。4.4 代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; int l 1, r n; vectorint ans; while (l r) { ans.push_back(l); if (l r) ans.push_back(r--); } for (int i 0; i n; i) { cout ans[i] (i 1 n ? \n : ); } } return 0; }注意循环里push_back(l)和push_back(r--)的顺序。如果先放右端点再放左端点得到的差值顺序会变成小的开头但不影响覆盖 1 到 n-1不过实现时容易越界所以写成上面的形式最稳。4.5 一个小坑n 1 和 n 2 需要额外确认。n 1 时没有相邻差排列就是 [1]输出 1n 2 时排列 [1, 2] 或 [2, 1] 都只有一个差值 1。上面的双指针代码天然能处理这两种情况因为 ans 的长度严格等于 n。构造题里这种极小的 n 经常让人在边界上翻车建议每次写完构造都手动跑一遍 n1、n2、n3、n4。5. D 题树上关键点连通要补几个点最容易把边数错当点数5.1 题意转化这题大概是这样的模型给一棵 n 个点的树其中有 k 个点是“关键点”。每次操作可以额外“点亮”一个点点亮后这个点也变成关键点。目标是让所有关键点包括初始的和新点亮的在树上构成一个连通点集。问最少要点亮多少个点。换句话说树上本来有一些点需要连通但路径上可能缺中间点。因为树的边只能连接相邻点如果两个关键点之间的路径上有一个点没有被点亮那么这整段就不连通。所以答案等于“包含所有关键点的最小连通子图”的点数减去 k。这个最小连通子图其实就是一个简化版的虚树把不在任何关键点路径上的多余分支全砍掉只保留对连通性必要的点和边。在一棵树上求它不需要建虚树也不需要 LCA直接用一次 DFS 统计每条边是否需要保留。5.2 核心观察一条边需要保留当且仅当它两侧都有关键点任选一个点作为根做一次 DFS维护每个子树里有多少个关键点记为 sz[u]。对于一条边 u-v其中 v 是 u 的儿子如果 sz[v] 0 且 sz[v] k说明删掉这条边后关键点被分成了两边两边都有关键点。为了让所有关键点连通这条边必须被保留下来。这里有一个很容易被忽略但很重要的点这个条件和根选在哪里其实无关。不管树根选哪个点一条边两侧的关键点数量分布是固定的所以“是否保留”的判断结果也一样。有些题解喜欢说“选一个关键点当根”这样做实现起来心理负担小一点因为根本身就是最终连通子图的一部分但如果你任选根只要用同一个判定条件结果同样正确。5.3 从边数到点数的转化为什么答案是 edges 1 - k统计出所有需要保留的边数 edges 之后最小连通子图是一个由这些边组成的连通图。在一个连通无环图里边数为 edges点数一定是 edges 1。因为树的性质就是“点数 边数 1”去掉多余分支后依然满足。所以最小连通子图的总点数是 edges 1。其中已经有 k 个点是初始关键点不需要额外点亮需要新点亮的点数就是答案 (edges 1) - k这就是最容易出错的地方。很多人统计完 edges 后直接输出 edges忘了加 1。单独看公式觉得很简单但赛场上样例如果刚好是一个关键点已经连通的情况edges k - 1答案 0此时输出 edges 会得到 k - 1差了很远如果样例是“一条链上有三个关键点且中间隔一个点”edges 恰好等于答案反而能过。这就是边界样例能骗过你的原因。5.4 完整代码与边界情况#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorint isKey(n 1, 0); int root -1; for (int i 1; i n; i) { cin isKey[i]; if (isKey[i] root -1) root i; } vectorvectorint g(n 1); for (int i 0; i n - 1; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } long long edges 0; functionint(int, int) dfs [](int u, int fa) - int { int cnt isKey[u]; for (int v : g[u]) { if (v fa) continue; int sub dfs(v, u); if (sub 0 sub k) edges; cnt sub; } return cnt; }; if (root -1) { cout 0 \n; return 0; } dfs(root, -1); cout edges 1 - k \n; return 0; }边界情况k 1只有一个关键点最小连通子图就是它自己答案 0。代码里所有子树的 sz 都不可能等于 kedges 0输出 0 1 - 1 0正确。所有关键点已经连通且路径上没有缺口假设 k 3最小连通子图是链上三个点edges 2答案 2 1 - 3 0正确。三个关键点分布在三条分支上汇聚点不是关键点三条边都必须保留edges 3点数 4答案 4 - 3 1也就是要点亮汇聚点正确。5.5 和虚树的联系这个模型可以理解成虚树的一种最简形态。虚树通常会保留所有关键点以及它们的 LCA然后用排序和栈去压缩树结构本题因为只需要统计点数不需要输出具体哪些点所以一次 DFS 就够。如果以后遇到“树上最少点亮几个点让若干点连通”的题先想一个问题哪些边必须保留答案就是删除后会把关键点分成非空两部分的边。这是比建虚树更基本的直觉。6. 复盘清单这轮题最容易踩的四个坑和通用套路6.1 坑一B 题看到 01 串就想逆序对“把 01 串排序”这句话太容易让人联想到冒泡排序了。但题目里只要出现“任意选择两个位置交换”就不能直接用逆序对。判断标准是看操作对象是“相邻元素”还是“任意元素”。任意交换时一次操作可以同时修正两个错位所以答案等于错位对数的一半相邻交换时一次操作只修正一个单位才用逆序对。6.2 坑二C 题没有先证明上界就乱构造构造题最忌讳一上来就试。先问自己这个答案最多能是多少C 题里差值最大值是 n-1种类数上界天然是 n-1。一旦上界确认构造目标就变成“让 1 到 n-1 全部出现”。这时候交替取两端的方案几乎是唯一直觉。先证上界再构造是这类题的通用顺序。6.3 坑三D 题统计完边数直接输出 edges这个错误不显眼但很致命。答案要求的是“额外点亮多少个点”不是“保留多少条边”。从边数到点数要加 1再减去已有的 k 个关键点。把这两步合并成edges 1 - k之后最好在草稿纸上画一个三个关键点在一条链上的例子验算确认答案是 0 而不是 edges。6.4 坑四A 题忘记极值相等或 n 很小极值相等在所有数组题里都是常见特判。不要觉得这种特判多余它往往能拦住一半以上的 WA。另外n 1 和 n 2 在构造题、区间题里都很容易绕过实现养成“写完代码后先跑最小 n”的习惯能省很多罚时。6.5 赛后我能带走什么这轮 A-D 整体没有偏题怪题但每一道都在考“模型识别”A 题识别出最优区间和极值位置的关系B 题识别出任意交换和相邻交换的区别C 题识别出上界即目标D 题识别出边数和点数的换算。把这些模型沉淀成自己的 checklist比多刷十道类似的题更有用。这套题给我最深的印象不是哪一道题难而是每次卡住都是因为我没有先在草稿纸上写下“答案的形式应该是什么”。B 题如果先想清楚“一次交换能修好两处错位”根本不会绕到逆序对C 题如果先证明上界构造就是顺水推舟D 题如果先明确要求的是“点亮点数”就不会把 edges 直接输出。我现在补题的习惯是每道题先写下一句话结论再允许自己开编辑器。这个习惯帮我省下的调试时间比任何一个算法模板都多。