企业官网建设流程全解析

今天这道打卡题是洛谷 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 = 1，m = 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 = 3：

b[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 和窗口 3，i = 1，k = 2：

same = 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 和窗口 4，i = 2：

same = 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_{d=1}^{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 如果上到 10000，m 也可能接近 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_{t=1}^{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; vector<int> a(n + 1); for (int i = 1; i <= n; i++) cin >> a[i]; int m = n - k + 1; // 窗口数量 vector<int> 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); }; vector<unsigned short> dist(1ULL * m * (m - 1) / 2); vector<int> 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 个窗口的答案 vector<vector<unsigned short>> ans(q, vector<unsigned short>(m)); vector<int> 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)，这肯定不行。

我的做法是：

1. 把询问按阈值 x 从小到大排序；
2. 对每个窗口 i，把窗口 i 到其他所有窗口的距离拿出来排个序；
3. 因为询问已经从小到大排好序了，所以可以用一个指针 ptr 在这行有序距离上单调移动；
4. 指针指到哪里，说明有多少个距离小于等于当前阈值 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 输出顺序和答案矩阵

答案矩阵我开成：

vector<vector<unsigned short>> ans(q, vector<unsigned 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 - 1，m 不超过 10000，unsigned 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++ 的vector<unsigned 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 <= 20，q <= 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 这个过程完整走一遍，以后再遇到“两两比较 + 多组阈值查询”的题，思路会顺很多。