这是什么： S8 那 12
道真题，每道一份完整注释的标程，外加「为什么这么写」和「你最可能写出的错版」。
每道题至少交过一次，才准翻到它那一节。
没交过就看，你拿走的是代码，丢掉的是「怎么想到」——那正是你们说想不通的东西。看懂一份标程只要 5 分钟，自己想出来要 25 分钟，而考场上给分的是后者。
📝 这册的正确用法是「对照」，不是「获取」。 把你自己的代码和标程并排放，问三个问题：
< 还是
<=？从 0 还是从 1？⚠️ 即使你已经 AC 了，也要看。 AC 只说明你的代码对，不说明它好。写法上的差距在 T1 看不出来，到 T3 就是能不能写完的差距。
📝 标程的验证边界，说在前面： 本册每份标程都在
g++ -std=c++14
下编译通过，并且喂入题面上的每一组官方样例、输出逐字一致。但样例过了不等于洛谷
AC——最终以你自己提交的结果为准。如果你发现标程挂了某个测试点，那是一次极好的对拍素材，把数据记下来拿到答疑窗口。
已经在正课讲过的三道不在本册：乘方 P8813、小苹果
P9748 见 L01，公路 P9749 见 L02。
| 序 | 题 | 题号 | 核心零件 | 难度 |
|---|---|---|---|---|
| 1 | 数字游戏 | P5660 | 字符串遍历 | 热身 |
| 2 | 扑克牌 | P11227 | 二维标记数组 | ⭐ |
| 3 | 优秀的拆分 | P7071 | 位运算 | ⭐ |
| 4 | 拼数 | P14357 | 计数数组 | ⭐ |
| 5 | 分糖果 | P7909 | 取模 + 分类讨论 | ⭐⭐ |
| 6 | 座位 | P14358 | 排名 + 蛇形坐标 | ⭐⭐ |
| 7 | 地图探险 | P11228 | 方向数组 + 模拟 | ⭐⭐ |
| 8 | 直播获奖 | P7072 | 计数数组 + 值域扫描 | ⭐⭐⭐ |
| 9 | 插入排序 | P7910 | 稳定性 + 按修改次数分摊 | ⭐⭐⭐ |
| 10 | 公交换乘 | P5661 | 队列 + 窗口有界 | ⭐⭐⭐ |
| 11 | 解密 | P8814 | 韦达定理 + 整数开方 | ⭐⭐⭐ |
| 12 | 一元二次方程 | P9750 | 分数化简 + 分类输出 | ⭐⭐⭐⭐（T3） |
题面只有一句话：长度为 8 的 01 串，数其中有几个 1。
📝 这题唯一的价值是走通考场流程。
它不考任何算法——但每年都有人在这种题上爆零，因为文件名写错、freopen
忘了恢复。把它当成一次流程演练，不是一道题。
⚠️ 别被「01 字符串」骗去想位运算。
它是字符串不是二进制数，s[0] 是字符
'0' 或 '1'，不是数字 0 或 1。
#include <bits/stdc++.h>
using namespace std;
int main() {
string s;
cin >> s; // 整串读入，长度固定为 8
int cnt = 0; // 计数器必须清零
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] == '1') { // 和字符 '1' 比，注意是单引号
cnt++;
}
}
cout << cnt << endl;
return 0;
}官方样例： 00010100 →
2；11111111 → 8。
(int)s.size()：size()
返回的是无符号数，和 int
比较时编译器会警告。养成习惯强转，以后写
i < s.size() - 1 时若 s
为空会得到一个天文数字，那才是真出事的地方。s.length() 也不用
strlen：size()
一个就够，少记一个词。if (s[i] == 1) cnt++; // 少了引号1 是整数 1，'1' 是字符（ASCII 值
49）。这样写编译能过、不报警告，但 cnt 永远是
0。编译过 ≠ 写对了。
n 张牌里可能有重复。要凑齐 52 张完整牌，手上重复的牌毫无用处，所以：
答案 = 52 − 手上不同牌的种数
「数不同的种数」= S3 的计数数组套路。花色 4 种、点数 13
种，开一个 bool have[4][13] 打勾就行。
📝
把字符映射成下标的通用技巧：把合法字符按顺序写成一个字符串，用
find 求下标。
string suit = "DCHS"; // D→0 C→1 H→2 S→3
int s = suit.find(card[0]);比写 13 个 else if 短得多，也不容易抄错。
#include <bits/stdc++.h>
using namespace std;
bool have[4][13]; // 全局数组自动清零
string suit = "DCHS"; // 花色：方片 草花 红桃 黑桃
string rankStr = "A23456789TJQK"; // 点数，注意 10 记作 T
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
string card;
cin >> card; // 每张牌是长度为 2 的字符串
int s = suit.find(card[0]); // 花色字符 → 0~3
int r = rankStr.find(card[1]); // 点数字符 → 0~12
have[s][r] = true; // 重复打勾也无所谓，还是 true
}
int cnt = 0;
for (int s = 0; s < 4; s++) {
for (int r = 0; r < 13; r++) {
if (have[s][r]) {
cnt++; // 数一共打了几个勾
}
}
}
cout << 52 - cnt << endl;
return 0;
}官方样例： 1 / SA →
51；4 / DQ H3 DQ DT → 49。
have 开在 main
外面：全局数组自动清零，省掉一次
memset。这是本册每份标程的统一做法。true
不用判断：have[s][r] = true; 比
if (!have[s][r]) have[s][r] = true;
更短且完全等价——能不写的判断就不写。int cnt = 0;
for (int i = 1; i <= n; i++) {
string card;
cin >> card;
cnt++; // 直接数张数
}
cout << 52 - cnt << endl;忘了去重。样例 1 只有一张牌，这样写照样输出 51 —— 样例 1 过了，样例 2 才挂。这是本册反复出现的模式：第一个样例往往盖不住 bug。
「拆成若干个互不相同的 2 的正整数次幂」——两个限定词都是钥匙。
所以整题就两行逻辑：n 是奇数输出
-1；否则从高位往低位，哪位是 1 就输出
1 << k。
📝 数据范围定循环上界：n ≤ 10⁷ < 2²⁴，所以 k 从 23 开始就够，不用管更高位。
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
if (n % 2 == 1) { // 奇数 → 二进制第 0 位是 1 → 必须用到 2^0
cout << -1 << endl;
return 0; // 直接结束，后面不用再判断
}
bool first = true; // 控制空格：第一个数前面不加空格
for (int k = 23; k >= 1; k--) { // 从大到小输出，k 从 1 开始（不含 2^0）
if ((n >> k) & 1) { // 取出第 k 位，S1 讲过的固定写法
if (!first) {
cout << " ";
}
cout << (1 << k); // 第 k 位对应的值就是 2^k
first = false;
}
}
cout << endl;
return 0;
}官方样例： 6 →
4 2；7 → -1；126 →
64 32 16 8 4 2。
first
标志控制空格：题目要求「相邻两个数之间用一个空格隔开」。用标志位比「先输出第一个再循环剩下的」更不容易写错，尤其在你还不知道第一个是哪个的时候。(n >> k) & 1 而不是
n & (1 << k)：两种都对，但前者结果直接是
0 或 1，可以放进任何布尔上下文；后者结果是 0 或
2ᵏ，一旦你想拿它去比较就容易出事。统一用前者，少一个决策。k >= 1 不是
k >= 0：这一个字符就是「正整数次幂」这条限制的全部实现。for (int k = 0; k <= 23; k++) { // 从小到大
if ((n >> k) & 1) cout << (1 << k) << " ";
}两处错：输出顺序反了（题目要从大到小），以及行末多一个空格。行末空格在洛谷上通常能过（会忽略行尾空白），但在正式评测里不一定——别赌，用
first 标志。
⚠️ 这题不是洛谷 P1093 那种「几个数拼起来比大小」，别按印象做。
它是：从字符串里挑出任意多个数字字符，按任意顺序拼成一个正整数，求最大值。
两步推理：
所以答案 = 把 s 里所有数字字符取出来、降序拼接。
📝 别真的去 sort。 |s| ≤
10⁶，但数字只有 0~9 十种——这是 S3
计数数组的标准信号：数一下每个数字出现几次，再从 9 到 0
依次打印，天然就是降序。O(n) 而不是 O(n log n)。
#include <bits/stdc++.h>
using namespace std;
int cnt[10]; // cnt[d] = 数字 d 出现了几次
int main() {
ios::sync_with_stdio(false); // |s| 可达 10^6，关掉同步加速读入
string s;
cin >> s;
for (int i = 0; i < (int)s.size(); i++) {
if (s[i] >= '0' && s[i] <= '9') { // 字母直接跳过
cnt[s[i] - '0']++; // 字符转数字：减去 '0'
}
}
string ans = ""; // 先拼进字符串，最后一次性输出
for (int d = 9; d >= 0; d--) { // 从 9 到 0 ⇒ 天然降序
for (int j = 1; j <= cnt[d]; j++) {
ans += (char)('0' + d); // 数字转字符：加上 '0'
}
}
cout << ans << endl;
return 0;
}官方样例： 5 →
5；290es1q0 → 92100（数字是
2,9,0,1,0，降序拼成 9 2 1 0 0）。
cout << d：10⁶ 次 cout
每次都要走一遍输出流的逻辑，拼成一个 string
一次输出快得多。输出量大的题，这个习惯值几十分。s[i] - '0' 和
'0' + d：字符与数字互转的一对反向操作，S1
和 B 班 L05 都讲过。记住它们成对出现。ios::sync_with_stdio(false)：S7
第四节讲过。⚠️ 加了之后就不能再混用
scanf/printf。sort(digits.begin(), digits.end(), greater<char>());不算错，但没必要——而且如果你把 10⁶ 个字符先塞进 vector
再排序，多花的时间和内存都是白给的。看到「值域只有十种」就该想到桶。
真正的错法是这个：
if (ans[0] == '0') { ... 特判前导零 ... }多余。 题目保证「包含至少一个 1~9 中的数字」，所以最高位一定不是 0。⚠️ 题面里每一句限制都是为了让你少写代码，不是为了让你多写。
先把题意翻译成数学：拿 k 块糖，每轮所有 n 人各拿一块，直到剩下不足 n 块。剩下的就是 k mod n。
所以要求的是：在 L ≤ k ≤ R 里，让 k mod n 最大。
n ≤ 10⁹、R ≤ 10⁹ ⇒ 不能枚举 k（S0
复杂度表：n ≤ 10⁹ 必须 O(√n)、O(log n) 或 O(1)）。要找规律。
📝 S5 的两条要点在这里同时用上：
a % n 的最大可能值是 n − 1a / n == b / n ⟺ a 和 b
落在同一段（同一个「整除块」）里于是分两种情况：
L / n < R / n）：那么区间里一定包含某个
n 的倍数减 1 的位置，能取到最大值 n − 1。L / n == R / n）：这一段里
k % n 随 k 单调递增，取右端点最好，答案是 R %
n。整题最后就是一个 if。
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, L, R; // 都到 10^9，虽然 int 勉强够，但乘除时容易翻车
cin >> n >> L >> R;
if (L / n < R / n) { // 跨段：区间里必有余数取到 n-1 的位置
cout << n - 1 << endl;
} else { // 同段：余数随 k 递增，取右端点
cout << R % n << endl;
}
return 0;
}官方样例： 7 16 23 →
6（16/7=2，23/7=3，跨段 → 7−1=6）；10 14 18 →
8（都在第 1 段 → 18%10=8）。
long long 而不是
int：这题的值都 ≤ 10⁹，int
装得下。但一旦你写出 L / n
之外的任何乘法就会溢出，而且改类型的成本是零。S7
第五节把「int
溢出」列为「本地对、评测机错」的第二大原因——能用
long long 就用。long long best = 0;
for (long long k = L; k <= R; k++) {
best = max(best, k % n);
}这是正确的暴力，能拿测试点 1~4 的分。
写它不丢人——S0
说过「先写个一定对但很慢的暴力」，那是策略不是安慰。但 R−L 可达 10⁹
时必然 TLE。
⚠️ 真正的错法是这个：
if (R - L >= n) cout << n - 1;
else cout << R % n;看起来也像「跨段判断」，但边界是错的：n=7、L=16、R=23 时 R−L=7 ≥ 7
恰好成立，蒙对了；换成 L=16、R=21（差 5 < 7）就会输出
21%7=0，而实际上 16..21 里 20%7=6 才是最大。用
L / n < R / n
直接判断「有没有跨过段边界」，比猜一个差值阈值可靠得多。
两步，互不相干，分开写就不会乱：
第一步：小 R 排第几名。 成绩互不相同 ⇒ 排名 = 比他高的人数 + 1。n×m ≤ 100，直接数一遍，O(n²) 完全够。不需要排序。
第二步：第 rk 名坐哪儿。 蛇形按列走，每列 n 个人：
c = (rk - 1) / n + 1off = (rk - 1) % n（从 0 开始数）r = off + 1r = n - off📝 「先减 1、算完再加
1」是所有下标换算题的通用手法。 排名是从 1
开始的，而除法取模是按从 0 开始设计的，所以先 rk - 1 转成 0
起点，算完再转回来。硬记「要不要 +1」一定会错。
#include <bits/stdc++.h>
using namespace std;
int a[105]; // n×m ≤ 100，开 105 留余量
int main() {
int n, m;
cin >> n >> m;
int total = n * m;
for (int i = 1; i <= total; i++) {
cin >> a[i];
}
int rk = 1; // 小 R 的排名，从 1 起
for (int i = 2; i <= total; i++) {
if (a[i] > a[1]) { // 成绩互不相同，不用考虑并列
rk++;
}
}
int c = (rk - 1) / n + 1; // 第几列：每 n 个人换一列
int off = (rk - 1) % n; // 在这一列里是第几个（从 0 数）
int r;
if (c % 2 == 1) {
r = off + 1; // 奇数列：从上往下
} else {
r = n - off; // 偶数列：从下往上
}
cout << c << " " << r << endl;
return 0;
}官方样例： 2 2 / 99 100 97 98 →
1 2；2 2 / 98 99 100 97 →
2 2；3 3 / 94 95 96 97 98 99 100 93 92 →
3 1。
rk 不叫
rank：<bits/stdc++.h> 里有个叫
std::rank 的东西，加上 using namespace std;
之后重名虽然能编译，但一旦你把它当函数名用就会看到莫名其妙的报错。避开标准库已有的名字：rank、count、time、next、prev、hash
都别用。rk
交接：如果把排名和坐标混在一个循环里算，蛇形那几个 ±1
会立刻乱掉。能拆的一定拆。int r;
if (c % 2 == 1) r = off + 1;
else r = n - off + 1; // 偶数列写成 n - off + 1差一错。用 n=2、rk=3 验一下：c=2、off=0，正确答案是第 2
行（偶数列从下往上，第 1 个就是最底下那行），n - off = 2
✓，而 n - off + 1 = 3 越界了。
📝 蛇形题永远用最小的例子手验一遍：n=2 的第 2
列只有两个位置，错不到哪去，一验就现原形。这就是 S7
第二节第 1 步。
这题没有算法，全是模拟。它考的是你能不能把题面的规则一字不差地翻译成代码。
规则原文就三句：
d = (d + 1) % 4，位置不变📝 方向数组是 L06/L07 就在用的零件，这里只是换了个编号顺序。 题目规定 d=0 东、1 南、2 西、3 北，那就照抄：
int dx[4] = {0, 1, 0, -1}; // 东 南 西 北，对应行的变化
int dy[4] = {1, 0, -1, 0}; // 对应列的变化⚠️ 千万别用你背熟的那套「上下左右」顺序。 顺序错了，右转就转到别的方向去了，而且样例 1 有可能照样过。
「经过的位置有几个」= 去重计数 → vis 数组，第一次踏上才
cnt++。
k ≤ 10⁶、T ≤ 5，一步一步模拟就是 5×10⁶ 次，完全来得及。不要试图找规律优化，这题就是让你老老实实模拟的。
#include <bits/stdc++.h>
using namespace std;
const int N = 1005; // n, m ≤ 1000
char g[N][N];
bool vis[N][N];
int dx[4] = {0, 1, 0, -1}; // d=0 东(y+1) 1 南(x+1) 2 西(y-1) 3 北(x-1)
int dy[4] = {1, 0, -1, 0};
int main() {
ios::sync_with_stdio(false);
int T;
cin >> T;
while (T--) { // 多组数据
int n, m, k;
cin >> n >> m >> k;
int x, y, d;
cin >> x >> y >> d;
for (int i = 1; i <= n; i++) {
string row;
cin >> row; // 整行读入，再逐个拆到二维数组
for (int j = 1; j <= m; j++) {
g[i][j] = row[j - 1]; // row 下标从 0，地图下标从 1，差 1
vis[i][j] = false; // 顺手清空，多组数据必须清
}
}
vis[x][y] = true; // 起点也算「经过」
int cnt = 1;
for (int step = 1; step <= k; step++) {
int nx = x + dx[d];
int ny = y + dy[d];
if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == '.') {
x = nx; // 条件成立：走一步，朝向不变
y = ny;
if (!vis[x][y]) { // 第一次踏上才计数
vis[x][y] = true;
cnt++;
}
} else {
d = (d + 1) % 4; // 条件不成立：右转，位置不变
}
}
cout << cnt << endl;
}
return 0;
}官方样例：
2
1 5 4
1 1 2
....x
5 5 20
1 1 0
.....
.xxx.
.x.x.
..xx.
x....输出 3 和 13。
vis
在每组数据的读图循环里顺手清空：多组数据不清数组是 CSP
的经典死法，而且本地跑单组数据永远发现不了（S7
第五节第 3 条）。把清空写进读入循环里，就不会忘。nx >= 1 && nx <= n && ny >= 1 && ny <= m && g[nx][ny] == '.'。⚠️
顺序不能换——先判越界再访问数组，反过来会先读到数组外的内存。C++
的 && 是短路求值，这个顺序是有意义的。while (T--)：多组数据的标准写法，比
for (int t = 1; t <= T; t++) 少一个变量。if (g[nx][ny] == '.' && nx >= 1 && nx <= n && ny >= 1 && ny <= m) {先访问了数组，再判越界。
本地可能不崩（读到的是相邻内存），交上去就是 RE 或者莫名其妙的 WA。这是
S7 第三节「数组越界」最阴的一种。
另一个：
cnt++; // 每走一步就加，不判 vis题目问的是不同位置的个数，走回头路不能重复计。样例 1 的机器人不走回头路，所以样例 1 照样输出 3——又是一个「第一个样例盖住 bug」的例子。样例 2 里机器人在末尾来回走了两趟，才把它暴露出来。
每读入一个成绩，就要立刻算出当前的分数线。朴素做法是每次把已有成绩排一次序，取第
need 名——那是 O(n² log n)，n = 10⁵ 时必挂。
📝 钥匙在题面这句闲话：「每个选手的成绩均为不超过 600 的非负整数」。
值域只有 601 种！这是 S3
计数数组的标准信号。做法变成：
cnt[x]++ 记录成绩 x 出现了几次（O(1)）cnt，累计人数第一次 ≥
need 时的那个分数就是分数线（O(601)）总复杂度 O(601 n) ≈ 6×10⁷，稳过。
⚠️ 计划获奖人数 max(1, ⌊p × w%⌋)
必须用整数算。 题面专门提示过：用 double 算
5 × 60% 可能得到 2.999999。写成
p * w / 100——C++
的整数除法自动向下取整，正是题目要的 ⌊⌋。
#include <bits/stdc++.h>
using namespace std;
int cnt[605]; // 成绩 0~600，开 605 留余量
int main() {
ios::sync_with_stdio(false);
int n, w;
cin >> n >> w;
for (int p = 1; p <= n; p++) { // p = 已评出的人数
int x;
cin >> x;
cnt[x]++; // 边读边加，不用存数组
int need = p * w / 100; // 整数乘除，自动向下取整
if (need < 1) {
need = 1; // 题目要求的 max(1, ...)
}
int sum = 0;
int line = 0;
for (int s = 600; s >= 0; s--) { // 从高分往低分累加
sum += cnt[s];
if (sum >= need) { // 人数够了，当前分数就是分数线
line = s;
break;
}
}
if (p > 1) {
cout << " "; // 答案之间一个空格
}
cout << line;
}
cout << endl;
return 0;
}官方样例：
10 60 / 200 300 400 500 600 600 0 300 200 100 →
200 300 400 400 400 500 400 400 300 300。
p * w / 100 不写成
p * (w / 100)：后者里 w / 100 先算，w
≤ 99 所以恒等于 0，整个式子永远是 0。⚠️
整数除法不满足结合律，位置一动答案就变。cnt，成绩本身读完就可以丢。少一个 10⁵
的数组，也少一个出错的地方。sum >= need 用 >= 不用
==：因为成绩相同的人并列获奖，累加时可能一下子从 3
跳到
6，永远等不到恰好相等。这就是题面「实际获奖人数可能比计划中多」那句话的全部含义。double need = p * w / 100.0;
int k = (int)need;题面明确警告过：浮点算 5 × 60% 可能是 2.999999，取整变成
2，分数线就错了。题目专门写一段提示的地方，就是出题人埋的雷。
另一个：
for (int s = 0; s <= 600; s++) { // 从低分往高分扫方向反了。分数线是前 need 名的最低分，必须从高分往低分累加。这样写样例第一个数就不对，属于交之前就能自己发现的错——前提是你真的跑了样例。
⚠️ 这题的考点不是「手写插入排序」。 题面给你伪代码是为了定义一件事：排完之后，值相同的元素谁在前面。
看伪代码的关键一行：
if (a[j] < a[j-1]) { 交换 }只有严格小于才交换，相等时不动 ⇒ 这个插入排序是稳定的 ⇒
排序后的顺序 = 按 (值, 原下标) 双关键字从小到大排序的顺序
这就是 S2
讲的「把原下标当末位关键字」。题面那句「虽然此时 a₂ =
a₃，但是我们不能将其视为相同的元素」就是在提示这一点。
接下来是复杂度。 n ≤ 8000，Q ≤ 2×10⁵ —— 每次询问都 O(n) 数一遍是 1.6×10⁹，超时。
📝 钥匙又是一句闲话：「类型 1 的操作次数不超过 5000」。
修改很少、询问很多 ⇒ 把功夫全花在修改上，让询问变成 O(1)：
ord，以及每个下标的名次 pospos[x]，O(1)ord
里删掉、改值、再插回正确位置、重算 pos，O(n)总代价 5000 × O(8000) ≈ 4×10⁷，稳过。
#include <bits/stdc++.h>
using namespace std;
const int N = 8005;
int n, Q;
int val[N]; // val[i] = 第 i 个元素当前的值
int ord[N]; // ord[r] = 排名第 r 位的是哪个下标
int pos[N]; // pos[i] = 第 i 个元素排第几位（ord 的反函数）
bool cmp(int i, int j) { // 双关键字：先比值，值相同比原下标
if (val[i] != val[j]) {
return val[i] < val[j];
}
return i < j; // 这一行就是「稳定」的全部实现
}
int main() {
ios::sync_with_stdio(false);
cin >> n >> Q;
for (int i = 1; i <= n; i++) {
cin >> val[i];
ord[i] = i;
}
sort(ord + 1, ord + n + 1, cmp); // 初始排一次
for (int r = 1; r <= n; r++) {
pos[ord[r]] = r; // 由 ord 反推 pos
}
while (Q--) {
int op;
cin >> op;
if (op == 1) { // 修改：至多 5000 次，可以慢
int x, v;
cin >> x >> v;
for (int r = pos[x]; r < n; r++) {
ord[r] = ord[r + 1]; // 先把 x 从有序数组里删掉（整体前移）
}
val[x] = v; // 改值一定要在找插入位置之前
int q = n; // 默认插到最后
for (int r = 1; r < n; r++) {
if (cmp(x, ord[r])) { // 找到第一个「排在 x 后面」的位置
q = r;
break;
}
}
for (int r = n; r > q; r--) {
ord[r] = ord[r - 1]; // 给 x 腾位置（整体后移）
}
ord[q] = x;
for (int r = 1; r <= n; r++) {
pos[ord[r]] = r; // 重算名次
}
} else { // 询问：O(1)
int x;
cin >> x;
cout << pos[x] << endl;
}
}
return 0;
}官方样例：
3 4 / 3 2 1 / 2 3 / 1 3 2 / 2 2 / 2 3 → 1
1 2。
ord 和 pos
是一对互逆的映射：ord[pos[i]] == i
恒成立。维护两个数组听着麻烦，但询问 O(1) 全靠
pos，修改时定位 全靠
pos[x]。这一对是排序类题目的常用组合，值得记住。val[x] = v;
写在删除之后、查找之前：顺序错了就完蛋——如果先改值再删除，pos[x]
指向的位置已经和新值不匹配；如果改值在查找之后，找到的插入点是按旧值算的。这三行的顺序是这道题最容易写错的地方。cmp 里的
return i < j;：⚠️ S2
讲过，cmp 在相等时必须返回
false。这里因为加了下标这个末位关键字，i
和 j
不可能相等（同一个元素不会和自己比），天然满足。这正是「拿原下标当末位关键字」的另一个好处。// 每次询问都重新数一遍
int rk = 1;
for (int i = 1; i <= n; i++) {
if (val[i] < val[x] || (val[i] == val[x] && i < x)) rk++;
}
cout << rk << endl;这是正确的暴力，能拿测试点 1~13 的分（n, Q ≤
1500）。 照 S0
的策略，写不出正解时先把它交上去，50 分左右到手。⚠️
别因为知道它会 TLE 就不写。
真正的错法是这个：
sort(b + 1, b + n + 1); // 只按值排序，不带原下标值相同时 sort
的顺序是不确定的，本地和评测机可能给出不同结果 —— S7
第五节第 4 条说的就是这个。样例里
a₂ = a₃ = 2，这一版有一半概率输出
1 2 1。能跑对一次，不代表下次还对。
规则照抄就行，难点只有一个：怎么快速找到「最早获得的、还没用过的、票价 ≥ 本次公交票价的、还没过期的」那张优惠票。
朴素做法是每坐一次公交就从头扫一遍所有优惠票，n = 10⁵ 时最坏 O(n²)。
📝 钥匙藏在两句话里：
时间是互不相同的整数，而有效窗口只有 45 分钟宽 ⇒ 任何时刻，还没过期的优惠票最多只有 46 张！
所以：用一个 head
指针，每次先把已经过期的票永久跳过（head 只增不减），然后从
head 扫到 tail——这段最多 46
个元素。总复杂度 O(46n)，稳过。
⚠️ 优先用最早的那张：从 head
往后扫，第一个满足条件的就是最早的，直接用。别想复杂。
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int price[N]; // 每张优惠票对应的地铁票价
int tim[N]; // 每张优惠票的获得时刻
bool used[N]; // 这张票用掉了没有
int main() {
ios::sync_with_stdio(false);
int n;
cin >> n;
long long cost = 0; // 总花费，price ≤ 1000 × 10^5 条，用 long long 稳妥
int head = 1, tail = 0; // 优惠票队列的左右端（都是闭区间）
for (int i = 1; i <= n; i++) {
int type, p, t;
cin >> type >> p >> t;
if (type == 0) { // 坐地铁：付钱，并获得一张优惠票
cost += p;
tail++;
price[tail] = p;
tim[tail] = t;
used[tail] = false;
} else { // 坐公交：先找票
while (head <= tail && t - tim[head] > 45) {
head++; // 过期的票永久丢弃，head 只增不减
}
int found = -1;
for (int j = head; j <= tail; j++) { // 这一段最多 46 个
if (!used[j] && price[j] >= p) {
found = j; // 第一个满足的就是最早的
break;
}
}
if (found == -1) {
cost += p; // 没票可用，自己掏钱
} else {
used[found] = true; // 用掉这张票，不花钱
}
}
}
cout << cost << endl;
return 0;
}官方样例： 样例 1 → 36；样例 2 →
32。
tim 不叫
time：time 是 C
标准库的函数名，<bits/stdc++.h>
一并引入了。重名之后编译器给的报错会指向一个你根本没写过的地方。和第
6 题的 rank 是同一类坑。head
只增不减：这是复杂度能降下来的关键。已经过期的票永远不会再变有效，所以可以永久跳过。「单调指针」这个想法在很多题里都会再遇到。used
数组而不是真的从队列里删除：中间被用掉的票没法从数组里高效删除，打个标记跳过就行。扫描长度反正有
46 的上界，多跳几个不影响。if (t - tim[j] <= 45 && !used[j] && price[j] >= p) {条件本身没错，但如果不维护 head、每次都从 1
开始扫，最坏就是 O(n²)。样例只有 6
条记录，本地一瞬间出结果——这是典型的「样例秒过、评测机
TLE」，属于 S7 第四节。
另一个：
if (price[j] > p) // 写成严格大于题面说的是「票价不超过地铁票价的公交车」，即
公交票价 ≤ 地铁票价，对应
price[j] >= p。样例 2 的第六条记录恰好是
7 >= 7
的相等情况——出题人专门设了这一条来卡你。
题目给的两个式子：
n = p × q
e × d = (p − 1)(q − 1) + 1把第二个展开：e·d = pq − p − q + 1 + 1 = n − (p + q) + 2，于是
p + q = n − e·d + 2（记作 m），p × q = n
已知两个数的和与积，求这两个数 —— 这就是韦达定理：p
和 q 是方程 t² − m·t + n = 0 的两个根。
Δ = m² − 4n
p = (m − √Δ) / 2 q = (m + √Δ) / 2有解的条件（四条缺一不可）：
Δ ≥ 0√Δ 是整数（否则 p、q 不是整数）m − √Δ 是偶数（否则除以 2 除不尽）p ≥ 1（题目要正整数）⚠️ n ≤ 10¹⁸ ⇒ 必须 long long，而且
sqrt 不能直接用。 sqrt 返回
double，只有 53 位有效精度，对 10¹⁸
级别的数会算错最后几位。用 S5
里那个先估算再左右调整的 mySqrt。
#include <bits/stdc++.h>
using namespace std;
// S5 的整数开方：先用 double 估，再左右微调回准确值
long long mySqrt(long long x) {
if (x < 0) {
return -1;
}
long long r = (long long)sqrt((double)x);
while (r > 0 && r * r > x) {
r--; // 估大了往回退
}
while ((r + 1) * (r + 1) <= x) {
r++; // 估小了往前进
}
return r;
}
int main() {
ios::sync_with_stdio(false);
int k;
cin >> k;
while (k--) {
long long n, d, e;
cin >> n >> d >> e; // ⚠️ 输入顺序是 n, d, e，不是 n, e, d
long long m = n - e * d + 2; // m = p + q
if (m <= 0) {
cout << "NO" << endl;
continue;
}
long long delta = m * m - 4 * n;
if (delta < 0) { // 条件 1
cout << "NO" << endl;
continue;
}
long long s = mySqrt(delta);
if (s * s != delta || (m - s) % 2 != 0) { // 条件 2、3
cout << "NO" << endl;
continue;
}
long long p = (m - s) / 2;
long long q = (m + s) / 2;
if (p < 1 || p * q != n) { // 条件 4，外加一次兜底验算
cout << "NO" << endl;
continue;
}
cout << p << " " << q << endl; // p ≤ q 天然成立
}
return 0;
}官方样例： 10 组询问，输出 2 385 /
NO / NO / NO / 11 78
/ 3 241 / 2 286 / NO /
NO / 6 88。
n, d, e：题目描述里说「给定 n, e,
d」，但输入格式那一节写的是「第 i 行三个正整数 nᵢ, dᵢ,
eᵢ」。这题里 e 和 d 只以乘积 e·d
的形式出现，所以读反了也不影响答案——但下次遇到不对称的题就会送命。以输入格式那一节为准，永远。p * q != n
的兜底验算：数学上前三个条件已经够了，但这一行的成本是零，能挡住一切因为开方或溢出导致的意外。便宜的验算就该写。mySqrt 里两个 while
都要有：double
的误差可能偏大也可能偏小，只写一边就会漏。long long s = (long long)sqrt(delta);
if (s * s != delta) { cout << "NO" << endl; continue; }直接用 sqrt。n ≤ 10⁹ 的小测试点全过，10¹⁸
的大测试点开始零星错——因为 double 在 10¹⁸
量级的间隔已经大于 1 了。这是 S7
第五节「本地对、评测机错」里最难查的一种，因为它只在大数据上错，而你本地只跑样例。
另一个：
long long m = n - e * d + 2; // 用 int 存 e 和 de × d 可达 10¹⁸，int
早就爆了。读进来就用
long long，别等到算的时候才想起来转。
⚠️ 这是 T3，难点全在输出格式，不在数学。 如果时间紧，先保证前 11 题，这题最后做。
第一步：统一符号。 若 a < 0，把
a, b, c 同时取反——方程的解不变，但之后「较大的根」就固定是
(−b + √Δ) / (2a)，省掉一次分类讨论。
📝 这是竞赛里极常用的一招：先把输入规范化，再写主逻辑。
第二步：算 Δ = b² − 4ac。 Δ < 0 → 输出
NO。
第三步：把 √Δ 拆成 k√r 的形式，其中 r
不含平方因子。枚举 i 从 1 到 √Δ，记下最大的满足
i² | Δ 的 i：
k = i，r = Δ / i²|a|,|b|,|c| ≤ 1000 ⇒ Δ ≤ 10⁶ + 4×10⁶ = 5×10⁶ ⇒ i 最多到 2236，T ≤ 5000 ⇒ 总共约 10⁷ 次，来得及。
第四步：分类输出。
−b / (2a)(−b + k) / (2a)q₁ + q₂√r，其中
q₁ = −b/(2a)、q₂ = k/(2a)
q₁ ≠ 0 时先按分数输出 q₁，再输出一个
+q₂ 约分成 c₂/d₂ 后，按四种情况输出#include <bits/stdc++.h>
using namespace std;
long long gcdLL(long long x, long long y) { // S5 的辗转相除
if (y == 0) {
return x;
}
return gcdLL(y, x % y);
}
// 按题目要求输出既约分数 p/q（保证 q > 0；q == 1 时只输出 p）
void printFrac(long long p, long long q) {
if (q < 0) { // 把负号统一挪到分子上
p = -p;
q = -q;
}
long long g = gcdLL(llabs(p), q); // 用 |p| 求 gcd，避免负数搅局
p /= g;
q /= g;
if (q == 1) {
cout << p;
} else {
cout << p << "/" << q;
}
}
int main() {
ios::sync_with_stdio(false);
int T;
long long M;
cin >> T >> M;
while (T--) {
long long a, b, c;
cin >> a >> b >> c;
if (a < 0) { // 规范化：强制 a > 0，之后较大根固定是 (-b+√Δ)/(2a)
a = -a;
b = -b;
c = -c;
}
long long delta = b * b - 4 * a * c;
if (delta < 0) {
cout << "NO" << endl;
continue;
}
if (delta == 0) { // 两根相等，是有理数
printFrac(-b, 2 * a);
cout << endl;
continue;
}
long long k = 1, r = delta; // 把 √Δ 拆成 k√r，r 不含平方因子
for (long long i = 1; i * i <= delta; i++) {
if (delta % (i * i) == 0) {
k = i; // 循环到最后留下的就是最大的 i
r = delta / (i * i);
}
}
if (r == 1) { // √Δ 恰好是整数 k，根是有理数
printFrac(-b + k, 2 * a);
cout << endl;
continue;
}
if (-b != 0) { // q1 ≠ 0 才输出，然后补一个加号
printFrac(-b, 2 * a);
cout << "+";
}
long long c2 = k, d2 = 2 * a; // q2 = k / (2a)，先约分
long long g = gcdLL(c2, d2);
c2 /= g;
d2 /= g;
if (c2 == 1 && d2 == 1) {
cout << "sqrt(" << r << ")" << endl;
} else if (d2 == 1) {
cout << c2 << "*sqrt(" << r << ")" << endl;
} else if (c2 == 1) {
cout << "sqrt(" << r << ")/" << d2 << endl;
} else {
cout << c2 << "*sqrt(" << r << ")/" << d2 << endl;
}
}
return 0;
}官方样例（9 组）：
1
NO
1
-1
-1/2
12*sqrt(3)
3/2+sqrt(5)/2
1+sqrt(2)/2
-7/2+3*sqrt(5)/2printFrac
独立成函数：有理数要输出三次（Δ=0、r=1、q₁），写成函数就只有一份约分逻辑。⚠️
凡是同样的输出格式出现两次以上，一定抽成函数——否则改一处漏一处，是
T3 丢分的头号原因。if (a < 0) 全部取反：一行换掉一整套分类讨论。看到「较大的根」这种依赖符号的要求，先想能不能把符号规范掉。break：因为要的是最大的
i，所以一直循环到底，最后留下的自然是最大的。写成从大到小然后
break 也行，但这样少一行。llabs 不是
abs：abs 在 C++ 里对
long long 的重载在某些编译器上会悄悄退化成 int
版本，把大数截断。对 long long 取绝对值统一用
llabs。double x = (-b + sqrt(delta)) / (2 * a);
printf("%.6f", x);这题要的是精确的分数和根式，不是小数。用浮点数从第一步就走错了方向。⚠️ 看到题面里出现「gcd」「既约」「p/q」这些词，就说明它要的是精确表示。
另一个：
if (b != 0) { printFrac(-b, 2 * a); cout << "+"; }条件写成了 b != 0。这里 q₁ = −b/(2a)，它是否为 0
取决于 -b 是否为 0——恰好和 b != 0
等价，所以这一版碰巧是对的。但如果 q₁
的表达式再复杂一点，这种「判断原料而不判断结果」的写法就会出错。养成判断你真正要输出的那个量的习惯。
📝 把每道题的「我的写法 vs 标程」的差异记进你的卡点记录本，格式建议：
| 题 | 我卡在哪 | 标程和我差在哪 | 下次能不能自己想到 |
|---|---|---|---|
第 7 次课复盘时，这张表能直接告诉你：你缺的是知识（回去看
S1–S6），还是缺「怎么想到」（多做
S9
的限时训练），还是缺写法（继续对照本册）。这三种缺口的补法完全不同，别用错药。
⚠️ 最后一遍：看懂标程和写得出标程之间隔着很远。 每对照完一题，关掉这一页，从空文件重写一遍。写得出来才算过。