S8 真题分级提示

输入是字符串，不是数字。别想着用取模拆位——直接用 string 读进来，一个字符一个字符看。

判断条件是 s[i] == '1'——单引号的字符 '1'，不是数字 1。这是 L05 讲过的 char 与 int 的区别。

读入 string s，for 遍历每个字符，if (s[i] == '1') cnt++，输出 cnt。

这题本身没有任何难度。它的真正用途是让你把整套流程完整走一遍：建题目文件夹、写 freopen、造 .in 文件、检查 .out。如果这一步就卡住，先回去看 freopen函数用法教程.md——考场上这套流程出错，题做对了也是 0 分。

先把问题翻译一下：答案 = 52 − （手上不同牌的种数）。重复的牌一点用都没有。

所以真正要算的是"去重之后有几张"。

每张牌是两个字符：花色 ∈ D C H S，点数 ∈ A 2 3 4 5 6 7 8 9 T J Q K。

问题变成：怎么把一张牌变成数组下标？ 想想 S3 里"拿数值当下标"的做法——你需要把字符映射成 0 开始的编号。

开 bool vis[4][13]（全局，自动清零）。

映射办法：把 "DCHS" 和 "A23456789TJQK" 各存成一个字符串，用 find 查出字符的位置就是编号。例如 string suits = "DCHS"; int a = suits.find(s[0]); 得到 0~3。点数同理得到 0~12。

读一张就 vis[a][b] = true。最后双重循环数有多少个 true，答案 = 52 - 个数。

⚠️ 用 cin >> s 读一个长度为 2 的 string，别用 char 一个个读——空格和换行会给你惊喜。

2 的正整数次幂是 2, 4, 8, 16, 32…，它们有一个共同点。

想清楚这个共同点，你就能立刻判断出哪一类 n 一定拆不出来。先把这件事想明白，再想怎么拆。

它们全是偶数。若干个偶数相加还是偶数，所以 n 是奇数就直接输出 -1。

n 是偶数时呢？想想 S1：任何正整数写成二进制后，就是若干个不同的 2ᵏ 相加。而 n 是偶数保证了它二进制的第 0 位是 0——也就是永远不会用到 2⁰，正好符合题目要求。

所以：拆分方式就是 n 的二进制表示，而且它唯一。

1. if (n % 2 == 1) { 输出 -1; return 0; }
2. 否则从高位往低位扫。n ≤ 10⁷ < 2²⁴，所以 k 从 23 倒着数到 1 就够。
3. if ((n >> k) & 1) cout << (1 << k) << " ";

⚠️ 题目要求从大到小输出，所以 k 必须从大往小循环。 ⚠️ 位运算记得套括号（S1 坑 1）。

两个问题按顺序问自己：

1. 位数多的数和位数少的数，哪个大？→ 所以该挑多少个数字？
2. 如果全挑上，会不会出现"最高位是 0"的问题？

1. 位数越多越大，所以把所有数字字符全挑上。
2. 全挑上之后降序排列，最高位就是最大的那个数字。题目保证至少有一个 1~9 的数字，所以最高位一定不是 0，没有前导零的问题。

于是答案就是：把 s 里所有数字字符降序排一遍，直接输出。

用 S3 的计数数组：int cnt[10]，扫一遍 s，是数字就 cnt[s[i] - '0']++。

然后 for (int v = 9; v >= 0; v--)，每个 v 输出 cnt[v] 次。

⚠️ |s| 可以到 10⁶。不要用 ans = ans + 字符 这样一点点拼字符串——每次拼接都在复制整个字符串，会超时。要么直接 cout 输出（并在 main 开头加 ios::sync_with_stdio(false);），要么先把结果填进一个 char 数组再一次输出。

先把题意翻译成一个式子：你最后得到的是 k % n。所以要求的是 k 在 [L, R] 里取值时，k % n 的最大值。

k 能到 10⁹，所以绝对不能把 k 从 L 试到 R（回想 L01 的复杂度预算表）。

那就换个问法：k % n 最大能是多少？什么样的 k 能取到那个最大值？

k % n 的上限是 n - 1，在 k 恰好是"n 的倍数减 1"时取到。

所以问题变成：区间 [L, R] 里存不存在这样的数？

这等价于问：L 和 R 是不是落在同一个"长度为 n 的段"里。段的编号怎么算？见 S5 的第二条 📝。

• 若 L / n != R / n：区间跨过了至少一个 n 的倍数，那么"n 的倍数减 1"一定在区间内，答案 n - 1。
• 否则：L 和 R 在同一段里，这段内 k % n 随 k 单调递增，答案 R % n。

整道题就一个 if。用题目样例验算一遍再交：

• n=7, L=6, R=20 → 6/7=0，20/7=2，不等 → 答案 6（= n−1）✓
• n=10, L=14, R=18 → 都是 1，相等 → 答案 18%10 = 8 ✓

拆成两个独立的小问题：

1. R 的成绩排第几名？
2. 第 pos 名坐在哪个座位？

两个问题分开解决，别混在一起想。

第 1 问：成绩互不相同，所以根本不用排序——直接数"有多少个人的成绩比 R 高"，加 1 就是名次。

第 2 问：每列坐 n 个人。第 1~n 名在第 1 列，第 n+1~2n 名在第 2 列……所以列号由 (pos-1) / n 决定。至于行号，要分奇数列（从上往下）和偶数列（从下往上）两种情况。

设 pos 为名次（从 1 开始）：

• 列号 c = (pos - 1) / n + 1
• 在这一列里排第几个：t = (pos - 1) % n + 1
• c 是奇数 → r = t（从上往下）
• c 是偶数 → r = n - t + 1（从下往上）

输出 c 和 r。

n, m ≤ 10，怎么写都不会超时——这题考的纯粹是"把规则翻译成公式"。写之前先在纸上画一个 3 行 3 列的表，把 1~9 号填进去，再拿公式逐个验证：pos=4 应该落在第 2 列第 3 行，pos=6 应该落在第 2 列第 1 行。对上了再动手。

📝 实在推不出公式也有退路：n, m ≤ 10 意味着最多 100 个座位，直接开个二维数组按规则一个个填进去，填完再找 R 在哪。慢是慢，但一样满分——这就是 L01 说的"暴力是你的朋友"。

⚠️ 这题不是搜索。 别看见网格就上 DFS/BFS——机器人的路线是完全确定的，没有"选择"，你只要照着规则老老实实走 k 步。

这叫模拟，是 L01 的内容。搜索是"试所有可能"，模拟是"照做"。

方向数组照搬 L06/L07，但顺序必须严格按题目的编号排：0=东、1=南、2=西、3=北。

东是列 +1，南是行 +1，西是列 −1，北是行 −1，所以 dx[4] = {0, 1, 0, -1}、dy[4] = {1, 0, -1, 0}。

排对了之后，"右转"就是漂亮的一行：d = (d + 1) % 4。

开 bool vis[1005][1005] 记录到过的格子，起点也要标记并计数。

循环 k 次：

1. nx = x + dx[d]; ny = y + dy[d];
2. 若 nx, ny 在界内 且 是空地 → x = nx; y = ny;，若 !vis[x][y] 则标记并 cnt++
3. 否则 d = (d + 1) % 4

⚠️ 多组数据（T ≤ 5），每组开始前 vis 必须清零，否则上一组的痕迹会污染这一组。这是多测题最常见的死法。 ⚠️ k ≤ 10⁶，直接模拟 10⁶ 步完全来得及，不需要找循环节。

最直接的想法：每公布一个成绩，就把已公布的所有成绩排个序，取第 k 名。

先算一下这个做法的复杂度，再对照 L01 的预算表看看 n = 10⁵ 时过不过得去。

（算完你会发现过不去。那就回头找题面里被你忽略的那句话。）

每次重排是 O(n log n)，做 n 次就是 O(n² log n)，远超 10⁸。

被忽略的那句话是："所有成绩都是不超过 600 的非负整数"。值域只有 601 个值——这是在明示你用 S3 的计数数组。

开 cnt[0..600]，公布一个成绩就 cnt[x]++，完全不需要排序。那怎么求第 k 名的分数？从 600 往下累加个数，累加值第一次 ≥ k 时的那个分数就是。

维护 int cnt[605]，已公布个数 p。每读入一个成绩 x：

1. cnt[x]++; p++;
2. int k = max(1, p * w / 100); ⚠️ 纯整数运算——题面专门提醒过，写成 p * w / 100，不要出现 0.01 或 double，浮点误差会让你在某些点上差一名
3. 从 600 往 0 扫：sum += cnt[i]，一旦 sum >= k 就输出 i 并 break

复杂度：单次扫最多 601 步，总共 601 × 10⁵ ≈ 6×10⁷，稳过。

📝 这就是 S3 里说的"边加边查"：计数数组真正的价值不是排序快，而是新来一个数只要 O(1) 更新，不用把整个序列重排。

先把修改和查询都放一边，只回答一个问题：

不真的去跑那段插入排序，你能直接算出"原来第 x 个元素最终在第几位"吗？

（提示的提示：去读一遍题面给的伪代码，注意它的交换条件是"严格小于"还是"小于等于"。这个细节是整道题的钥匙。）

伪代码只在严格小于时才交换 → 两个相等的元素永远不会互换 → 这个插入排序是稳定的（见 S2）。

所以"插入排序后的位置"完全等价于：按 (值升序, 原下标升序) 双关键字排序后的排名。

问题于是变成一个干净的形式：维护一个序列，支持"改某个值"和"查某个元素的排名"。

关键在读懂这句数据范围：Q 到 2×10⁵，但修改最多只有 5000 次。

出题人是在告诉你：修改可以很慢，查询必须很快。

所以做法是：维护一张表 pos[i] = 原第 i 个元素当前排在第几位。

• 查询：直接输出 pos[x]，O(1)
• 修改：值变了，重新算一遍 pos 表

重算的办法：把 (值, 原下标) 存成结构体数组，用 S2 的双关键字 cmp 排一遍，然后 pos[b[j].idx] = j + 1。修改只影响一个元素，所以更省的做法是只把那个元素在有序序列里挪到正确位置（O(n) 的一次插入），不必整个重排。

⚠️ 先把"每次修改都整个重排"的版本写对，确认样例过了、拿到部分分，再去优化。这是 L01 的部分分策略。

先把规则拆成两件互不相干的事：

• 什么时候产生券：坐地铁 → 产生一张券，记下它的面值（= 这次地铁票价）和产生时间
• 什么时候消耗券：坐公交 → 找一张可用的券用掉；找不到就付钱

分开写，别混在一起。

"可用"要同时满足三个条件，一个都不能漏：

1. 这张券还没被用过
2. 没过期：t_公交 − t_地铁 ≤ 45
3. 面值够：券的面值 ≥ 公交票价

题目说优先用最早得到的，而记录本来就按时间顺序给你，所以"从前往后找第一张满足这三条的券"就是对的。

用三个数组（或一个 vector 存结构体）按产生顺序记下每张券的：面值、时间、是否已用。

坐公交时从前往后扫，找到第一张满足三条件的就标记为已用、这次不花钱；扫完没找到就 ans += 票价。

⚠️ 这个写法是 O(n²)，n = 10⁵ 会超时。但它能拿到 30% 的部分分（n ≤ 1000 那一档）——先把它写对，这是 L01 说的"先保证暴力分到手"。

优化方向：维护一个"起始指针" head。因为记录按时间递增，一旦某张券对当前这次公交已经过期，它对后面所有次公交也永远过期，可以让 head 直接跳过它，再也不看。

⚠️ 注意区分两种跳过：过期的券可以推 head 永久跳过；已用但没过期的券不能推 head 越过去（它后面可能还有没用的券）。

两个未知数 p、q，两个方程。这是纯代数题，不是算法题。

第一个方程直接给了你 p × q = n。

现在把第二个方程展开：(p−1)(q−1) + 1 = pq − p − q + 1 + 1。你已经知道 pq 是多少了——能不能解出 p + q？

e×d − 1 = pq − p − q + 1 = n − (p+q) + 1

移项得 p + q = n − e×d + 2（题面提示里那个 m 就是它）。

现在你同时知道了两个数的和 m 与积 n。那么 p、q 就是一元二次方程

x² − m·x + n = 0

的两个根。剩下的就是解方程 + 判断解合不合法。

1. m = n - e*d + 2
2. Δ = m*m - 4*n，若 Δ < 0 → 输出 NO
3. 求 s = √Δ，若 s*s != Δ（不是完全平方数）→ 输出 NO
4. p = (m - s) / 2，q = (m + s) / 2
5. 回代验证：p、q 都必须是正整数，且 p * q == n。不满足就 NO

两个必踩的坑：

⚠️ 全程 long long。 n 到 10¹⁸，m*m 和 4*n 都在 long long 的边缘（上限约 9.2×10¹⁸），int 连门都摸不到。

⚠️ 不能直接用 sqrt。 这是本题最大的杀手：sqrt 返回 double，只有约 15~16 位有效数字，而 Δ 有 18 位——算出来会差 1，于是"是不是完全平方数"的判断直接错掉。必须用 S5 里那个"先算再修"的写法：先 (long long)sqrt((double)Δ)，再用 while 往上下各修一修。

⚠️ 步骤 4 里 m - s 可能是奇数（除以 2 除不尽），也可能是负数。第 5 步的回代验证能兜住这些情况——别省这一步。

⚠️ 这是 T3，而且它的难度 90% 在输出格式，不在数学上。 求根公式你早就会了。

所以第一步不是写代码，是拿张纸把所有情况列全：

• Δ < 0 → NO
• Δ = 0 或 Δ 是完全平方数 → 有理根，输出分数（分母是 1 时只输出分子；分子是负数时负号在哪；a 是负数怎么办）
• Δ 不是完全平方数 → 输出 q₁+q₂√r 形式（q₁ 为 0 时还输不输出；q₂ 为 1 时输不输出这个 1）

每一种情况先在纸上写出它对应的输出长什么样。 列不全就开始写代码，一定会陷进无穷无尽的 WA。

较大根 = (-b + √Δ) / (2a)。

⚠️ 但 a 可能是负数！ a < 0 时，(-b + √Δ)/(2a) 反而是较小的那个根。先统一处理：若 a < 0，把 a、b、c 三个全部取反（方程的根完全不变），这样就能保证 a > 0，后面所有分析都简单一档。

有理根的情况：把结果当分数 p / q 处理，用 S5 的 gcd 约到最简，保证分母为正；分母为 1 时只输出分子。

无理根的情况，要把 √Δ 化简成 q₂√r 的形式，r 无平方因子：

枚举 i 从 2 到 √Δ，只要 i*i 整除 Δ，就从根号里提出一个 i（Δ /= i*i，提出的系数 *= i），同一个 i 要反复提到提不动为止。剩下的 Δ 就是 r。

然后 x = -b/(2a) + (提出的系数/(2a))·√r，两个分数各自用 gcd 约分。

按提示 1 列的表，逐种情况拼输出字符串。

⚠️ 题面要求 q₂ > 0，且输出不含空格。 ⚠️ T ≤ 5000 组数据，但 |a|,|b|,|c| ≤ 10³，所以 Δ ≤ 约 4×10⁶，枚举提平方因子完全来得及。

📝 建议这道题最后做，而且做之前先把前 11 道全部 AC。 它的调试成本远高于收益——考场上遇到这种题，先把 T1、T2 拿满再回头。