今天继续打卡信奥题。这一篇做的是洛谷 P6360题目来自 CEOI 2018叫 Lottery。刚看到这个题名我以为是个概率期望题读完题发现完全不是那么回事——它其实是一个“全区间两两比较 多组阈值查询”的计数题核心考点是固定偏移量后的滚动递推以及对多查询做阈值分档。先说这题适合谁正在准备信奥提高组、省选的选手尤其是想练“不要枚举窗口而是枚举偏移量”这种经典套路的人。代码不长但要真正想清楚边界和查询处理还是需要花点时间的。我这一篇直接给出可提交的 C17 写法并把推导过程、边界检查、对拍思路全部拆开讲。1. 题目在做什么把每个连续子段当成一张彩票两两比差距给定一个长度为 n 的整数序列 a再给一个窗口长度 m。我们把 a 中所有长度为 m 的连续子段都拿出来一共有 N n - m 1 个每个子段就是一张“彩票”。定义两张彩票的“距离”为逐位比较时位置上数字不相同的个数。比如 a [1, 2, 3, 2, 1]m 3那么彩票分别是 [1,2,3]、[2,3,2]、[3,2,1]。第一张和第二张逐位比较1≠2、2≠3、3≠2三处全不同所以距离是 3。现在有 q 个询问每个询问给一个整数 k要求对每张彩票 i 输出有多少张其他的彩票 j满足彩票 i 和彩票 j 的距离不超过 k。记号含义n序列长度m每张彩票的长度N n - m 1彩票总数dist(i, j)第 i 张和第 j 张彩票逐位不同的位置数q, k询问次数和每次的阈值按照洛谷上的数据范围n ≤ 10^4m ≤ nq ≤ 100。这个数据范围很有意思N 最多也是 10^4 左右两两配对有约 5×10^7 对但如果每一对都逐位比 m 个位置复杂度会到 O(N²·m)最坏是 10^12直接 TLE 到没边。所以第一步要解决的就是如何高效求出所有窗口对之间的距离。1.1 为什么不能老老实实枚举窗口对最朴素的做法是两层循环枚举 i 和 j再内层循环逐位比较for i in 0..N-1: for j in i1..N-1: cnt 0 for t in 0..m-1: if a[it] ! a[jt]: cnt这个三层循环把“窗口对”当成枚举对象完全没有利用到数组本身的连续性。N 10^4 时光窗口对就是 10^8 级别再乘上 m任何语言都扛不住。1.2 真正该枚举的是“偏移量”窗口对 (i, j) 可以看成起点相差 d j - i 的两个窗口。如果固定 d那么窗口对从左往右移动时比较范围其实只是整体平移了一格。这个观察能把每个偏移量下的所有窗口对距离用 O(n) 时间全部滚动推出来。这是整道题最关键的思维转变枚举偏移量 d而不是枚举窗口对。2. 固定偏移量后相邻窗口对只需滚动更新2.1 核心推导对于某个固定的正整数 d我们关心所有形如 (i, id) 的窗口对。记 cur[i] dist(i, id)也就是cur[i] a[i..im-1] 和 a[id..idm-1] 逐位不同的个数现在看 cur[i] 和 cur[i1] 的关系。cur[i] 比较的是这些配对(a[i], a[id]), (a[i1], a[i1d]), ... (a[im-1], a[idm-1])cur[i1] 比较的是这些配对(a[i1], a[i1d]), (a[i2], a[i2d]), ... (a[im], a[idm])对比一下就发现cur[i1] 的结果就是 cur[i] 去掉最前面一对 (a[i], a[id])再加上最后面新出现的一对 (a[im], a[idm])。所以有cur[i1] cur[i] - (a[i] ! a[id]) (a[im] ! a[idm])这里用 C 的 bool 转 int 规则表达式为 true 时等于 1为 false 时等于 0。这样每算完一对下一步只需要 O(1) 就能推出下一对。2.2 一个偏移量下的完整流程对于固定的 d先暴力算出第一对窗口 (0, d) 的距离也就是 cur[0]代价 O(m)。然后 i 从 0 开始用上面公式依次推出 cur[1]、cur[2]、…直到覆盖所有起点 i 满足 id ≤ N-1。因为 N 是彩票总数起点 i 加上偏移量 d 之后仍然要落在合法彩票范围内所以 i 最大是 N-1-d。这样处理一个 d 的代价是 O(m (N-d))把所有 d 1 到 N-1 都算一遍总代价是sum_{d1}^{N-1} (m N - d) m(N-1) N(N-1)/2这就在 O(n²) 级别了。n 10^4 时大约是 10^8 次简单操作C 开 O2 跑完全没问题。对比原来的 O(n²m)是本质性的优化。2.3 为什么这个递推式不会错最容易担心的一点是cur[i] 里比较的配对和 cur[i1] 里比较的配对有一部分是重合的。没错重合部分正是从 i1 到 im-1 的这些配对它们的比较结果完全没变。唯一被删掉的是最左边那一对唯一新增的是最右边那一对。这其实和“长度为 m 的滑动窗口求和”是同一个思路窗口滑动一格出去一个数进来一个数。区别只是这里出去和进来的不是数组元素本身而是“两个位置是否相等”的判断结果。把这个递推式写成代码时还要注意 i 的边界。我习惯用 0-indexed 表示起点这样 a[im] 和 a[idm] 的下标非常直观。3. 多查询别硬算把距离先映射到“第一个覆盖它的询问”拿到所有窗口对的距离之后还剩两个问题一是怎么存二是怎么回答 q 个询问。如果直接把所有 dist(i, j) 存在一个 N×N 的矩阵里N 10^4 时就是 10^8 个数就算用 short 也要 200MB内存非常紧张。如果对每个询问再暴力扫一遍所有窗口对复杂度变成 O(q·N²)同样不可行。所以查询部分也要做一点巧妙的处理。3.1 距离值只需关心“第一个覆盖它的询问”先把所有询问的阈值排序去重得到k[0] k[1] ... k[Q-1]其中 Q ≤ 100。对于一个距离值 v它能被哪些询问统计到答案是所有满足 k[t] ≥ v 的询问。换句话说从某个位置开始后面所有询问都会统计它。记 cat[v] 为第一个满足 k[cat[v]] ≥ v 的询问下标。这个 cat[v] 可以用二分求但因为 v 的范围只有 0..m也可以直接预处理while (p Q k[p] v) p; cat[v] p;这么一来一对距离为 v 的窗口 (i, j)它对答案的贡献就是所有询问 t只要 t ≥ cat[v]都要 1。与其在每对窗口上循环所有询问不如先给每张彩票开一个桶数组 bucket[i][c]表示“有多少对包含彩票 i 的窗口它们的 cat 值等于 c”。处理完所有窗口对之后对每个 i 做一次桶数组的前缀和就能得到每个询问的答案。3.2 为什么前缀和能对上对于彩票 i桶数组第 c 格放的是“距离类别为 c 的窗口对数量”。因为类别 c 表示该距离从询问 c 开始才被覆盖所以询问 0 的答案是 bucket[i][0]询问 1 的答案是 bucket[i][0] bucket[i][1]询问 t 的答案是 bucket[i][0] ... bucket[i][t]这就是一个非常标准的前缀和。方案空间时间存 N×N 距离矩阵约 200MB危险查询还要扫矩阵对每对窗口枚举 q小O(q·N²)太慢桶数组 前缀和N×Q约 4MBO(N² N·Q)桶数组的大小是 N×Q 而不是 N×m这是这道题查询部分的关键。q ≤ 100 意味着 Q ≤ 10010^4 个窗口每个开 100 个桶内存只有几 MB。3.3 自身对要不要算注意我上面枚举 d 的时候是从 1 开始的也就是说完全避开了 d 0 的情况不会把彩票 i 和它自己组成一对。因此输出天然是“其他彩票”的数量。如果某些变体题面要求“包括自己”那答案统一加 1 就行。我写代码时按原题“其他彩票”处理这也是 CEOI 2018 原题的意思。4. 完整 C17 代码与关键行说明下面这段代码可以直接在洛谷以 C17 提交。主算法就是第 2 节的滚动递推加上第 3 节的桶数组统计。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin n m; vectorint a(n); for (int i 0; i n; i) cin a[i]; int q; cin q; vectorint query(q); for (int i 0; i q; i) cin query[i]; vectorint ks query; sort(ks.begin(), ks.end()); ks.erase(unique(ks.begin(), ks.end()), ks.end()); int Q (int)ks.size(); int N n - m 1; // 彩票总数 // cat[v] 第一个满足 k[cat[v]] v 的询问下标 vectorint cat(m 1); for (int v 0, p 0; v m; v) { while (p Q ks[p] v) p; cat[v] p; } // bucket[i * Q c]彩票 i 的“距离类别 c”统计 vectorint bucket((long long)N * Q, 0); auto add [](int idx, int c) { if (c Q) bucket[(long long)idx * Q c]; }; vectorint cur(N, 0); for (int d 1; d N; d) { // 先算第一对窗口 (0, d) int diff0 0; for (int t 0; t m; t) if (a[t] ! a[d t]) diff0; cur[0] diff0; add(0, cat[diff0]); add(d, cat[diff0]); // 滚动推出剩下的窗口对 for (int i 0; i N - d - 1; i) { int nd cur[i] - (a[i] ! a[i d]) (a[i m] ! a[i d m]); cur[i 1] nd; int c cat[nd]; add(i 1, c); add(i 1 d, c); } } // 对每个彩票做桶的前缀和得到每个询问的答案 for (int i 0; i N; i) for (int c 1; c Q; c) bucket[(long long)i * Q c] bucket[(long long)i * Q c - 1]; // 按照原始询问顺序输出 for (int t 0; t q; t) { int pos lower_bound(ks.begin(), ks.end(), query[t]) - ks.begin(); for (int i 0; i N; i) { cout bucket[(long long)i * Q pos]; if (i 1 N) cout ; } cout \n; } return 0; }4.1 代码里几个容易写错的地方第一个是 cat 的预处理。如果你在滚动递推的内层循环里临时做二分查 cat[v]虽然也能过但完全没必要。v 的范围只有 0..m提前把所有 v 的类别算好内层就是一次 O(1) 查表。第二个是滚动递推的边界判断。内层循环写成i N - d - 1而不是i N。原因是最多只能取到 i N - d - 1 作为窗口对起点再往右就越界了。通常在写这类代码时边界少写一个单位直接导致数组越界或者漏算最后一对。第三个是桶数组的一维化。用vectorvectorint写起来方便但 N×Q 本身很小没必要让二维 vector 多一层寻址。直接用(long long)i * Q c手动定位缓存友好速度也更快。4.2 如果题面给的是“相同位数”而不是“不同位数”有些题会用“相似度”来描述两张彩票相同的位数。遇到这种情况请先把相似度 s 换算成距离 v m - s再来查 cat。否则类别映射就全乱了。我在做题时习惯先把题目统一翻译成自己的定义再动手这个习惯能避免很多后期改 bug 的时间。5. 边界检查、对拍思路与踩过的坑这一节总结我在实际提交前必做的检查项以及踩过的一些坑。5.1 自己先对拍一遍写完主算法后我建议立刻写一个 O(N²·m) 的暴力版本生成小规模随机数据比如 n ≤ 30m ≤ 10q ≤ 5反复随机对比主算法和暴力的输出。对拍重点看这么几个地方d 1 和 d N-1 这两端是否都正确。m 1 时每张彩票只有一个数字距离只有 0 和 1滚动递推仍然成立。q 个询问里有重复阈值时输出是否和暴力一致。k 大于 m 时理论上所有窗口对都满足答案应该都是 N-1这可以作为一组天然的边界测试。我最早就是靠对拍发现自己在内层循环里漏了最后一对窗口修复之后就全绿了。5.2 排序去重后输出顺序别丢q 个询问不一定有序也不一定互不相同。我的做法是先把原始询问存一份排序去重得到 ks最后再用lower_bound找回原始询问对应的位置。如果你想偷懒不写去重Q 最大 100桶数组多开几列也无所谓但去重后代码逻辑更干净前缀和的语义也更清楚。5.3 这道题真正值得记下来的套路说回一开始那个“枚举偏移量”的思路。以后遇到所有“子段两两比较”的题目第一反应都应该是不枚举窗口对而是枚举偏移量 d然后想办法滚动更新这个偏移量下的所有结果。类似的思想在字符串匹配、区间相似度、甚至一些 DP 优化里都会出现。P6360 这道题妙就妙在它把那个看起来很吓人的“所有子段两两比较”压缩成了 O(n²)而且代码核心只有那一条滚动递推公式。我个人觉得做这道题的收获不在于是不是 AC而在于以后看到“两两比较”四个字时能立刻想到偏移量这个维度。多了一维思考方式很多题会突然变简单不少。