今天这道打卡题是洛谷 P6360 [CEOI 2018] Lottery。光看标题我一开始还以为是概率期望或者什么抽奖模型点进去才发现是一道很实在的序列匹配计数题给一个序列固定窗口长度把所有长度相同的连续子段两两比较统计“对应位置不相同的个数”然后回答若干组阈值查询。题目名字很喜庆但真要把 C 代码写得能过数据范围还是有不少细节值得掰开揉碎说一遍。这篇文章我会把从暴力到正解的完整推导、内存压缩思路、可提交代码以及我实际踩过的坑都写出来给同样在刷信奥题的同学做个参考。这道题的定位很适合拿来练“暴力枚举到优化”的思维过程。它不考什么冷门数据结构核心就两个点第一怎么把两个窗口之间逐位比较的 O(k) 时间省掉第二怎么把几万个窗口两两之间的距离存下来而不炸内存。把这两点想明白代码其实不长但每一步都有讲究。1. 题目到底在做什么1.1 题面人话翻译先理解一下题意。假设给出一个长度为 n 的数组 a再给一个窗口长度 k。我们从左往右滑动会得到 m n - k 1 个长度为 k 的连续子段每个子段可以看作一个“窗口”。任意拿两个窗口出来比如窗口 i 和窗口 j它们的距离定义是逐位比较两个窗口中的元素对应位置不同距离加 1对应位置相同距离不变。所以距离的取值范围是 [0, k]距离为 0 表示两个窗口完全一样距离为 k 表示两个窗口没有一位相同。这个距离本质上就是两个等长序列之间的汉明距离只不过元素不是字符而是整数。接下来会有 q 次询问。每次询问给一个阈值 x要求对于每一个起点 i统计一共有多少个窗口 j满足第 i 个窗口和第 j 个窗口的距离不超过 x。注意统计的是距离不超过 x 的窗口数量一般题目不会把第 i 个窗口自己算进去因为自己和自己距离为 0会多一个常数。做题前要看清题面我下面按“不考虑自身”来写。这个模型特别像“找相似子串”但是又比字符串匹配灵活因为这里比较的是数值序列而且阈值是动态查询的。如果窗口长度很小理论上可以枚举所有窗口对直接算但一旦 n 上到几千甚至一万这个想法就不可行了。1.2 先算一笔暴力账假设我第一反应是暴力for (int i 1; i m; i) { for (int j 1; j m; j) { int dis 0; for (int p 0; p k; p) { if (a[i p] ! a[j p]) dis; } // 记录 dis } }这个写法的时间复杂度是 O(m^2 * k)。m 大约是 n所以总复杂度接近 O(n^2 * k)。当 n 5000 时n^2 是 2500 万再乘上 k如果 k 也是几千那就是百亿级别操作C 再快也扛不住。就算 k 很小比如 k 1m n暴力复杂度 O(n^2)看起来好像勉强能跑但距离计算本身还有 q 次查询要处理。如果 q 是几千再乘上 m又是千万级别依然很悬。所以这道题真正的难点不是“题意有多绕”而是“能不能把窗口之间的比较从 O(k) 降到 O(1)”。只要这一步想通了整道题就从暴力题变成了偏考察实现功底的题。2. 破局点差值固定时距离就是一条对角线上的区间和2.1 固定差值 d把问题变成一维匹配两个窗口起点分别为 i 和 j令差值 d j - i这里先假设 j i也就是 d 0。两个窗口要比较的是a[i] 和 a[j] 是否相同a[i 1] 和 a[j 1] 是否相同...a[i k - 1] 和 a[j k - 1] 是否相同注意看下标它们永远相差 d。也就是说当 d 固定时比较的每一对元素都落在同一条“右移 d 位”的对角线上。我们可以先造一个长度为 n - d 的布尔数组 b其中b[t] 1 表示 a[t] a[t d] b[t] 0 表示 a[t] ! a[t d]那么窗口 i 和窗口 i d 的“相同位数”就是same b[i] b[i 1] ... b[i k - 1]这就是一个区间求和。既然 b 数组是静态的我们就可以对 b 做前缀和pre[t] pre[t - 1] b[t]于是任意窗口的相同位数都能 O(1) 得到same pre[i k - 1] - pre[i - 1]距离自然就是dis k - same这个思路的关键在于所有距离为 d 的窗口对它们的比较对象都可以共用同一个 b 数组所以不需要重复枚举窗口里的每一位。2.2 一个手算小例子为了把上面这套东西讲得更好理解我举一个具体的例子。假设数组 a [1, 2, 3, 2, 1]窗口长度 k 2窗口总数 m 4。窗口依次是窗口 1[1, 2]窗口 2[2, 3]窗口 3[3, 2]窗口 4[2, 1]我现在算差值 d 2 的情况。b 数组长度是 n - d 3b[1] (a[1] a[3]) (1 3) 0 b[2] (a[2] a[4]) (2 2) 1 b[3] (a[3] a[5]) (3 1) 0前缀和 pre 为pre[0] 0 pre[1] 0 pre[2] 1 pre[3] 1对于窗口 1 和窗口 3i 1k 2same pre[1 2 - 1] - pre[0] pre[2] - pre[0] 1 - 0 1 distance 2 - 1 1实际上看窗口 1 [1, 2] 和窗口 3 [3, 2]对应位置 1 和 3 不同2 和 2 相同距离确实是 1。对于窗口 2 和窗口 4i 2same pre[2 2 - 1] - pre[1] pre[3] - pre[1] 1 - 0 1 distance 2 - 1 1窗口 2 [2, 3] 和窗口 4 [2, 1]2 和 2 相同3 和 1 不同距离也是 1。可以看到整个过程不需要真的去枚举窗口内部的两位来比较直接用前缀和就推出来了。2.3 复杂度为什么会降一个量级外层的 d 从 1 枚举到 m - 1因为两个窗口起点差不可能超过 m - 1。对于每个 d预处理 b 数组需要扫描 n - d 个位置然后对 i 从 1 到 m - d 的这些窗口起点用前缀和 O(1) 计算距离。总复杂度大约是sum_{d1}^{m-1} (n - d) (m - 1) * n - (m - 1) * m / 2上限差不多是 O(n * m)最坏情况接近 O(n^2 / 2)。如果 n 10000这就是 5000 万次操作C 完全可以在 1 秒左右跑完。这比之前的 O(m^2 * k) 好了太多。而且这个优化很“无脑”不需要任何高级数据结构只需要想清楚“两个窗口起点差值固定时比较路径是整齐的对角线”。3. C实现从矩阵到可提交代码3.1 距离矩阵的内存管理距离计算完之后所有窗口两两之间的距离需要存下来因为后面还有 q 组询问要反复读取。最简单直观的做法是开一个二维数组int dist[MAXM][MAXM];但 n 如果上到 10000m 也可能接近 10000这样 dist 就有 1 亿个 int占 400MB 内存很容易超限。我实际采用的方案有两个关键点第一距离类型用unsigned short。两个窗口的距离最大是 k而 k 不会超过 n所以用能存到 65535 的 unsigned short 足够。如果题目里 n 最大是 10000那距离最大值就是 10000完全放得下。这能把内存直接砍掉一半。第二只存上三角。距离矩阵是对称的dist[i][j] 和 dist[j][i] 相等所以我只需要存 i j 的部分。总元素数量从 m * m 变成 m * (m - 1) / 2又省了一半。这两步叠加内存占用大概是原来的四分之一。上三角用一维数组存的时候需要自己算索引。我习惯让窗口编号从 1 开始定义 idx(i, j)其中 i j表示窗口 i 和窗口 j 的距离存在一维数组的哪个位置。计算方式是这样的第 1 行有 m - 1 个元素第 2 行有 m - 2 个元素...第 i 行之前有 sum_{t1}^{i-1} (m - t) 个元素第 i 行第 j 列是这一行的第 (j - i - 1) 个元素。写成代码就是auto idx [](int i, int j) - size_t { return 1ULL * (i - 1) * m - 1ULL * (i - 1) * i / 2 (j - i - 1); };这里的1ULL是为了防止乘法溢出尤其是当 m 上万时m * m 已经接近 1 亿int 虽然也能存但总归保险一点。3.2 完整C代码下面是完整的可提交代码。我默认输出格式是“每个询问输出一行每行 m 个整数”如果你的题目要求“每个窗口输出一行”只需要把最后双重循环的嵌套顺序调换一下。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, k, q; cin n k q; vectorint a(n 1); for (int i 1; i n; i) cin a[i]; int m n - k 1; // 窗口数量 vectorint qx(q), qid(q); for (int i 0; i q; i) { cin qx[i]; qid[i] i; } sort(qid.begin(), qid.end(), [](int x, int y) { return qx[x] qx[y]; }); // 上三角一维索引 auto idx [](int i, int j) - size_t { return 1ULL * (i - 1) * m - 1ULL * (i - 1) * i / 2 (j - i - 1); }; vectorunsigned short dist(1ULL * m * (m - 1) / 2); vectorint pre(n 1, 0); for (int d 1; d m - 1; d) { // b[t] (a[t] a[t d]) for (int t 1; t n - d; t) { pre[t] pre[t - 1] (a[t] a[t d]); } // 计算所有起点差为 d 的窗口对 for (int i 1; i m - d; i) { int same pre[i k - 1] - pre[i - 1]; dist[idx(i, i d)] (unsigned short)(k - same); } } // ans[id][i] 表示询问 id 对第 i 个窗口的答案 vectorvectorunsigned short ans(q, vectorunsigned short(m)); vectorint row; row.reserve(m - 1); for (int i 1; i m; i) { row.clear(); // 第 i 行的所有距离 for (int j 1; j i; j) row.push_back(dist[idx(j, i)]); for (int j i 1; j m; j) row.push_back(dist[idx(i, j)]); sort(row.begin(), row.end()); int ptr 0; int sz (int)row.size(); for (int id : qid) { int x qx[id]; while (ptr sz (int)row[ptr] x) ptr; ans[id][i - 1] (unsigned short)ptr; } } for (int id 0; id q; id) { for (int i 0; i m; i) { if (i) cout ; cout ans[id][i]; } cout \n; } return 0; }3.3 关键代码段讲解先看预处理距离的部分。for (int d 1; d m - 1; d) { for (int t 1; t n - d; t) { pre[t] pre[t - 1] (a[t] a[t d]); } for (int i 1; i m - d; i) { int same pre[i k - 1] - pre[i - 1]; dist[idx(i, i d)] (unsigned short)(k - same); } }这里有一个容易忽略的边界为什么第二个循环里 i 只到 m - d因为窗口 i 和窗口 i d 都必须完整落在长度为 n 的序列内。窗口 i d 的右端点是(i d) k - 1 i d k - 1 n移项得到i n - k 1 - d m - d所以 i 的范围是 [1, m - d]。同理d 本身最大也只能是 m - 1因为当 i 1 时窗口 1 和窗口 1 d 要能同时存在必须满足 1 d m也就是 d m - 1。再回答一个问题为什么第二个循环里same pre[i k - 1] - pre[i - 1]是对的因为窗口 i 和窗口 i d 比较时对应的匹配位置是从 i 到 i k - 1恰好是 b 数组的一个长度为 k 的区间。前缀和 pre 的差分就是这个区间的和也就是相同位数。距离等于 k 减去相同位数这个也很好理解。两个长度为 k 的窗口一共有 k 个对应位置要么相同要么不同没有第三种情况。4. 多组询问的离线回答4.1 排序双指针一次处理所有查询距离矩阵算完之后剩下的问题是怎么高效回答 q 个阈值询问。最笨的方法是每个询问都扫一遍所有窗口的所有距离复杂度 O(q * m^2)这肯定不行。我的做法是把询问按阈值 x 从小到大排序对每个窗口 i把窗口 i 到其他所有窗口的距离拿出来排个序因为询问已经从小到大排好序了所以可以用一个指针 ptr 在这行有序距离上单调移动指针指到哪里说明有多少个距离小于等于当前阈值 x。这样做的好处是每一行只需要排序一次所有询问都在这行上用同一个指针扫描不需要每个询问都二分一次。核心代码就是sort(row.begin(), row.end()); int ptr 0; int sz (int)row.size(); for (int id : qid) { int x qx[id]; while (ptr sz (int)row[ptr] x) ptr; ans[id][i - 1] (unsigned short)ptr; }比如这一行距离排完序是 [0, 2, 3, 5, 5, 7]当前要回答阈值 x 4那么小于等于 4 的距离有 3 个答案就是 3。指针继续往下到 x 6 时又多了两个等于 5 的距离答案变成 5。这个技巧实际应用很广。凡是“多组查询 静态序列 统计小于等于某个值的数量”基本都可以往这个方向想。4.2 输出顺序和答案矩阵答案矩阵我开成vectorvectorunsigned short ans(q, vectorunsigned short(m));这对应“q 个询问每个询问有 m 个窗口答案”。具体输出时for (int id 0; id q; id) { for (int i 0; i m; i) { if (i) cout ; cout ans[id][i]; } cout \n; }如果你发现自己的题目输出是“每个窗口一行每行 q 个答案”那就把这两层循环反过来变成外层窗口、内层询问。这个不涉及算法复杂度只是读题时要仔细。另外ans 也用了 unsigned short因为答案最大是 m - 1m 不超过 10000unsigned short 足够。这样整个答案矩阵能省一半内存。4.3 如果m、q很大怎么办如果 m 和 q 都特别大比如 m 10000、q 10000那么 ans 矩阵就是 1 亿个 unsigned short占 200MB再加上 dist 数组的一百多 MB内存依然很紧张。这种情况下可以进一步优化第一dist 数组也可以考虑边算边释放。如果不需要保存完整距离矩阵可以在算完某个窗口 i 的所有距离后马上排序并回答询问然后丢掉这一行的数据。不过因为前面我们用差值 d 去算距离得到的是对角线方向的数据想要按行组织需要先把所有差值算完这个方式不太容易改成流式。第二距离的取值范围是 [0, k]如果 k 不大每行排序可以改成桶排序或者计数排序这样排序复杂度从 O(m log m) 降到 O(m k)。不过大部分常规数据下直接用 sort 已经能过没必要为了极端的边界数据把代码写得很复杂。第三如果 q 很大但是输入阈值 x 有很多重复也可以先去重再用映射记录答案能省一点查询时间。总的来说实际比赛里要根据数据范围动态调整P6360 这道题的常规数据下上面的代码已经足够稳。5. 踩坑记录与调试技巧5.1 下标与索引公式最容易写错这个题我最开始写了三四个版本WA 的原因基本都是下标的边界问题。第一个坑是窗口编号。我习惯用 1-based数组 a 下标从 1 到 n窗口起点从 1 到 m。如果你中间突然混进 0-based 的下标比如 a 从 0 开始读入那么 pre 数组和 idx 函数都要重新推特别容易乱。所以我建议统一用 1-based从读入数组的时候就留一个a[0]空着。第二个坑是 idx 函数。这个公式如果写错程序不会 RE而是把距离写进错误的内存位置造成诡异的逻辑错误。我的经验是写完 idx 后先写一个小测试idx(1, 2) 应该等于 0因为第 1 行第 1 个元素idx(m - 1, m) 应该等于 m * (m - 1) / 2 - 1也就是数组最后一个元素。你可以直接在代码里加几个断言跑小数据时检查能有效避免下标错位。第三个坑是 d 的上界。有人会把 m - 1 写成 n - 1。如果写成 n - 1那么在 i 循环里 i d 可能超过 m导致计算出来的距离没有任何意义甚至数组访问越界。记住两个窗口的起点差值最大是 m - 1不是 n - 1。5.2 类型、I/O和常数优化C 的vectorunsigned short是个好东西。它比 int 数组省一半内存访问速度也不会慢多少。但要注意从unsigned short读出来参与运算时最好显式转成 int否则容易出现意想不到的隐式类型提升问题。比如我的代码里while (ptr sz (int)row[ptr] x) ptr;这个(int)row[ptr]看起来多余但能避免某些环境下 unsigned short 和 int 比较时的类型坑尤其当 x 是负数时。虽然这道题的 x 理论上是非负的但养成显式转换的习惯总没坏处。I/O 优化也很关键。这题输入输出量很大尤其是输出q 行每行 m 个数如果还用默认的 cout 而不关同步很容易 TLE。代码开头ios::sync_with_stdio(false); cin.tie(nullptr);这两行必须写。如果你担心输出仍然慢可以改用\n而不是endl因为 endl 会强制刷新缓冲区而\n不会。我上面的代码全部用的\n。5.3 暴力对拍流程遇到这种“思路好像对但不知道哪里写错”的题最好的方法就是写一个暴力程序对拍。我一般会写一个纯暴力的 generate 和 brute// 暴力程序n 很小 for (int i 1; i m; i) { for (int j 1; j m; j) { if (i j) continue; int dis 0; for (int p 0; p k; p) { if (a[i p] ! a[j p]) dis; } // 统计每个阈值 } }然后写一个脚本生成随机小数据比如 n 20q 10值域 [1, 5]分别跑暴力程序和优化程序比较输出。这个流程看着笨实际价值非常大。尤其这个题的核心难点是边界处理随机数据很快就能暴露出 idx 算错、d 循环边界不对、输出顺序反了等一系列问题。我实际对拍时最快遇到的一个 bug 就是预处理时只给 pre 数组算了前 n - d 项但是后面某个循环我却访问到了 pre[n]导致读到一个脏值。后来我干脆把这个循环写得更保守for (int t 1; t n - d; t) { pre[t] pre[t - 1] (a[t] a[t d]); }然后用到的查询区间永远在 [1, n - d] 内就没有再出过问题。6. 再多说一点个人体会这道题让我想起很多“序列窗口类”问题的通用套路不要一开始就枚举所有窗口对先看能不能固定一个相对位移把二维比较转成一维统计。一旦差值固定所有窗口对的比较路径就是一条规整的对角线这时候前缀和、差分、单调队列这些工具就能派上用场。C 实现本身没有什么高深技巧但内存和类型上的细节很考验经验。我第一次用 int 存 dist 的时候本地跑大样例直接爆内存后来改成 unsigned short 上三角存储才过。还有输出顺序我一开始按窗口输出结果题目要求按询问输出白调了半天。这些都是不实际提交就很难意识到的坑。如果你也正在刷这道题我强烈建议先写一个暴力版再去改优化版最后用对拍确认。这比看十篇题解都管用。等到你把 P6360 这个过程完整走一遍以后再遇到“两两比较 多组阈值查询”的题思路会顺很多。