2026/6/12/YZR笔记(逻辑思维)
课堂笔记：构造、数论、位运算与 MEX
0. 今日知识地图
| 模块 | 对应题目 | 核心方法 |
|---|---|---|
| 构造排列 | The 67th Permutation Problem | 从两端取数，按规律输出一个合法排列 |
| 数论构造 | The 67th OEIS Problem | 质数筛 + 相邻质数乘积构造 |
| 位运算暴力 | The 67th XOR Problem | 枚举两两异或，取最大值 |
| 排序 + MEX | Shifted MEX | 排序去重，找最长连续段 |
一、构造题：The 67th Permutation Problem
1. 题型特征
题目要求输出一个长度为 3n 的排列。
构造题的关键不是“搜索答案”，而是：
- 先观察样例和限制；
- 找到一种稳定的输出规律；
- 保证每个数只出现一次；
- 保证输出范围是
1 ~ 3n。
2. 最终思路
最终通过代码使用了“双指针构造”：
int l = 1, r = n * 3;
while (l < r) {
cout << l << " " << r << " " << r - 1 << " ";
l++;
r -= 2;
}
每次输出 3 个数：
- 当前最小的
l - 当前最大的
r - 当前次大的
r - 1
然后：
l++;
r -= 2;
这样每一轮刚好消耗 3 个不同的数。
3. 为什么不会重复？
初始时：
l = 1;
r = 3 * n;
每轮取：
l, r, r - 1
下一轮：
l 变成 l + 1
r 变成 r - 2
所以左边依次取：
1, 2, 3, ...
右边依次取：
3n, 3n-1, 3n-2, 3n-3, ...
左右两边不会撞在一起，直到刚好输出 3n 个数。
4. 关键代码
#include<bits/stdc++.h>
using namespace std;
int T, n;
int main() {
cin >> T;
while (T--) {
cin >> n;
int l = 1, r = n * 3;
while (l < r) {
cout << l << " " << r << " " << r - 1 << " ";
l++;
r -= 2;
}
cout << "\n";
}
return 0;
}
5. 易错点
今天这题尝试次数较多，主要问题集中在：
cnt更新规律不稳定，容易让数字重复或越界；- 没有从“每次消耗 3 个数”这个角度设计构造；
- 构造题不要靠随机试，最好先证明每个数是否只出现一次。
建议做构造题时先问自己三件事：
- 输出的数是否都在合法范围内？
- 是否每个数只出现一次？
- 是否一共输出了正确数量的数？
二、数论构造：The 67th OEIS Problem
1. 题型特征
题目要求构造一个长度为 n 的数列，使相邻两个数的 gcd 满足特定规律。
从最终代码可以看出，这题的核心是：
用质数制造相邻位置之间可控的最大公因数。
2. 核心构造
最终输出规律：
if (i == 1 || i == 2) cout << i << " ";
else cout << zs[i - 2] * zs[i - 1] << " ";
也就是：
a1 = 1
a2 = 2
a3 = 第1个质数 * 第2个质数 = 2 * 3 = 6
a4 = 第2个质数 * 第3个质数 = 3 * 5 = 15
a5 = 第3个质数 * 第4个质数 = 5 * 7 = 35
...
这样相邻两项会共享一个质因子。
例如：
1, 2, 6, 15, 35, 77, ...
相邻 gcd：
gcd(1, 2) = 1
gcd(2, 6) = 2
gcd(6, 15) = 3
gcd(15, 35) = 5
gcd(35, 77) = 7
刚好得到一串递增的质数或特殊起点。
3. 质数筛模板
这题需要先筛出足够多的质数。
int a[1001000], zs[1001000];
int cnt = 0;
a[0] = 1;
a[1] = 1;
for (int i = 2; i <= 1000000; i++) {
if (a[i] == 0) {
zs[++cnt] = i;
for (int j = i * 2; j <= 1000000; j += i) {
a[j] = 1;
}
}
}
含义：
a[i] == 0：当前i是质数；a[i] == 1：当前i不是质数；zs[cnt]：存第cnt个质数。
4. 完整关键代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
int T, n;
int a[1001000], zs[1001000];
signed main() {
a[0] = 1;
a[1] = 1;
int cnt = 0;
for (int i = 2; i <= 1000000; i++) {
if (a[i] == 0) {
zs[++cnt] = i;
for (int j = i * 2; j <= 1000000; j += i) {
a[j] = 1;
}
}
}
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
if (i == 1 || i == 2) cout << i << " ";
else cout << zs[i - 2] * zs[i - 1] << " ";
}
cout << "\n";
}
return 0;
}
5. 今日易错点
从提交记录看，这题中间出现过几个典型问题：
错误 1：筛法循环写错
错误倾向：
for (int j = i + a[i]; j <= 10000; j += a[i])
这里 a[i] 是标记数组，不是步长。筛倍数时步长应该是 i。
正确：
for (int j = i * 2; j <= 1000000; j += i)
错误 2：质数标记含义反了
建议统一记法：
a[i] == 0 表示还没有被筛掉，也就是质数
a[i] == 1 表示合数
并且一开始要写：
a[0] = a[1] = 1;
错误 3：乘法可能爆 int
最终代码用了：
#define int long long
这是必要的。因为质数乘质数可能比较大，普通 int 有溢出风险。
三、位运算：The 67th XOR Problem
1. 题型特征
给一个长度为 n 的数组，要求找出两个数异或后的最大值。
异或符号是：
^
例如：
5 ^ 3
表示 5 和 3 按二进制逐位异或。
2. 数据范围决定做法
这题 n 大约在 3105 级别，可以直接枚举两两组合。
时间复杂度：
O(n^2)
当 n ≈ 3000 时：
3000 * 3000 = 9,000,000
这个数量可以接受。
3. 核心代码
int ans = INT_MIN;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
ans = max(ans, a[i] ^ a[j]);
}
}
注意第二层循环从：
j = i + 1
开始，避免自己和自己异或，也避免重复枚举。
4. 完整关键代码
#include<bits/stdc++.h>
using namespace std;
int T, n, a[3110];
int main() {
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int ans = INT_MIN;
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
ans = max(ans, a[i] ^ a[j]);
}
}
cout << ans << "\n";
}
return 0;
}
5. 易错点
^是异或，不是乘方。- 如果题目要选两个不同位置，内层循环应从
i + 1开始。 - 看到
n <= 3000，优先考虑O(n^2)暴力，不要一上来想复杂数据结构。
四、排序 + MEX：Shifted MEX
1. 题型特征
题目和 MEX 有关。
MEX 指一个序列中没有出现过的最小非负整数。
例如：
MEX([1, 2, 0, 5]) = 3
MEX([1, 2, 4, 9]) = 0
这题允许整体平移数组，也就是所有数同时加上同一个 x。
目标是让平移后的数组 MEX 尽量大。
2. 核心转化
如果平移后想让：
0, 1, 2, ..., k-1
都出现，那么平移前数组中必须存在一段连续的数：
x, x+1, x+2, ..., x+k-1
所以问题转化为：
在原数组中找最长的连续整数段长度。
例如：
原数组：2 4 1 0 -1
排序后：-1 0 1 2 4
最长连续段：-1, 0, 1, 2
答案：4
3. 做法
- 排序；
- 跳过重复数字；
- 如果当前数等于前一个数
+1，连续长度加一； - 否则更新答案，重新开始计数。
4. 关键代码
sort(a + 1, a + n + 1);
a[n + 1] = -2e9;
int s = 1, ans = 1;
for (int i = 2; i <= n + 1; i++) {
if (a[i] == a[i - 1]) continue;
if (a[i] == a[i - 1] + 1) {
s++;
} else {
ans = max(ans, s);
s = 1;
}
}
cout << ans << "\n";
这里加了一个哨兵：
a[n + 1] = -2e9;
它的作用是强制最后一段连续段也被结算。
5. 完整关键代码
#include<bits/stdc++.h>
using namespace std;
int T, n;
int main() {
cin >> T;
while (T--) {
cin >> n;
int a[3010] = {0};
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
sort(a + 1, a + n + 1);
a[n + 1] = -2e9;
int s = 1, ans = 1;
for (int i = 2; i <= n + 1; i++) {
if (a[i] == a[i - 1]) continue;
if (a[i] == a[i - 1] + 1) {
s++;
} else {
ans = max(ans, s);
s = 1;
}
}
cout << ans << "\n";
}
return 0;
}
6. 今日易错点
易错点 1：重复数字不能打断连续段
例如：
1 1 2 3
最长连续段仍然是：
1, 2, 3
重复的 1 应该跳过：
if (a[i] == a[i - 1]) continue;
易错点 2：最后一段要记得更新答案
如果没有哨兵，循环结束后还要补一句：
ans = max(ans, s);
今天最终代码用的是哨兵写法，也可以。
五、今日整体复盘
1. 做得好的地方
- 4 道题最终都拿到了
100。 - 能从调试尝试中逐步修正方向。
- 对
O(n^2)暴力的判断比较准确，XOR 题很快通过。 - MEX 题最终抓住了“最长连续段”这个核心转化。
2. 需要加强的地方
1）构造题要先证明，再提交
构造题最怕“看起来像对的”。
提交前至少检查：
范围对不对？
数量对不对？
有没有重复？
能不能覆盖边界 n=1、n=2？
2）数论筛法要写熟
质数筛是基础模板，建议背熟下面这个版本：
vis[0] = vis[1] = 1;
for (int i = 2; i <= N; i++) {
if (!vis[i]) {
prime[++cnt] = i;
for (int j = i * 2; j <= N; j += i) {
vis[j] = 1;
}
}
}
特别注意：
j += i
不是 j += vis[i]，也不是 j += a[i]。
3）MEX 题常常要转化
看到 MEX，不一定直接模拟 MEX。
这题的关键不是找当前 MEX，而是问：
平移之后，怎样让
0,1,2,...尽量完整出现？
于是转化成了原数组中的最长连续段。
六、课后练习建议
必练 1：手写质数筛
要求不看模板，写出：
vis[0] = vis[1] = 1;
for (int i = 2; i <= N; i++) {
if (!vis[i]) {
prime[++cnt] = i;
for (int j = i * 2; j <= N; j += i) {
vis[j] = 1;
}
}
}
并回答：
vis[i] = 0表示什么？- 为什么
j从i * 2开始？ - 为什么步长是
i？
必练 2：排序后找最长连续段
给数组：
4 2 3 6
排序后：
2 3 4 6
最长连续段是：
2 3 4
答案是：
3
再练一个带重复的：
1 1 2 2 3 5
答案应该是：
3
因为最长连续段是：
1 2 3
必练 3：判断复杂度
如果 n <= 3000，两层循环大约是：
9 * 10^6
一般可以接受。
所以 XOR 最大值这类题可以直接：
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
ans = max(ans, a[i] ^ a[j]);
}
}
七、一句话总结
今天的重点不是单个语法点，而是四种常见竞赛思维：
构造：找规律并证明不重复
数论：用质数和 gcd 设计性质
位运算：根据数据范围选择 O(n^2)
MEX：把目标转化成最长连续段