尧图网页设计 
昨晚把 Educational Round 188 从 A 到 F 完整打了一遍说实话这场的梯度设计得很舒服前四题是典型的教育场风格——考察的是“能不能把问题转化到已知模型上”而不是堆冷门算法后面两题认真起来E 是组合计数的容斥F 是单调栈拆贡献的经典套路。整体打下来最大的感受是这场的题特别适合拿来练“为什么会想到这样做”的思维链路。下面我把每一题的完整复盘写出来包括我现场是怎么一步步试错、最后敲定方案的以及代码实现和几个容易踩的边界坑。1. A题Polycarp and Snakes——一个“看似复杂”的网格验证题1.1 题目说的到底是什么Polycarp 在一条水平展示线上画了若干条蛇。每条蛇用一个小写字母表示身体是一段连续的格子。规则是先画编号小的蛇再画编号大的蛇后面的蛇会覆盖在之前的蛇上面。所以如果字母a和b同时出现且a b那么a所在的区间必须完全被b所在的区间包含。网格中给定的字符矩阵.表示空格其他字符表示该位置被某条蛇覆盖。换句话说题面可以理解成给定一个n x m的矩阵判断是否能由一组满足“按字母序递增的区间互相包含”的蛇叠加而成。1.2 先想清楚要验证哪些条件这题 A 题难就难在条件比较多现场很容易只检查了部分条件就交然后 WA 一发。我梳理了一下其实要检查的无非是四点所有非.的字符必须在同一行。因为题目说了蛇都画在一条水平展示线上如果出现了两行都有字母那肯定不合法。出现过的字符集合必须是a开始的连续前缀。比如出现了a、c但没有b这就不合法。每个字母的格子必须连续也就是形成一段完整的区间中间不能有空洞。按字母序从小到大后一个字母的区间必须包含前一个字母的区间。这些条件看着多但代码写起来很直接。我们扫描一遍矩阵对每个字母记录它出现的最左列、最右列、所在行以及出现次数。只要出现次数等于R - L 1就说明这段是连续的。1.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, m; cin n m; vectorstring g(n); for (int i 0; i n; i) cin g[i]; vectorint L(26, m), R(26, -1), row(26, -1), cnt(26, 0); int mx -1; for (int i 0; i n; i) { for (int j 0; j m; j) { if (g[i][j] .) continue; int c g[i][j] - a; cnt[c]; L[c] min(L[c], j); R[c] max(R[c], j); row[c] i; mx max(mx, c); } } if (mx -1) { cout YES\n; continue; } bool ok true; // 检查是否从 a 开始连续出现 for (int c 0; c mx; c) { if (cnt[c] 0) { ok false; break; } if (cnt[c] ! R[c] - L[c] 1) { ok false; break; } } // 检查是否都在同一行且区间按字母序互相包含 if (ok) { for (int c 1; c mx; c) { if (row[c] ! row[0]) { ok false; break; } if (L[c] L[c - 1] || R[c] R[c - 1]) { ok false; break; } } } cout (ok ? YES : NO) \n; } return 0; }1.4 容易漏掉的三个边界这题我现场第一次提交就栽在边界上。三个容易漏的点第一矩阵里完全没有字母的情况。这时候mx -1直接输出YES因为“画了零条合法蛇”也是合法的。这个边界一开始很容易忽略。第二区间包含关系的传递性。因为我们保证了字母集合是连续前缀所以只需要检查相邻两个字母的包含关系即可。a被b包含b被c包含自然a就被c包含了不需要额外检查。第三行不相同的情况。有些实现会只检查区间连续性而忽略“所有蛇必须在同一行”这个约束这就会导致样例里的特殊情况判断错。所有非空格的行号必须一致这一步不能省。A 题的教训是遇到这种“多条件验证”的题最靠谱的做法是先把条件一条条列出来再逐条实现而不是一边写一边想。这也对后面几题有帮助。2. B题排序 双指针的贪心直觉为什么大的必须去配小的2.1 题意与一个错误的直觉B 题是一道典型的“配对”题给定n个整数和一个上限k每次操作可以选择两个下标i、j如果a[i] a[j] k就把这两个数从数组中删除。问最多能执行多少次这样的操作。很多人的第一反应是每次找最小的数和某个数配对这样能配对的数量最多。这句“找最小的数”没错但“某个数”怎么选才是关键。我现场一开始想的是用哈希表或者桶去记录每个数出现的次数然后从小到大枚举值域看有没有对应的数能和它相加不超过k。这个思路在值域小的时候能写但一旦n到2e5值域也到2e5哈希表写法虽然能过却完全没有体现出这道题想考的贪心。实际上这题的最佳做法是排序后双指针。2.2 为什么双指针是对的排序之后我们维护左右两个指针l 0r n - 1。每次看a[l] a[r]如果小于等于k说明当前最小的元素可以和当前最大的元素配对直接配对成功l、r--答案加 1。如果大于k说明当前最大的元素太大了它跟数组里最小的元素都配不了那它跟谁也都配不了只能把它丢掉r--。这个贪心为什么正确关键在第二条。当一个元素大到连当前全局最小值都配不了那么在有序数组里它和其他任何元素的和只会更大所以这个元素不可能参与任何配对直接丢弃不会损失最优解。而如果最小元素和最大元素能配对那我们就要“用最小的去配最大的”因为最小元素是“最容易被配对”的资源把它用在一个最难的对手上剩下的数之间配对的余地最大反过来如果让最小元素去配一个中等大小的数最大元素反而可能被浪费掉。排序后 [l] ... [r] 若 a[l] a[r] k配对 l 和 r 否则r--因为 a[r] 与任何 a[l..r] 中的元素相加都 k2.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, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); int l 0, r n - 1, ans 0; while (l r) { if (a[l] a[r] k) { ans; l; r--; } else { r--; } } cout ans \n; } return 0; }2.4 这题的思维价值B 题的思维价值不在于代码而在于“配对”类问题的通用思考方式。以后看到“选两个数删除”“选两个点连边”“选两个人组队”这一类问题第一反应就应该是能不能排序排序之后有没有单调性如果有单调性双指针通常就是最优解。另外这题也提醒我们不要一上来就想着用值域桶、哈希表、平衡树去硬模拟先想想排序能不能让问题变简单。很多 CF 前两题的 B 题正解往往就是很朴素的排序加扫描但前提是你得具备“排序之后信息变整齐”的敏感度。3. C题滑动窗口的经典容斥——如何统计“恰好K个不同元素”的子数组3.1 题面与核心转化C 题题目是给一个长度为n的数组问有多少个连续子数组其中不同的元素个数恰好等于k。如果直接枚举左端点然后向右扩展用 set 维护不同元素个数复杂度是O(n^2)肯定不行。但如果我们把问题稍微改一下问有多少个连续子数组不同元素个数不超过 k这个问题就能用滑动窗口在O(n)内解决。于是“恰好等于 k”就转化成了f(k) 不同元素个数不超过 k 的子数组数 答案 f(k) - f(k - 1)这个转化的思路非常关键它是一个通用的容斥技巧“恰好”比“至多”难算那就先算“至多”再相减。3.2 滑动窗口的实现细节怎么统计“不同元素个数不超过 k”的子数组数量呢经典做法是枚举右端点r维护当前窗口[l, r]内不同元素的个数。如果个数大于k就不断移动左端点l直到个数重新小于等于k。这里有个容易想不明白的点为什么当右端点为r时合法的子数组数量是r - l 1因为固定右端点r之后左端点l越往左子数组越长包含的不同元素个数只可能越多。所以如果[l, r]合法那么所有以r为右端点、左端点在[l, r]范围内的子数组都是合法的。这些子数组一共有r - l 1个。累加每个右端点对应的合法数量就是总数。用cnt数组记录窗口内每个数字出现的次数用distinct记录当前窗口内有多少个不同的数字。#include bits/stdc.h using namespace std; long long countAtMostK(const vectorint a, int k) { if (k 0) return 0; int n (int)a.size(); vectorint cnt(200005, 0); int l 0, distinct 0; long long ans 0; for (int r 0; r n; r) { if (cnt[a[r]] 0) distinct; cnt[a[r]]; while (distinct k) { cnt[a[l]]--; if (cnt[a[l]] 0) distinct--; l; } ans r - l 1; } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; long long ans countAtMostK(a, k) - countAtMostK(a, k - 1); cout ans \n; return 0; }3.3 两个注意点第一countAtMostK里的cnt数组大小。如果题目没有给出值域最好的做法是先对数组做离散化或者用unordered_map。但如果值域在可接受范围内直接用数组是最快的。我这里写的是 200005实际使用时要根据题目数据范围调整别直接照抄。第二k - 1小于 0 的情况。如果k 0那么要统计的是“不同元素个数不超过 0”的子数组数也就是空区间但子数组通常非空所以答案是 0。代码里countAtMostK(a, k - 1)会传入-1需要单独判断并返回 0。C 题的核心收获是滑动窗口不是只能求最长/最短区间它也可以用来统计满足某种性质的区间数量。配合“恰好转至多”的容斥能解决一大类统计问题。4. D题选择问题——区间覆盖的最小代价与线段树优化DP4.1 题目模型D 题是经典的区间覆盖问题。给定n个区间每个区间是[l_i, r_i]选择它的代价是c_i。现在要用这些区间覆盖[1, m]上的所有整数点求最小总代价。如果无法完整覆盖输出-1。这个题的“选择”二字实际上是在说区间摆在那里你可以选也可以不选目标是让选出来的区间并集覆盖整个范围。这就是一个典型的“决策类 DP”问题。4.2 朴素 DP设dp[i]表示覆盖[1, i]的最小代价。初始时dp[0] 0其余为无穷大。当我们选择区间[l, r]时如果前面已经覆盖到了l - 1那么接上这个区间后就能覆盖到r。所以转移是dp[r] min(dp[r], min(dp[x]) c) 其中 x 属于 [l - 1, r - 1]这里x只要至少等于l - 1就行因为区间[l, r]本身能覆盖从l到r的所有点前面覆盖到x l - 1的话中间有空隙接不上。所以朴素做法是对每个区间枚举x从l - 1到r - 1找一个最小的dp[x]加c更新dp[r]。复杂度是O(n^2)显然不行。4.3 用线段树优化观察转移式子我们要的是一个区间内的dp最小值而且 DP 是顺序更新的按r从小到大更新。这正好可以用线段树维护整个dp数组的前缀最小值。具体实现先把区间按右端点r从小到大排序。初始化线段树所有位置值设为无穷大dp[0] 0单点更新到线段树。遍历每个区间[l, r, c]查询[l - 1, r - 1]范围内的最小值best。如果best是无穷大说明这个区间接不上任何已覆盖的前缀跳过。否则用best c尝试更新dp[r]也就是在线段树的r位置做单点取最小值。最终答案是dp[m]如果无穷大则输出-1。注意几个细节区间端点都是整数如果m范围很大比如1e9需要先离散化所有端点如果区间端点从 1 开始那么dp[0]对应一个虚拟的“起点”。我写的时候习惯让下标从 1 开始这样转移时查询[l - 1, r - 1]更自然。#include bits/stdc.h using namespace std; const long long INF 4e18; struct SegmentTree { int n; vectorlong long tree; SegmentTree(int n) : n(n), tree(4 * n 4, INF) {} void update(int p, long long val, int node, int l, int r) { if (l r) { tree[node] min(tree[node], val); return; } int mid (l r) / 2; if (p mid) update(p, val, node * 2, l, mid); else update(p, val, node * 2 1, mid 1, r); tree[node] min(tree[node * 2], tree[node * 2 1]); } long long query(int ql, int qr, int node, int l, int r) { if (ql r || qr l) return INF; if (ql l r qr) return tree[node]; int mid (l r) / 2; return min(query(ql, qr, node * 2, l, mid), query(ql, qr, node * 2 1, mid 1, r)); } }; struct Node { int l, r; long long c; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorNode segs(n); for (int i 0; i n; i) { cin segs[i].l segs[i].r segs[i].c; } sort(segs.begin(), segs.end(), [](const Node A, const Node B) { return A.r B.r; }); SegmentTree st(m 1); st.update(0, 0, 1, 0, m); for (auto s : segs) { if (s.l m) continue; int ql max(0, s.l - 1); int qr min(m, s.r - 1); long long best st.query(ql, qr, 1, 0, m); if (best ! INF) { st.update(s.r, best s.c, 1, 0, m); } } long long ans st.query(m, m, 1, 0, m); cout (ans INF ? -1 : ans) \n; return 0; }4.4 为什么线段树优化是对的这个 DP 的转移来源是一个区间的dp最小值而不是单个点所以不能用简单的前缀最小值数组来维护因为我们要的到底是哪一段取决于新区间的左端点。线段树能灵活地支持“区间查最小值 单点更新”正好适配这个需求。另外按右端点排序保证了我们处理区间时之前所有可能更新到dp[x]的区间都已经处理过了DP 的无后效性就满足了。D 题告诉我们要对“区间类 DP”的优化敏感当转移方程变成dp[i] min(dp[j]) cost且j在某个范围内时线段树/树状数组优化往往就是下一步的方向。5. E题棋盘染色的二项式反演——容斥也能解计数题5.1 题面E 题是一个n x m的棋盘每个格子可以染成黑色或白色问有多少种染色方案使得每一行至少有一个黑色格子并且每一列至少有一个黑色格子。注意这里的限制条件里行和列都是“至少一个黑格”而不是“恰好”。这种“至少”型的计数问题很容易让人想到容斥我们统计“某些行/列不合法”的方案数再通过容斥把它们去掉。5.2 容斥公式推导我们设“坏行”表示这一行没有黑格“坏列”表示这一列没有黑格。题目要求的就是坏行数为 0 且坏列数为 0 的方案数。记F(i, j)表示至少指定某i行和某j列是坏的方案数。这里“指定”的意思是我们选择i行让它们必须全白选择j列让它们必须全白剩下的格子随意填。那么在n行中有i行坏、m列中有j列坏的情况下剩下的格子数量是(n - i) * (m - j)每个格子可以黑可以白所以方案数是F(i, j) C(n, i) * C(m, j) * 2^((n - i) * (m - j))然后容斥坏行数和坏列数都为 0 的方案数等于答案 Σ_{i0}^{n} Σ_{j0}^{m} (-1)^(ij) * C(n, i) * C(m, j) * 2^((n - i) * (m - j))这里(-1)^(ij)是因为我们对i个坏行和j个坏列做容斥所以符号由ij的奇偶决定。5.3 代码实现细节#include bits/stdc.h using namespace std; const long long MOD 1e9 7; long long qpow(long long base, long long exp) { long long res 1; while (exp) { if (exp 1) res res * base % MOD; base base * base % MOD; exp 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; int lim max(n, m); vectorlong long fact(lim 1), invFact(lim 1); fact[0] 1; for (int i 1; i lim; i) fact[i] fact[i - 1] * i % MOD; invFact[lim] qpow(fact[lim], MOD - 2); for (int i lim; i 1; i--) invFact[i - 1] invFact[i] * i % MOD; auto C [](int a, int b) - long long { if (b 0 || b a) return 0; return fact[a] * invFact[b] % MOD * invFact[a - b] % MOD; }; long long ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { long long term C(n, i) * C(m, j) % MOD; term term * qpow(2, 1LL * (n - i) * (m - j)) % MOD; if ((i j) 1) { ans (ans - term MOD) % MOD; } else { ans (ans term) % MOD; } } } cout ans \n; return 0; }5.4 指数范围与取模细节这个题第一个容易错的地方是2^((n - i) * (m - j))的指数可能很大最大是n * m如果n, m都到1e5n*m可能到1e10所以不能直接用数组预处理 2 的幂必须用快速幂或者预处理pow2到n*m前提是n*m在可接受范围。第二个容易错的地方是容斥取模时减法要加MOD再取模避免负数。我见过很多选手在负数取模上 WA 到怀疑人生这题因为项数多尤其要小心。第三个点是如果n, m都很大O(nm)的二重循环可能会超时。这题如果数据范围到1e5需要用生成函数或者 NTT 来做但作为 E 题O(nm)的版本其实已经足够用来理解容斥的核心思想。比赛里碰到这类题先确认数据范围再决定要不要降复杂度。E 题给我的最大感受是组合计数题里“至少”永远比“恰好”难算而容斥就是连接两者的桥。遇到“至少”不要怕先把反面条件设成坏事件然后逐项容斥通常能把式子写出来。6. F题所有子区间的“最大-最小-长度”贡献——单调栈拆贡献6.1 题目与公式化简F 题题目给定一个长度为n的排列p定义区间[l, r]的价值为max(p[l..r]) - min(p[l..r]) - (r - l)求所有子区间的价值之和。如果直接枚举所有区间复杂度是O(n^2)。必须拆贡献。设S_max为所有子区间最大值之和S_min为所有子区间最小值之和S_len为所有子区间长度之和那么总价值是S_max - S_min - (S_len - 区间个数)因为每个区间的(r - l)就等于长度减 1。区间长度之和可以直接算长度为 1 的区间有n个长度为 2 的有n-1个...所以S_len Σ_{k1}^{n} k * (n - k 1) n*(n1)*(n2)/6区间个数是n*(n1)/2所以Σ(r - l) S_len - n*(n1)/2 n*(n-1)*(n1)/6于是题目变成了求S_max和S_min。6.2 单调栈的核心思路S_max的计算是经典题对每个位置i我们找到p[i]作为最大值时能覆盖哪些子区间。问题是如果两个相等的最大值同时出现在一个区间里我们只应该计算一次。所以某个位置i作为最大值时我们要规定它是这个区间里“最左的最大值”或“最右的最大值”这样才不会重复计数。我用的是“左边严格大于右边大于等于”的规则L[i]左边第一个大于p[i]的位置不含默认-1R[i]右边第一个大于等于p[i]的位置不含默认n这样p[i]作为“严格最大”能覆盖的所有子区间的左端点在(L[i], i]之间右端点在[i, R[i])之间。数量是(i - L[i]) * (R[i] - i)。对于S_min同理L[i]左边第一个小于p[i]的位置R[i]右边第一个小于等于p[i]的位置这样保证每个区间的最小值只被最左的最小值位置统计一次。6.3 代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint L(n), R(n); stackint st; // 计算 S_max左边第一个大于右边第一个大于等于 for (int i 0; i n; i) { while (!st.empty() a[st.top()] a[i]) st.pop(); L[i] st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i n - 1; i 0; i--) { while (!st.empty() a[st.top()] a[i]) st.pop(); R[i] st.empty() ? n : st.top(); st.push(i); } long long sumMax 0; for (int i 0; i n; i) { sumMax 1LL * a[i] * (i - L[i]) * (R[i] - i); } // 计算 S_min左边第一个小于右边第一个小于等于 while (!st.empty()) st.pop(); for (int i 0; i n; i) { while (!st.empty() a[st.top()] a[i]) st.pop(); L[i] st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i n - 1; i Codeforces Round 188 A-F 完整复盘：从贪心到单调栈的思维进阶
昨晚把 Educational Round 188 从 A 到 F 完整打了一遍说实话这场的梯度设计得很舒服前四题是典型的教育场风格——考察的是“能不能把问题转化到已知模型上”而不是堆冷门算法后面两题认真起来E 是组合计数的容斥F 是单调栈拆贡献的经典套路。整体打下来最大的感受是这场的题特别适合拿来练“为什么会想到这样做”的思维链路。下面我把每一题的完整复盘写出来包括我现场是怎么一步步试错、最后敲定方案的以及代码实现和几个容易踩的边界坑。1. A题Polycarp and Snakes——一个“看似复杂”的网格验证题1.1 题目说的到底是什么Polycarp 在一条水平展示线上画了若干条蛇。每条蛇用一个小写字母表示身体是一段连续的格子。规则是先画编号小的蛇再画编号大的蛇后面的蛇会覆盖在之前的蛇上面。所以如果字母a和b同时出现且a b那么a所在的区间必须完全被b所在的区间包含。网格中给定的字符矩阵.表示空格其他字符表示该位置被某条蛇覆盖。换句话说题面可以理解成给定一个n x m的矩阵判断是否能由一组满足“按字母序递增的区间互相包含”的蛇叠加而成。1.2 先想清楚要验证哪些条件这题 A 题难就难在条件比较多现场很容易只检查了部分条件就交然后 WA 一发。我梳理了一下其实要检查的无非是四点所有非.的字符必须在同一行。因为题目说了蛇都画在一条水平展示线上如果出现了两行都有字母那肯定不合法。出现过的字符集合必须是a开始的连续前缀。比如出现了a、c但没有b这就不合法。每个字母的格子必须连续也就是形成一段完整的区间中间不能有空洞。按字母序从小到大后一个字母的区间必须包含前一个字母的区间。这些条件看着多但代码写起来很直接。我们扫描一遍矩阵对每个字母记录它出现的最左列、最右列、所在行以及出现次数。只要出现次数等于R - L 1就说明这段是连续的。1.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, m; cin n m; vectorstring g(n); for (int i 0; i n; i) cin g[i]; vectorint L(26, m), R(26, -1), row(26, -1), cnt(26, 0); int mx -1; for (int i 0; i n; i) { for (int j 0; j m; j) { if (g[i][j] .) continue; int c g[i][j] - a; cnt[c]; L[c] min(L[c], j); R[c] max(R[c], j); row[c] i; mx max(mx, c); } } if (mx -1) { cout YES\n; continue; } bool ok true; // 检查是否从 a 开始连续出现 for (int c 0; c mx; c) { if (cnt[c] 0) { ok false; break; } if (cnt[c] ! R[c] - L[c] 1) { ok false; break; } } // 检查是否都在同一行且区间按字母序互相包含 if (ok) { for (int c 1; c mx; c) { if (row[c] ! row[0]) { ok false; break; } if (L[c] L[c - 1] || R[c] R[c - 1]) { ok false; break; } } } cout (ok ? YES : NO) \n; } return 0; }1.4 容易漏掉的三个边界这题我现场第一次提交就栽在边界上。三个容易漏的点第一矩阵里完全没有字母的情况。这时候mx -1直接输出YES因为“画了零条合法蛇”也是合法的。这个边界一开始很容易忽略。第二区间包含关系的传递性。因为我们保证了字母集合是连续前缀所以只需要检查相邻两个字母的包含关系即可。a被b包含b被c包含自然a就被c包含了不需要额外检查。第三行不相同的情况。有些实现会只检查区间连续性而忽略“所有蛇必须在同一行”这个约束这就会导致样例里的特殊情况判断错。所有非空格的行号必须一致这一步不能省。A 题的教训是遇到这种“多条件验证”的题最靠谱的做法是先把条件一条条列出来再逐条实现而不是一边写一边想。这也对后面几题有帮助。2. B题排序 双指针的贪心直觉为什么大的必须去配小的2.1 题意与一个错误的直觉B 题是一道典型的“配对”题给定n个整数和一个上限k每次操作可以选择两个下标i、j如果a[i] a[j] k就把这两个数从数组中删除。问最多能执行多少次这样的操作。很多人的第一反应是每次找最小的数和某个数配对这样能配对的数量最多。这句“找最小的数”没错但“某个数”怎么选才是关键。我现场一开始想的是用哈希表或者桶去记录每个数出现的次数然后从小到大枚举值域看有没有对应的数能和它相加不超过k。这个思路在值域小的时候能写但一旦n到2e5值域也到2e5哈希表写法虽然能过却完全没有体现出这道题想考的贪心。实际上这题的最佳做法是排序后双指针。2.2 为什么双指针是对的排序之后我们维护左右两个指针l 0r n - 1。每次看a[l] a[r]如果小于等于k说明当前最小的元素可以和当前最大的元素配对直接配对成功l、r--答案加 1。如果大于k说明当前最大的元素太大了它跟数组里最小的元素都配不了那它跟谁也都配不了只能把它丢掉r--。这个贪心为什么正确关键在第二条。当一个元素大到连当前全局最小值都配不了那么在有序数组里它和其他任何元素的和只会更大所以这个元素不可能参与任何配对直接丢弃不会损失最优解。而如果最小元素和最大元素能配对那我们就要“用最小的去配最大的”因为最小元素是“最容易被配对”的资源把它用在一个最难的对手上剩下的数之间配对的余地最大反过来如果让最小元素去配一个中等大小的数最大元素反而可能被浪费掉。排序后 [l] ... [r] 若 a[l] a[r] k配对 l 和 r 否则r--因为 a[r] 与任何 a[l..r] 中的元素相加都 k2.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, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; sort(a.begin(), a.end()); int l 0, r n - 1, ans 0; while (l r) { if (a[l] a[r] k) { ans; l; r--; } else { r--; } } cout ans \n; } return 0; }2.4 这题的思维价值B 题的思维价值不在于代码而在于“配对”类问题的通用思考方式。以后看到“选两个数删除”“选两个点连边”“选两个人组队”这一类问题第一反应就应该是能不能排序排序之后有没有单调性如果有单调性双指针通常就是最优解。另外这题也提醒我们不要一上来就想着用值域桶、哈希表、平衡树去硬模拟先想想排序能不能让问题变简单。很多 CF 前两题的 B 题正解往往就是很朴素的排序加扫描但前提是你得具备“排序之后信息变整齐”的敏感度。3. C题滑动窗口的经典容斥——如何统计“恰好K个不同元素”的子数组3.1 题面与核心转化C 题题目是给一个长度为n的数组问有多少个连续子数组其中不同的元素个数恰好等于k。如果直接枚举左端点然后向右扩展用 set 维护不同元素个数复杂度是O(n^2)肯定不行。但如果我们把问题稍微改一下问有多少个连续子数组不同元素个数不超过 k这个问题就能用滑动窗口在O(n)内解决。于是“恰好等于 k”就转化成了f(k) 不同元素个数不超过 k 的子数组数 答案 f(k) - f(k - 1)这个转化的思路非常关键它是一个通用的容斥技巧“恰好”比“至多”难算那就先算“至多”再相减。3.2 滑动窗口的实现细节怎么统计“不同元素个数不超过 k”的子数组数量呢经典做法是枚举右端点r维护当前窗口[l, r]内不同元素的个数。如果个数大于k就不断移动左端点l直到个数重新小于等于k。这里有个容易想不明白的点为什么当右端点为r时合法的子数组数量是r - l 1因为固定右端点r之后左端点l越往左子数组越长包含的不同元素个数只可能越多。所以如果[l, r]合法那么所有以r为右端点、左端点在[l, r]范围内的子数组都是合法的。这些子数组一共有r - l 1个。累加每个右端点对应的合法数量就是总数。用cnt数组记录窗口内每个数字出现的次数用distinct记录当前窗口内有多少个不同的数字。#include bits/stdc.h using namespace std; long long countAtMostK(const vectorint a, int k) { if (k 0) return 0; int n (int)a.size(); vectorint cnt(200005, 0); int l 0, distinct 0; long long ans 0; for (int r 0; r n; r) { if (cnt[a[r]] 0) distinct; cnt[a[r]]; while (distinct k) { cnt[a[l]]--; if (cnt[a[l]] 0) distinct--; l; } ans r - l 1; } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; long long ans countAtMostK(a, k) - countAtMostK(a, k - 1); cout ans \n; return 0; }3.3 两个注意点第一countAtMostK里的cnt数组大小。如果题目没有给出值域最好的做法是先对数组做离散化或者用unordered_map。但如果值域在可接受范围内直接用数组是最快的。我这里写的是 200005实际使用时要根据题目数据范围调整别直接照抄。第二k - 1小于 0 的情况。如果k 0那么要统计的是“不同元素个数不超过 0”的子数组数也就是空区间但子数组通常非空所以答案是 0。代码里countAtMostK(a, k - 1)会传入-1需要单独判断并返回 0。C 题的核心收获是滑动窗口不是只能求最长/最短区间它也可以用来统计满足某种性质的区间数量。配合“恰好转至多”的容斥能解决一大类统计问题。4. D题选择问题——区间覆盖的最小代价与线段树优化DP4.1 题目模型D 题是经典的区间覆盖问题。给定n个区间每个区间是[l_i, r_i]选择它的代价是c_i。现在要用这些区间覆盖[1, m]上的所有整数点求最小总代价。如果无法完整覆盖输出-1。这个题的“选择”二字实际上是在说区间摆在那里你可以选也可以不选目标是让选出来的区间并集覆盖整个范围。这就是一个典型的“决策类 DP”问题。4.2 朴素 DP设dp[i]表示覆盖[1, i]的最小代价。初始时dp[0] 0其余为无穷大。当我们选择区间[l, r]时如果前面已经覆盖到了l - 1那么接上这个区间后就能覆盖到r。所以转移是dp[r] min(dp[r], min(dp[x]) c) 其中 x 属于 [l - 1, r - 1]这里x只要至少等于l - 1就行因为区间[l, r]本身能覆盖从l到r的所有点前面覆盖到x l - 1的话中间有空隙接不上。所以朴素做法是对每个区间枚举x从l - 1到r - 1找一个最小的dp[x]加c更新dp[r]。复杂度是O(n^2)显然不行。4.3 用线段树优化观察转移式子我们要的是一个区间内的dp最小值而且 DP 是顺序更新的按r从小到大更新。这正好可以用线段树维护整个dp数组的前缀最小值。具体实现先把区间按右端点r从小到大排序。初始化线段树所有位置值设为无穷大dp[0] 0单点更新到线段树。遍历每个区间[l, r, c]查询[l - 1, r - 1]范围内的最小值best。如果best是无穷大说明这个区间接不上任何已覆盖的前缀跳过。否则用best c尝试更新dp[r]也就是在线段树的r位置做单点取最小值。最终答案是dp[m]如果无穷大则输出-1。注意几个细节区间端点都是整数如果m范围很大比如1e9需要先离散化所有端点如果区间端点从 1 开始那么dp[0]对应一个虚拟的“起点”。我写的时候习惯让下标从 1 开始这样转移时查询[l - 1, r - 1]更自然。#include bits/stdc.h using namespace std; const long long INF 4e18; struct SegmentTree { int n; vectorlong long tree; SegmentTree(int n) : n(n), tree(4 * n 4, INF) {} void update(int p, long long val, int node, int l, int r) { if (l r) { tree[node] min(tree[node], val); return; } int mid (l r) / 2; if (p mid) update(p, val, node * 2, l, mid); else update(p, val, node * 2 1, mid 1, r); tree[node] min(tree[node * 2], tree[node * 2 1]); } long long query(int ql, int qr, int node, int l, int r) { if (ql r || qr l) return INF; if (ql l r qr) return tree[node]; int mid (l r) / 2; return min(query(ql, qr, node * 2, l, mid), query(ql, qr, node * 2 1, mid 1, r)); } }; struct Node { int l, r; long long c; }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorNode segs(n); for (int i 0; i n; i) { cin segs[i].l segs[i].r segs[i].c; } sort(segs.begin(), segs.end(), [](const Node A, const Node B) { return A.r B.r; }); SegmentTree st(m 1); st.update(0, 0, 1, 0, m); for (auto s : segs) { if (s.l m) continue; int ql max(0, s.l - 1); int qr min(m, s.r - 1); long long best st.query(ql, qr, 1, 0, m); if (best ! INF) { st.update(s.r, best s.c, 1, 0, m); } } long long ans st.query(m, m, 1, 0, m); cout (ans INF ? -1 : ans) \n; return 0; }4.4 为什么线段树优化是对的这个 DP 的转移来源是一个区间的dp最小值而不是单个点所以不能用简单的前缀最小值数组来维护因为我们要的到底是哪一段取决于新区间的左端点。线段树能灵活地支持“区间查最小值 单点更新”正好适配这个需求。另外按右端点排序保证了我们处理区间时之前所有可能更新到dp[x]的区间都已经处理过了DP 的无后效性就满足了。D 题告诉我们要对“区间类 DP”的优化敏感当转移方程变成dp[i] min(dp[j]) cost且j在某个范围内时线段树/树状数组优化往往就是下一步的方向。5. E题棋盘染色的二项式反演——容斥也能解计数题5.1 题面E 题是一个n x m的棋盘每个格子可以染成黑色或白色问有多少种染色方案使得每一行至少有一个黑色格子并且每一列至少有一个黑色格子。注意这里的限制条件里行和列都是“至少一个黑格”而不是“恰好”。这种“至少”型的计数问题很容易让人想到容斥我们统计“某些行/列不合法”的方案数再通过容斥把它们去掉。5.2 容斥公式推导我们设“坏行”表示这一行没有黑格“坏列”表示这一列没有黑格。题目要求的就是坏行数为 0 且坏列数为 0 的方案数。记F(i, j)表示至少指定某i行和某j列是坏的方案数。这里“指定”的意思是我们选择i行让它们必须全白选择j列让它们必须全白剩下的格子随意填。那么在n行中有i行坏、m列中有j列坏的情况下剩下的格子数量是(n - i) * (m - j)每个格子可以黑可以白所以方案数是F(i, j) C(n, i) * C(m, j) * 2^((n - i) * (m - j))然后容斥坏行数和坏列数都为 0 的方案数等于答案 Σ_{i0}^{n} Σ_{j0}^{m} (-1)^(ij) * C(n, i) * C(m, j) * 2^((n - i) * (m - j))这里(-1)^(ij)是因为我们对i个坏行和j个坏列做容斥所以符号由ij的奇偶决定。5.3 代码实现细节#include bits/stdc.h using namespace std; const long long MOD 1e9 7; long long qpow(long long base, long long exp) { long long res 1; while (exp) { if (exp 1) res res * base % MOD; base base * base % MOD; exp 1; } return res; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; int lim max(n, m); vectorlong long fact(lim 1), invFact(lim 1); fact[0] 1; for (int i 1; i lim; i) fact[i] fact[i - 1] * i % MOD; invFact[lim] qpow(fact[lim], MOD - 2); for (int i lim; i 1; i--) invFact[i - 1] invFact[i] * i % MOD; auto C [](int a, int b) - long long { if (b 0 || b a) return 0; return fact[a] * invFact[b] % MOD * invFact[a - b] % MOD; }; long long ans 0; for (int i 0; i n; i) { for (int j 0; j m; j) { long long term C(n, i) * C(m, j) % MOD; term term * qpow(2, 1LL * (n - i) * (m - j)) % MOD; if ((i j) 1) { ans (ans - term MOD) % MOD; } else { ans (ans term) % MOD; } } } cout ans \n; return 0; }5.4 指数范围与取模细节这个题第一个容易错的地方是2^((n - i) * (m - j))的指数可能很大最大是n * m如果n, m都到1e5n*m可能到1e10所以不能直接用数组预处理 2 的幂必须用快速幂或者预处理pow2到n*m前提是n*m在可接受范围。第二个容易错的地方是容斥取模时减法要加MOD再取模避免负数。我见过很多选手在负数取模上 WA 到怀疑人生这题因为项数多尤其要小心。第三个点是如果n, m都很大O(nm)的二重循环可能会超时。这题如果数据范围到1e5需要用生成函数或者 NTT 来做但作为 E 题O(nm)的版本其实已经足够用来理解容斥的核心思想。比赛里碰到这类题先确认数据范围再决定要不要降复杂度。E 题给我的最大感受是组合计数题里“至少”永远比“恰好”难算而容斥就是连接两者的桥。遇到“至少”不要怕先把反面条件设成坏事件然后逐项容斥通常能把式子写出来。6. F题所有子区间的“最大-最小-长度”贡献——单调栈拆贡献6.1 题目与公式化简F 题题目给定一个长度为n的排列p定义区间[l, r]的价值为max(p[l..r]) - min(p[l..r]) - (r - l)求所有子区间的价值之和。如果直接枚举所有区间复杂度是O(n^2)。必须拆贡献。设S_max为所有子区间最大值之和S_min为所有子区间最小值之和S_len为所有子区间长度之和那么总价值是S_max - S_min - (S_len - 区间个数)因为每个区间的(r - l)就等于长度减 1。区间长度之和可以直接算长度为 1 的区间有n个长度为 2 的有n-1个...所以S_len Σ_{k1}^{n} k * (n - k 1) n*(n1)*(n2)/6区间个数是n*(n1)/2所以Σ(r - l) S_len - n*(n1)/2 n*(n-1)*(n1)/6于是题目变成了求S_max和S_min。6.2 单调栈的核心思路S_max的计算是经典题对每个位置i我们找到p[i]作为最大值时能覆盖哪些子区间。问题是如果两个相等的最大值同时出现在一个区间里我们只应该计算一次。所以某个位置i作为最大值时我们要规定它是这个区间里“最左的最大值”或“最右的最大值”这样才不会重复计数。我用的是“左边严格大于右边大于等于”的规则L[i]左边第一个大于p[i]的位置不含默认-1R[i]右边第一个大于等于p[i]的位置不含默认n这样p[i]作为“严格最大”能覆盖的所有子区间的左端点在(L[i], i]之间右端点在[i, R[i])之间。数量是(i - L[i]) * (R[i] - i)。对于S_min同理L[i]左边第一个小于p[i]的位置R[i]右边第一个小于等于p[i]的位置这样保证每个区间的最小值只被最左的最小值位置统计一次。6.3 代码#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); for (int i 0; i n; i) cin a[i]; vectorint L(n), R(n); stackint st; // 计算 S_max左边第一个大于右边第一个大于等于 for (int i 0; i n; i) { while (!st.empty() a[st.top()] a[i]) st.pop(); L[i] st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i n - 1; i 0; i--) { while (!st.empty() a[st.top()] a[i]) st.pop(); R[i] st.empty() ? n : st.top(); st.push(i); } long long sumMax 0; for (int i 0; i n; i) { sumMax 1LL * a[i] * (i - L[i]) * (R[i] - i); } // 计算 S_min左边第一个小于右边第一个小于等于 while (!st.empty()) st.pop(); for (int i 0; i n; i) { while (!st.empty() a[st.top()] a[i]) st.pop(); L[i] st.empty() ? -1 : st.top(); st.push(i); } while (!st.empty()) st.pop(); for (int i n - 1; i