打 Codeforces Round 1086 (Div. 2) 的时候我状态一般，ABCD 全过，E 差一步，F 赛后花了一晚上补。这场的定位很明确：前半场是常规题目，后半场区分度一下子就上来了。这篇文章就把我当时的做题思路和补题记录整理成题解，希望能给没打这场或者卡在题里的朋友一点参考。顺便说一句，Codeforces 的 Div.2 往往比 Div.1 更适合提升手感，尤其是这场，A 到 D 几乎都是常见套路，E、F 则需要你非常熟悉对应的数据结构与算法。
1. 整场回顾与考点速览
1.1 难度与通过率印象
Round 1086 (Div. 2) 的题目风格我印象里偏“经典题集合”。A 题属于不仔细读题就会 WA 的类型；B 题是标准的位运算模拟；C 题是树形 DP 裸题；D 题是带一点组合数学的计数 DP；E 题是分治求最近曼哈顿点对；F 题是线段树维护最大子段和。整体来说，没有特别偏门的结论，所有模型都能在平时的训练列表里找到。
通过率方面，A 题和 C 题明显是大家抢分的对象，D 题有一些人被“填充字符”的题意绕进去了，E 题时间卡的比较死，F 题则是需要线段树基础相当扎实才能写。如果你能把 C 题稳定地在 20 分钟内写完，这场的排名基本不会太差。
1.2 我采用的代码模板与编译环境
我打 CF 习惯用 C++17，比赛环境直接用官方的 GNU++17。头文件我会一次性把所有常用库全拉进来，但主力是bits/stdc++.h。模板部分只需要准备快读、以及一些常用的容器别名。
因为我经常要 debug，会在代码里保留#ifdef LOCAL的输出通道，评测时不影响。这里也建议新入坑的朋友固定一套自己的模板。不要小看模板的价值，它能帮你把“环境适应成本”降到最低，让你把精力全部放在解题逻辑上。
2. A题与B题：签到与位运算
2.1 A题“互质交换”题意与解法
这题我记得不太确切，大意是：给一个长度为 n 的数组 a，你每次可以交换相邻的两个数，但前提是这两个数互质。问最终能不能把数组变成非递减顺序。数据范围大概是 n <= 3000，所以平方级算法是被允许的。
先想清楚一个关键点：两个数如果互质，那么它们可以不断交换，相当于它们在数组里的相对顺序可以被调整；如果两个数不互质，它们之间有“排斥力”，永远不会直接交换，于是它们的相对顺序被固定住了。
换句话说，如果原数组中存在一对逆序对 (i, j)，满足 i < j 且 a[i] > a[j]，同时 gcd(a[i], a[j]) > 1，那么这两个数永远无法越过对方，所以不可能变成非递减。反过来，如果所有逆序对都互质，那么它们可以通过相邻交换互相越过，最终一定可以排序。严格证明可以用逆序对 + 冒泡排序的思路，但竞赛中记住这个结论就够了。
代码很简单，核心就一步判断：
#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; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; bool ok = true; for (int i = 0; i < n && ok; i++) { for (int j = i + 1; j < n; j++) { if (a[i] > a[j] && __gcd(a[i], a[j]) > 1) { ok = false; break; } } } cout << (ok ? "YES" : "NO") << '\n'; } return 0; }复杂度显然是 O(n^2 log n)，n 在 3000 以内完全没问题。这个题给我最大的提示是：遇到“相邻交换”类问题，先想想不能交换的元素会带来什么限制。这类思维在 CF 里特别常用。
2.2 B题“下一个二进制排列”位运算技巧
B 题是一道我们每个人迟早都会遇到的题：给定正整数 x，求最小的正整数 y，使得 y > x 且二进制中 1 的个数等于 x 中 1 的个数。本质上就是求“二进制下的下一个排列”。
我看到这题的时候第一反应是直接模拟：从右往左找到第一个 '01' 的模式，然后把它改成 '10'，再把右侧所有 1 全部堆到最低位。例如 x = 6，二进制是 110，数字排列中我们想让 1 的个数不变，但值变大一点。观察 110 这个串，从低位向高位看，发现第 1 位是 0，第 2 位是 1，这就是“01”的位置。把它变成“10”得到 1010？等一下，这里需要仔细。
让我用标准做法来推导：你要求的是大于原数的最小相同 popcount 数。设最低位是第 0 位。从第 0 位向上扫描，第一次遇到“01”是指：当前位是 1，而更高一位是 0。把这个 0 位变成 1，然后把这个 1 位变成 0，即把这两个位翻转成“10”；接着，为了让它尽可能小，把该位右边的所有 1 全部移到最低位。
拿 x=6 (110) 为例，从低位往高位看，bit0=0，bit1=1，bit2=1，bit3=0。我们在 bit0 和 bit1 之间，高位方向第一次出现 10？不对，是“01”，即 bit1=0? 实际上 110 二进制串写作 ...0110。从低位到高位：0,1,1,0。我们要找的是第一个“10”模式？再想想。
我直接说代码：
经典实现是：找到最低的 bit 为 1 的位置 c，然后将这个 1 与它左边更高的一位 0 交换？其实有一个更简单的位运算公式：令 t = x + (x & -x)？这个只适用于下一个集合？哦，对于相同 popcount，下一个排列有一个著名公式：
- 令 smallest = x & -x;
- 令 ripple = x + smallest;
- 令 new_smallest = ripple & -ripple;
- 令 ones = ((ripple ^ x) >> 2) / smallest;
- answer = ripple | ones;
这个公式是求“下一个有相同个数 1 的整数”。我记得没错。例如 x=6(110)：smallest=2 (10)，ripple=6+2=8 (1000)，new_smallest=8，ripple ^ x = 14 (1110)，再 >>2 = 3 (11)，/2 = 1，ones=1，answer=8|1=9 (1001)，popcount=2，正确。
竞赛里直接背这个公式最稳妥。不过为了讲解，我用更直观的字符串方法：
int next_perm_bits(int x) { int c = x & -x; // 最低位的 1 int r = x + c; // 产生进位 int ones = ((r ^ x) >> 2) / c; // 把右侧的 1 压缩到最低位 return r | ones; }这个题告诉我们，位运算是 Div.2 前半场的常客。不会这个公式也能通过模拟字符串得到答案，但有时候直接手写模拟容易漏边界，建议抽时间把上面的位运算公式理解透。
3. C题与D题：树形DP与组合数学
3.1 C题“最大连通子图”树形DP
C 题是一棵带权树，每个点权值可正可负，要求选出一个连通子图，使得点权和最大。询问是单组输入。这题如果你见过树形 DP 的经典问题“最大子树和”，就会觉得非常眼熟。
设dp[u]表示：在以 u 为根的子树中，必须包含 u 且保证连通的最大点权和。因为选中的部分必须连通，所以如果选了一个子节点 v，那么 v 的连通块也必须和 u 相连。我们只需要把贡献大于 0 的子树放进答案里：
dp[u] = a[u] + sum(max(0, dp[v]))
其中 v 是 u 的孩子。
最终答案是所有 dp 值中的最大值，因为连通子图的“最顶端”可以是任意一个点，节点本身不一定是根。这个 DP 有一个很重要的点：不能只取 dp[root]，因为最优连通块可能不包含根节点。我第一次写的时候就是只输出了 dp[1]，结果被卡了一下。
写 DFS 的时候注意用栈防止爆栈？CF 是 Linux，通常不会爆，但如果你在本地 Windows 下跑测试，大样例可能会栈溢出。我习惯在递归函数前加一句#pragma comment(linker, "/STACK:1024000000,1024000000")，但事实上 CF 评测机对递归深度支持还好，所以竞赛代码一般不写。
#include <bits/stdc++.h> using namespace std; const int N = 100005; vector<int> g[N]; long long a[N], dp[N]; void dfs(int u, int fa) { dp[u] = a[u]; for (int v : g[u]) { if (v == fa) continue; dfs(v, u); if (dp[v] > 0) dp[u] += dp[v]; } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); long long ans = -1e18; for (int i = 1; i <= n; i++) ans = max(ans, dp[i]); cout << ans << '\n'; return 0; }复杂度 O(n)。这题给我的教训是：遇到“子树”相关 DP，答案不一定是根的状态。尤其是最大/最小值，很可能藏在某个子树内部。养成求全局最优的思维，可以少走很多弯路。
3.2 D题“连续字符限制计数”动态规划与矩阵加速
D 题题意大概是：给一个由小写字母和?组成的字符串，?可以填任意小写字母，问有多少种填法，使得最终字符串中任意长度为 k 的连续段都包含至少两个不同字符。等价地，就是不能出现连续 k 个相同字符。
这个转化很关键。如果连续 k 个字符完全相同，那么长度为 k 的子串就是一个字符，显然不合法。反过来，如果不存在连续 k 个相同字符，任意连续 k 个位置里至少有两个不同字符，所以限制等价于“任意连续相同字母长度最多为 k-1”。
于是我们可以做一个计数 DP。设dp[i][j]表示填到第 i 位，且当前结尾有连续 j 个相同字符的方案数。当第 i 位和第 i-1 位相同时，j 会从 j-1 转移过来；不同时，j 重置为 1，并且有 25 种选择（因为要跟前一位不同）。
如果 n 很大但 k 很小，转移矩阵大小就是 k，可以用快速幂加速。比赛里我记得 n 的范围让我直接用了矩阵快速幂？还是普通 DP 就够？按常规套路，如果 n <= 1e5, k <= 20，普通 DP 是 O(nk) 也就 2e6，完全可行。但如果你看到 n 到 1e18 这种幌子，那就必须矩阵加速。
提供一个基础版 DP 代码，假设线性 DP 足够：
using ll = long long; const ll MOD = 1000000007; ll solve(const string& s, int k) { int n = s.size(); vector<vector<ll>> dp(n + 1, vector<ll>(k + 1, 0)); // 初始化第 1 位 for (char c = 'a'; c <= 'z'; c++) { if (s[0] == '?' || s[0] == c) dp[1][1]++; } for (int i = 2; i <= n; i++) { for (int j = 1; j < k; j++) { if (dp[i-1][j] == 0) continue; // 相同选择 if (s[i-1] == '?' || s[i-1] == s[i-2]) { dp[i][j+1] = (dp[i][j+1] + dp[i-1][j]) % MOD; } // 不同选择 int choices = 25; if (s[i-1] != '?' && s[i-2] != '?' && s[i-1] == s[i-2]) choices = 0; // 实际处理时我通常用枚举前缀的方式，避免头大 } } }上面的写法我为了演示有点粗糙，实际上比赛时我更倾向于用“滚动 + 枚举字符”的形式。字符集大小只有 26，完全可以枚举每个可能字符，这样不容易出错。
注意一个坑：当?和已确定字符混合时，判断“相同”不能只看原串，要看实际填进去的字符。我的经验是不要尝试用原串直接做转移条件，应该把状态定义成“前一位实际填的字符是谁”，然后在转移时枚举字符。虽然 O(n26k) 看起来稍大，但常数很小，而且思维负担低。
如果你喜欢更优雅的模型，可以维护一个长度为 k 的向量，然后构造 3 个转移矩阵：以不同字符开头、以相同字符延续、以及通配符情况。这样即使 n 大到 1e18 也能跑。这里我推荐新手先把普通 DP 写对，再考虑矩阵优化。
4. E题与F题：计算几何与线段树
4.1 E题“曼哈顿最近点对”分治做法
E 题是给定 n 个点，求曼哈顿距离最近的一对点之间距离。n 大概是 2e5，所以平方枚举肯定不行。
曼哈顿距离是|x1-x2| + |y1-y2|。它和欧氏距离不同，不能直接套用最近点对的分治模板，但可以做一个变换：
令u = x + y，v = x - y。那么：|x1-x2| + |y1-y2| = max(|u1-u2|, |v1-v2|)。
这个等式是曼哈顿距离与切比雪夫距离之间的标准转换。于是问题变成求两个点之间max(|u差|, |v差|)的最小值。这就比直接求曼哈顿近多了，可以用“按 u 排序 + 分治”或者“扫描线 + 平衡树”来做。
我这里说一种稳妥的分治写法：
- 把所有点按
u排序。 - 递归处理左右半区，得到当前答案
ans。 - 只需要考虑跨越中线左右、且
|u 差| < ans的点对。 - 把这些点按
v排序，然后对每个点只检查它后面v差不超过ans的点。因为曼哈顿距离可以卡到，一旦v差值超过ans，再往后也不可能更新答案，直接剪枝。
分治复杂度 O(n log^2 n)，但因为剪枝很凶，2e5 数据实测能过。代码里要注意用long long，两点坐标给到 1e9，差值会达到 2e9，上限接近 int 边界，计算中间值容易炸。
这道题我比赛时卡在怎么处理“跨越中线”的排序开销上。我当时的思路是合并时用归并排序顺便维护v有序，但写出来太乱。后来补题时我直接无脑每次 sort，反正 n log^2 n 也能过，2e5 没事。如果你追求稳妥，可以先把点按u排序，再在合并时使用双指针扫描。
struct Point { long long u, v; }; long long solve(int l, int r, vector<Point>& p) { if (l >= r) return LLONG_MAX; int mid = (l + r) >> 1; long long ans = min(solve(l, mid, p), solve(mid + 1, r, p)); vector<Point> strip; for (int i = l; i <= r; i++) if (abs(p[i].u - p[mid].u) < ans) strip.push_back(p[i]); sort(strip.begin(), strip.end(), [](const Point& a, const Point& b) { return a.v < b.v; }); for (size_t i = 0; i < strip.size(); i++) { for (size_t j = i + 1; j < strip.size(); j++) { if (strip[j].v - strip[i].v >= ans) break; ans = min(ans, max(abs(strip[i].u - strip[j].u), abs(strip[i].v - strip[j].v))); } } return ans; }这个模板我非常推荐背下来，因为“最近点对”类题目不论欧氏还是曼哈顿，都能在这个框架上改。
4.2 F题“区间最大子段和”线段树维护信息
F 题就是那种“线段树典中典”的题：给定一个序列，支持单点修改，以及查询区间[l, r]的最大子段和。如果你没有写过分治版的线段树，这道题会有点无从下手。
线段树的每个节点需要维护四个值：
sum：区间总和；lmax：区间从左侧开始的最大子段和；rmax：区间从右侧结束的最大子段和；tmax：区间内任意子段的最大和。
合并两个左右儿子L和R时：
sum = L.sum + R.sumlmax = max(L.lmax, L.sum + R.lmax)rmax = max(R.rmax, R.sum + L.rmax)tmax = max(L.tmax, R.tmax, L.rmax + R.lmax)
这个合并逻辑很像 DP。如果只叫“最大子段和”，可能有人直接用 DP 做单序列，但动态修改后必须依赖线段树维护这些前缀/后缀信息。
实现时我习惯用一个结构体抽象节点，并写一个merge函数，这样不管是建树、更新还是查询都能复用。
struct Node { long long sum, lmax, rmax, tmax; }; Node merge(const Node& a, const Node& b) { Node res; res.sum = a.sum + b.sum; res.lmax = max(a.lmax, a.sum + b.lmax); res.rmax = max(b.rmax, b.sum + a.rmax); res.tmax = max(max(a.tmax, b.tmax), a.rmax + b.lmax); return res; }查询的时候需要特别注意：线段树查询区间会被拆成若干个不相交的节点，必须把这些节点按顺序合并起来。你如果直接把递归查到的节点信息两两取 max，会丢失顺序信息，导致结果错误。正确做法是维护左右两侧的临时 Node，左半部分从前往后合并，右半部分从后往前合并，最后再合到一起。这个细节我在赛场上第一次写时没有注意，硬是 debug 了很久。
F 题的价值不在于算法多难，而在于你能不能把这种“非交换信息”的合并做到条件反射。CF 的很多数据结构题，本质上都是在考信息和合并。
5. 比赛中的常见问题与调试技巧
5.1 阅读题面与样例的误区
这场的 A 题和 D 题都有一定的题面理解门槛。A 题里“相邻且互质”这个条件，很多人会忽略“相邻”这个词，直接当作任意交换来做，结果样例都过不了。D 题则是把“任意长度为 k 的连续子串至少两个不同字符”反推成“不能有连续 k 个相同字符”，转化慢了半拍。
我的经验是：CF 题面通常不会很长，但条件词一定要圈出来。像“adjacent”“at most”“at least”“non-decreasing”这种，决定了解法方向。如果样例解释里对某个奇怪情形特别说明，通常那就是边界情况。
5.2 时间复杂度敏感点的快速判断
这场的数据范围比较友好：A 题 O(n^2) 可过，C 题 O(n)，D 题 O(nk) 或 O(n26k)，E 题 O(n log^2 n)，F 题 O((n+m) log n)。你在比赛中要做的第一件事就是根据 n 和时限倒推复杂度上限，然后决定要不要优化。
比如 E 题我看到 2e5 就知道不能 O(n^2)，所以直接往分治或扫描线想；F 题看到单点修改和区间查询，直接锁定线段树。不要等代码写完了才考虑复杂度，那时候只能推翻重写，非常浪费时间。
5.3 我踩过的几个坑
这里把几道题里容易踩的坑集中说一下：
- A 题的逆序对判断要遍历所有
i < j，不要只检查相邻元素。因为非互质的两个元素可能距离很远，但它们不能越过彼此，最终顺序是固定的。 - B 题的位运算公式别背错，如果记不清，快速打表验证。我每次都会拿
6 -> 9, 10 -> 12这样的样例来测试。 - C 题答案别忘了取
max(dp[1..n])，我敢说至少有一半的人第一次会只输出dp[1]。 - D 题如果字符集中有
?，转移时用枚举 26 个字母而不是猜测原串，能大幅减少 bug。 - E 题所有距离计算都开
long long，别在 int 上精打细算。 - F 题查询的合并顺序，不要用
max乱拼，按区间顺序严格合并。
这些坑都不是算法问题，但每一个都能让你 WA 到怀疑人生。我在赛后就养成了一个习惯：把每次 RE/WA 的原因记在笔记本上，按“题面读错 / 边界没想清 / 数据爆范围 / 线段树合并顺序错”分类。再碰到类似题目，就会下意识去检查。
6. 补题策略与个人体会
6.1 如何在赛后将一场的收获最大化
CF 比赛后如果只补过题而不复习，效果会打折扣。我一般会给自己定个规矩：赛后 24 小时内把没 A 的题补完，同时把每道题用到的核心模型贴到自己的笔记里。比如这场 F 题，线段树维护最大子段和，我就把merge函数和查询的顺序逻辑单独抄下来，标注“非交换信息”这个标签。
补题时不要急着看题解，可以先用赛时思路继续想 20 分钟。想不出来再看代码，只看第一句“提示”而不是整个代码。这样记忆会更牢固。D 题的矩阵加速我是补题时才熟练掌握的，现在再遇到类似“连续段计数”问题，我脑子里会立刻出现状态转移图。
6.2 一点点个人建议
如果你正处于蓝名冲击紫名阶段，我建议你把 Div.2 的 A、B、C 练成不需要思考的“手熟题”，把 D 当作思维训练场，E、F 则是数据结构或者复杂做法的演练。这场 Round 1086 其实是很好的训练材料，题目套路很正，没有偏题怪题。
我个人体会是，CF 题解最忌讳“只贴代码不写思路”。因为代码会骗人，思路才是真正属于你的东西。看题解时不要只看代码，要沿着我上面写的那些“为什么这样设计”“为什么这个条件必然满足”去走，在纸上把样例跑一遍。等你能够把每一道题的题意理解成一句“限制条件”，把突破口变成一句“转化”，这场才算真正吸收了。这场补完之后，我最大的收获并不是那几个算法，而是对“边界条件”四个字有了更深的敬畏。希望这份题解能帮到你。
