S 组没有送分题，但真正难到做不出的只有 12 分。
整卷 100 分压在「把代码在脑子里跑起来」这件事上：阅读程序 40 分、完善程序 30 分，再加上单选里直接给代码的 6 分，合计 76 分；纯计算 24 分，靠背概念拿分的题是 0 分。更值得注意的是——四道压轴题（21、33、38、43）全部不需要新知识，它们考的都是「多推一步」：删一句会怎样、能不能计数、结论对不对、等号取哪边。
阅读程序 40 + 完善程序 30 + 单选给代码的 6 分。纯推导计算只有 24 分，记忆型常识 0 分。
位运算、哈夫曼树、数位计数、区间 DP、模拟法——S 卷里仍有近四分之一的分值来自入门级（2.1）。
全卷 54 分落在难度系数 6 的提高级核心条目上；对照 J 卷最高只用到【5】，差距就在这里。
第 21、33、38、43 题，每题 3 分。四道题不给新知识，只给「想不到就丢分」的细节。
> 与 >= 两种写法，答案分别为 C 与 D，详见第 27 题的说明块。全部结论未经官方发布，仅供参考。把「考什么」拆成四层来看：能力归口、难度分档、大纲板块、大纲系数。
把 a[i] <= a[j] 改成 a[i] < a[j]、删掉一句 if (a[i] == 0) continue;、交换两个 if 的先后顺序。同一行文字的细微差别，会让整个程序的语义偏出去。这是 S 卷最偏爱的手法（本卷出现 3 次），也是「背模板」最没用的一类题。
题目给的代码都不长，但必须一个变量一个变量地跟。和 J 卷一样：命题人不奖励「看起来懂」，只认「跑得出来」。
光会跑还不够，要能一句话概括语义：是模 2 多项式除法（CRC）？是 ST 表查询？是求树的直径？选项里通常埋着一个「动作对但说法错」的伪答案。
主定理三种情形、循环不变量、全局数组的初值、建表的时间复杂度。不需要算具体数字，但需要讲得出「为什么」。
拓扑序计数、卡特兰数、border 长度之和、合法输入的种类数。本卷区分度最高的一类题，也最容易「方向对、算错数」。
最少补几条边、gcd 与区间最小值的大小关系、lg 数组的上下取整、cnt + (r < n)、v >= (n & 1)——答案往往就差一个等号、一个取整方向。
43 题完整答案。判断题填 √ / ×，选择题填选项字母。本表为独立推演结果，仅供参考。
这四道题决定了 12 分的差距，也决定了「看懂」与「做对」之间的那道坎。
四道题都是 ★★★★★，每题 3 分，合计 12 分。它们的共同点是：不需要任何新知识，考的是愿不愿意在「看起来会了」之后再多推一步。
卡在哪第 16 行的 if (a[i] == 0) continue; 是这段模 2 除法（CRC）的「守卫」。删掉它，程序不会崩、不会越界，照样输出一个 12 位的 '0'/'1' 串——所以很多同学会误判成「基本没影响」。
怎么破关键在于：删掉守卫后，每个 i 都会无条件异或一次 gen，整段程序变成一个与输入无关的固定操作。用程序跑 50 组随机输入，输出永远是同一个串 100000000101——这正是选项 C 说的「能正常输出，但结果与输入 s 无关」。看到「删一句」的题，先问自己：删掉的这句承担了什么职责？
卡在哪题面：n = 10 时，输出为 9 的合法输入有多少种？输出 9 意味着直径恰好是 9——十棵树里最长的路径要覆盖全部 10 个点，也就是这棵树必须退化成一条链。
怎么破把「树是一条链」翻译成父指针语言：整棵树就是「以 1 为根、两条链挂在 1 上」，而每个点的父结点编号比它小，所以每条链内部的顺序是被唯一确定的——只要决定 2~10 这 9 个点各自归左边还是右边，就唯一确定一种输入。左右互换得到同一棵树，故为 2^9 / 2 = 256 种（选项 C）。本题被穷举程序完整验证：全部 362880 种合法输入里，恰好 256 种输出 9。
卡在哪平衡路线的程序，前半段是标准的 BFS + 二分图染色，好写；难的是最后一句：if (⑤) cout << 0; else cout << 1;。四个选项都是「ok 与 c[s] == c[t] 的布尔组合」，看不出对错的区别，只能靠推理。
怎么破两条线索。①若图是二分图（ok 为真），从 s 到 t 的所有路线长度同奇偶，权值也同奇偶——距离为偶数时才可能凑出 0，对应 c[s] == c[t]；②若图非二分（ok 为假），存在奇环，长短两条路线的奇偶性都能凑出来，再配合两种符号的边，一定能把权值凑成 0。两条合起来就是 (!ok) || (c[s] == c[t])（选项 C）。用 800 组随机小图，把选项代进程序与暴力搜索逐一对照，只有这一组零偏差。
卡在哪第 43 空是 if (⑤) res[j] = 'A'; else res[j] = 'B';，而四个选项是 v >= (n & 1)、v > (n & 1)、v + (n & 1) >= 0、v * (n & 1) >= 0——看上去都很像，甚至有一项在大部分情况下都对。
怎么破v 是 n 个 ±1 的和，所以 v 与 n 同奇偶：n 为奇数时 v 必为奇数，永远不会等于 0；n 为偶数时 v 可能为 0。要让这一题取到最优，就得让 v 与所选的 s[j] 同号，即当选 A 时希望 v > 0（n 奇数）或 v ≥ 0（n 偶数）——恰好就是 v >= (n & 1)（选项 A）。其余三项在 n 为奇数且 v = 1 时会选错，输出的标准答案不再最优。
15 题共 30 分。难点集中在第 6、9、11、14 题：小规模时贪心与最优解常常一致、递归树每层和恒定、比较符一改动口径就变。
执行下列代码后，cnt 的值是（ ）。
int x = 2026, cnt = 0;
while (x) {
x &= x - 1;
cnt++;
}x & (x-1) 的作用是消掉 x 的二进制里最低位的那一个 1：减 1 会把最低位的 1 变 0、并把右边的 0 全部变成 1，再按位与，这一位连同右边的变化就一起被抹掉了。所以循环每转一圈消掉一个 1，cnt 数出来的正是 2026 的二进制中 1 的个数。
2026 = 1024+512+256+128+64+32+8+2，写作二进制是 11111101010，共 8 个 1，故 cnt = 8，选 D。
用权值 {1, 2, 3, 4, 5, 6, 7, 8} 构造哈夫曼树，其带权路径长度是（ ）。
哈夫曼树有一个很好用的结论：带权路径长度 = 所有非叶结点（每步合并出来的新结点）权值之和。所以不必真把树画出来，只要按贪心反复取最小的两个相加，再把每次的和累加即可。
合并过程：1+2=3 → 3+3=6 → 4+5=9 → 6+6=12 → 7+8=15 → 9+12=21 → 15+21=36。累加 3+6+9+12+15+21+36 = 102，选 D。
把 1 到 1000 的所有整数按十进制写出，数字「1」总共出现了多少次（ ）。
按数位分类计数，不要按数字一个个枚举。1 到 999 每个数都有百、十、个三个数位；固定某一位为 1，另外两位各有 10 种取法，所以每一位上出现 1 的次数都是 100。
三个数位合计 300 次，再加上 1000 里那一个 1，共 301 次，选 C。
将 5 封信随机装入 5 个写好地址的信封（每封一个），恰好有 2 封装对的方案数是（ ）。
分两步：先选出哪 2 封装对，再让剩下的 3 封全部装错。
选 2 封有 C(5,2) = 10 种；3 个元素的错排 D₃ = 2（只可能是 231 与 312）。10 × 2 = 20，选 D。
3^2026 mod 100 的值是（ ）。
求幂取模先找循环节。3¹⁰ = 59049 ≡ 49，49² = 2401 ≡ 1，所以 3²⁰ ≡ 1 (mod 100)，3 的幂模 100 以 20 为周期。
2026 = 20 × 101 + 6，因此 3^2026 ≡ 3⁶ = 729 ≡ 29（mod 100），选 A。
有 5 堆石子排成一行，重量依次为 4, 1, 3, 2, 5。每次只能把相邻的两堆合并成一堆，代价为这两堆重量之和。将所有石子合并成一堆的最小总代价是（ ）。
这是线性相邻合并，不能贪心——本题的贪心解恰好是 35，比最优解大（见「易错」）。正确做法是区间 DP：设 f[i][j] 为把第 i 到第 j 堆合成一堆的最小代价，则 f[i][j] = min{ f[i][k] + f[k+1][j] } + (a[i]+…+a[j])。
按区间长度递推：长度 2 得 5、4、5、7；长度 3 得 [1,3]=12、[2,4]=10、[3,5]=15；长度 4 得 [1,4]=20、[2,5]=24；最后 [1,5] = min(24, 5+15, 12+7, 20) + 15 = 34，选 C。
树状数组维护长度 n = 16 的序列。查询前缀和 sum(11) 与单点修改 add(3, x) 分别需要访问树状数组中多少个下标（ ）。
树状数组两个操作的跳法是固定的：查询 sum(i) 每次 i -= i & -i（lowbit），修改 add(i) 每次 i += i & -i，后者一直跳到下标超过 n 为止。
sum(11)：11 → 10 → 8 → 0，共 3 个下标；add(3)：3 → 4 → 8 → 16，共 4 个下标。选 A。
有向无环图 G 顶点集为 {1, 2, 3, 4}，边集为 {(1,2), (1,3)}，顶点 4 与任何顶点均不相邻。该图不同的拓扑序共有多少种（ ）。
顶点 4 是孤立点，它与 1、2、3 之间没有任何先后约束；而 1 必须排在 2、3 之前。
先排 {1,2,3}：只有 1,2,3 与 1,3,2 两种。再把 4 插进这三个点形成的 4 个空位（最前、两处中间、最后），每种排法有 4 种插法。2 × 4 = 8，选 B。
某分治算法满足 T(n) = T(n/3) + T(2n/3) + Θ(n)，T(1) = O(1)，则 T(n) 是（ ）。
这类式子最稳的做法是画递归树。每一层所有子问题的规模之和恒为 n（n/3 + 2n/3 = n），所以每层的加工代价都是 Θ(n)。
再看深度：规模大于等于 1 就必须继续分，每次乘以 2/3，深度为 log_{3/2} n。总代价 = Θ(n) × Θ(log n) = Θ(n log n)，选 A。
无根树含 9 个结点（编号 1—9），边集为 {(1,2), (1,3), (2,4), (2,5), (3,6), (6,7), (7,8), (5,9)}。该树的直径（以边数计）与重心分别是（ ）。
先把树画出来：1 连 2、3；2 连 4、5；5 连 9；3 连 6；6-7-8 是一条链。最长的一条路是 9-5-2-1-3-6-7-8，经过 7 条边，故直径 7。
重心定义为「删掉它后，剩下的每个连通块都不超过 n/2」。删结点 1 得到 {2,4,5,9} 与 {3,6,7,8}，两块都是 4 个点，都不超过 4.5；n = 9 是奇数时重心唯一，故重心就是结点 1。选 D。
一张有向图缩点后得到的有向无环图含 6 个顶点，其中入度为 0 的顶点有 3 个、出度为 0 的顶点有 4 个。为使原图变成强连通图，至少需要添加多少条有向边（ ）。
缩点后成为 DAG，让它强连通有一个干净的结论：最少加边数 = max(入度为 0 的顶点数, 出度为 0 的顶点数)——把每个「只出不进」的点接向每个「只进不出」的点，形成一个大环即可。
本题源点 3 个、汇点 4 个，故最少 4 条边，选 C。
含 6 个结点的不同形态的二叉树共有多少棵（结点不带标号，区分左右子树）（ ）。
n 个结点的不同形态二叉树（区分左右子树）的个数正是卡特兰数：Cₙ = C(2n, n) / (n+1)。
n = 6 时：C(12,6) = 924，924 ÷ (6+1) = 132，选 C。
字符串 S = 「ababaabab」，其所有既是真前缀又是真后缀的子串（非空）的长度之和是（ ）。
逐长度检查。长度 1：前缀 a 与后缀 b 不符；长度 2：ab 与末尾 ab 相符 ✓；长度 3、5、6、7、8 都不符；长度 4：abab 与末尾四位 abab 相符 ✓。
符合条件的长度是 2 和 4，和为 6，选 B。（这正是 KMP 的 border 链：π(9) = 4，沿 π(4) = 2、π(2) = 0 一路回退。）
用归并排序统计逆序对，合并部分的判断条件由 a[i] <= a[j] 改成 a[i] < a[j]，则 ans 统计出的结果是（ ）。
// 归并 a[l..mid] 与 a[mid+1..r]，同时累加逆序对
if (a[i] <= a[j]) {
tmp[k++] = a[i++]; // 取左半段元素
} else {
tmp[k++] = a[j++]; // 取右半段元素
ans += mid - i + 1;
}原写法里，只有 a[i] > a[j] 才走 else 分支并累加 mid - i + 1，统计的是严格逆序对（i < j 且 a[i] > a[j]）。
改成 a[i] < a[j] 后，a[i] == a[j] 也会走左分支、不再计数；于是只有 a[i] >= a[j] 才累加——统计对象变成i < j 且 a[i] ≥ a[j] 的数对，选 C。
执行 power(2, 100, 1000) 调用下列函数，返回值是（ ）。
long long power(long long a, long long b, long long p) {
long long r = 1 % p;
while (b) {
if (b & 1) r = r * a % p;
a = a * a % p;
b >>= 1;
}
return r;
}这是快速幂：把指数 100 看成二进制 1100100，按「平方—乘」交替执行——b 的最低位为 1 时把当前的 a 乘进结果，每轮 a 自平方、b 右移一位。
手工算中间量（模 1000）：2¹⁰ = 1024 ≡ 24；2²⁰ ≡ 24² = 576；2⁴⁰ ≡ 576² = 331776 ≡ 776；2⁸⁰ ≡ 776² = 602176 ≡ 176；于是 2¹⁰⁰ = 2⁸⁰ × 2²⁰ ≡ 176 × 576 = 101376 ≡ 376，选 B。
r = 1 % p 这个写法是为了处理 p = 1 的边界，说明命题人在细节上很讲究。三组程序共 40 分。这里没有一个空是靠背知识填的——第 20、21 题考算法本质与守卫的作用，第 27 题考取整方向，第 33 题考「数输入」。
01 #include <iostream>
02 #include <string>
03 using namespace std;
04 int a[100];
05 string s;
06 int gen[13] = {1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1};
07 int main() {
08 cin >> s;
09 for (int i = 0; i < 32; ++i) {
10 a[i] = s[i] - '0';
11 }
12 for (int i = 32; i < 44; ++i) {
13 a[i] = 0;
14 }
15 for (int i = 0; i < 32; ++i) {
16 if (a[i] == 0) continue;
17 for (int j = 0; j < 13; ++j) {
18 a[i + j] ^= gen[j];
19 }
20 }
21 for (int i = 32; i < 44; ++i) {
22 cout << a[i];
23 }
24 cout << endl;
25 return 0;
26 }说明：输入保证为一个长度恰为 32 的 '0'/'1' 字符串。
（1 分）当输入为 32 个 '0' 时，程序输出 12 个 0。
全 0 输入时，每一位都满足 a[i] == 0，第 16 行的 continue 会让 32 次循环全部被跳过；a[32]~a[43] 保持补零循环写进去的 0，于是输出 12 个 '0'。√
程序运行结束后，数组 a 中下标从 0 到 31 的元素一定全部为 0。
看下标的「方向性」：第 i 轮循环（i 从 0 到 31 递增）只可能修改下标 ≥ i 的位置（a[i+j] ^= gen[j]，j ≥ 0）。所以第 i 轮结束时 a[i] 已经变成 0，而后续 i′ > i 的轮次只会影响下标 ≥ i′，再也碰不到 a[i]。
一位一位看下来，每处理完一位它就永久归零，故最终 a[0..31] 全为 0。√（用 200 组随机 32 位串复核，全部成立。）
若将第 12～14 行（为 a[32] 到 a[43] 补 0 的循环）删除，会改变程序输出结果。
关键在第 04 行：int a[100]; 写在 main 之外，是全局数组，程序启动时已被零初始化——a[32] 到 a[43] 本来就是 0。
补零循环只是把「本来就是 0」这件事明写了一遍，删掉之后每一步得到的中间状态完全相同，输出不会变。×
关于第 6 行定义的数组 gen，下列说法正确的是（ ）。
int gen[13] = {1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1}; 共 13 个元素，取值依次拼起来就是 1100000001111。
程序在第 18 行用 a[i + j] ^= gen[j] 去消掉当前最高位 a[i]，说明 gen[0] 与 a[i] 对齐——gen[0] 就是除数的最高位。选 C。
该程序实现的功能，最准确的说法是（ ）。
第一步是「补 12 个 0」：把 M 的每一位依次写进 a[0..31]，再令 a[32..43] = 0，等价于把 M 左移 12 位，即 M × 2¹²。
第二步是「见 1 就异或一次 gen」：这是模 2 多项式除法的标准写法（与二进制长除法、CRC 校验完全一致）——从最高位开始，若当前位是 1 就把除数对齐着异或一次，把它消成 0 再往右走。除数是 13 位的 1100000001111，除完剩下的低 12 位就是余数，也正是程序的输出。选 B。
若将第 16 行 if (a[i] == 0) continue; 删除，说法正确的是（ ）。
删掉守卫后，每个 i 都会无条件执行 a[i + j] ^= gen[j]，不再依赖 a[i] 的值。此时 a[32..43] 的初值恒为 0，而每位被异或的次数只由 i、j 的循环次数决定——整段程序变成一个与输入 s 完全无关的固定操作。
实测：50 组随机输入，输出永远是同一个串 100000000101。程序不会崩、也不会越界（最大下标 43 < 100），但结果与 s 无关。选 C。
01 #include <iostream>
02 using namespace std;
03 int n, m, a[100007], L, R, lg[100007], i, j, t, dp[100007][25], pw[25];
04 int gcd(int x, int y) {
05 if (y == 0) return x;
06 return gcd(y, x % y);
07 }
08 int main() {
09 cin >> n >> m;
10 for (i = 1; i <= n; i++) cin >> a[i];
11 t = 0;
12 pw[0] = 1;
13 for (i = 1; i <= 24; i++) pw[i] = pw[i - 1] * 2;
14 for (i = 2; i <= 100000; i++)
15 if (pw[t + 1] >= i) lg[i] = t;
16 else t++, lg[i] = t;
17 for (i = 1; i <= n; i++)
18 dp[i][0] = a[i];
19 for (j = 1; j <= lg[n]; j++)
20 for (i = 1; i + pw[j] - 1 <= n; i++) {
21 dp[i][j] = gcd(dp[i][j - 1], dp[i + pw[j - 1]][j - 1]);
22 }
23 for (i = 1; i <= m; i++) {
24 cin >> L >> R;
25 cout << gcd(dp[L][lg[R - L + 1]], dp[R - pw[lg[R - L + 1]] + 1][lg[R - L + 1]]) << endl;
26 }
27 return 0;
28 }说明：保证 1 ≤ n ≤ 100000，每次查询满足 1 ≤ L ≤ R ≤ n，且数组 a 的元素均为正整数。
>= i——取整方向直接决定第 27 题。当 n = 5，a = {4, 2, 6, 3, 9}，且仅有一次查询 L = 2、R = 5 时，输出为 1。
查询区间是 a[2..5] = {2, 6, 3, 9}：gcd(2, 6) = 2，gcd(2, 3) = 1，所以整个区间的 gcd 就是 1。程序用两块长度 2^k 的重叠区间覆盖查询，重叠保证了不漏任何元素，结果同样是 1。√
当某次查询的区间长度为 1（即 L = R）时，这次查询的输出一定等于 a[L]。
长度 1 时 k = lg[1] = 0，两块区间都是 dp[L][0] = a[L]，gcd(a[L], a[L]) = a[L]。√
任意一次查询的输出结果一定不小于该查询区间内的最小值。
区间 gcd 一定整除区间里的每一个数，因此它必然不大于区间最小值。题干写的是「不小于」，方向反了。
用 500 组随机数据检验，没有出现「gcd 大于区间最小值」的情形。×
对于 j ≥ 1，数组 dp[i][j] 保存的是（ ）。
递推式是 dp[i][j] = gcd(dp[i][j-1], dp[i + pw[j-1]][j-1])，而 pw[j-1] = 2^(j-1)：把两个长度 2^(j-1) 的块拼起来，正好覆盖连续 2^j 个数。所以 dp[i][j] 表示从 a[i] 开始的连续 2^j 个数的 gcd。选 B。
若把一次求最大公约数的运算视为 O(1)，则第 17～22 行建表过程的时间复杂度为（ ）。
建表是两层循环：外层 j 从 1 到 lg[n] ≈ log₂n，内层 i 从 1 到 n − 2^j + 1。总运算次数约为 n·log n，每次 gcd 记为 O(1)，故为 Θ(n log n)。选 B。
（每次查询只需 O(1) 次 gcd，与 m 无关；Θ(mn) 是「每次查询重新扫一遍区间」的朴素做法。）
设 x 为一次查询的区间长度（即 x = R − L + 1），则使得 lg[x] = 5 的 x 的取值范围是（ ）。
这段代码里的 lg 数组不是常见的「下取整」版本。盯住两处细节：循环从 i = 2 开始，判断写的是 pw[t + 1] >= i（带等号）。于是 t 只在 2^(t+1) 严格小于 i 时才增加，等价于 lg[i] = ⌈log₂ i⌉ − 1。
直接代入：lg[32] = 4（因为 2⁵ = 32 ≥ 32，t 还停在 4）、lg[33] = 5、lg[64] = 5、lg[65] = 6。所以 lg[x] = 5 的范围是 [33, 64]，选 D。
for (i = 1; ...) + if (pw[t+1] > i) —— 此时 lg[i] = ⌊log₂i⌋，lg[x] = 5 对应 [32, 63]，应选 C；for (i = 2; ...) + if (pw[t+1] >= i) —— 此时 lg[i] = ⌈log₂i⌉ − 1，lg[x] = 5 对应 [33, 64]，应选 D。>= 这个等号上。（两个版本的 lg 都能让 ST 表正确工作，所以命题人敢这么出。）01 #include <iostream>
02 using namespace std;
03 int n, fa[100007], f[100007], ans;
04 int main() {
05 cin >> n;
06 for (int i = 2; i <= n; ++i) {
07 cin >> fa[i];
08 }
09 for (int i = n; i >= 2; --i) {
10 if (f[fa[i]] + f[i] + 1 > ans) {
11 ans = f[fa[i]] + f[i] + 1;
12 }
13 if (f[i] + 1 > f[fa[i]]) {
14 f[fa[i]] = f[i] + 1;
15 }
16 }
17 cout << ans << endl;
18 return 0;
19 }说明：输入第一行为结点个数 n，第二行为 n − 1 个整数，依次表示结点 2 ~ n 的父结点编号，满足 2 ≤ n ≤ 100000 且 1 ≤ fa[i] < i，根结点为 1。
当 n = 5，fa[2] ~ fa[5] = {1, 2, 3, 4} 时，程序输出 4。
这组输入是一条链 1-2-3-4-5。程序从 i = n 递减处理，保证先算完儿子再算父亲：i=5：ans = 0+0+1 = 1，f[4] = 1；i=4：ans = 2，f[3] = 2；i=3：ans = 3，f[2] = 3；i=2：ans = 4，f[1] = 4。输出 4。√
程序输出前，f[1] 的值一定等于 ans 的值。
两者含义不同：f[u] 是以 u 为根的子树高度（以边数计），ans 是整棵树的直径（最远两点间的边数），根的高度与全树直径一般不等。
反例：n = 3、fa[2] = fa[3] = 1 的星形树，f[1] = 1，而 ans = 2（叶子 2 → 1 → 叶子 3）。×
将第 10～12 行与第 13～15 行两个 if 语句的顺序交换后，程序的输出结果不受影响。
原顺序是「先用旧的 f 值更新 ans，再抬高 f[fa[i]]」，两条腿算的是不同的儿子，互不干扰。
交换之后，抬高 f[fa[i]] 的那句先执行，ans 的计算就会用上「刚被自己这条腿抬上去的」值，等于把同一条链数了两遍。实测：n = 5 的链，原程序输出 4，交换后输出 8。×
程序输出的 ans 表示的是（ ）。
处理结点 i 时，用 f[i]（i 这条腿的高度）加上 f[fa[i]]（父结点已统计过的另一条最好的腿），再加 1（连接它们的这条边）去更新 ans——求的正是「穿过边 (i, fa[i]) 的最长路径」。对每条边取一遍最大值，得到的就是全树直径。选 A。
（这就是「树型 DP 一次遍历求直径」的经典写法。）
当 n = 7，fa[2] ~ fa[7] = {1, 1, 2, 2, 3, 3} 时，输出为（ ）。
结构：1 的儿子是 2、3；2 的儿子是 4、5；3 的儿子是 6、7。最长路径形如 4-2-1-3-6，4 条边。
逐步模拟：i=7、6 把 f[3] 抬到 1、ans 到 2；i=5、4 把 f[2] 抬到 1；i=3 时 f[1] 变 2；i=2 时 ans = f[1] + f[2] + 1 = 2 + 1 + 1 = 4。选 C。
当 n = 10，满足输出为 9 的合法输入种类数为（ ）。
输出 9 说明直径是 9，而树里总共只有 10 个结点——要想最远的两点距离达到 9，这棵树必须退化成一条链（10 个点串成一线）。
把「树是一条链」翻译成父指针的语言：每个点的父结点编号都比它小，链上的先后顺序因此被唯一确定，整棵树完全取决于「2～10 这 9 个点各自归 1 的左边还是右边」；而左右互换得到的是同一棵树，故为 2⁹ ÷ 2 = 256 种。选 C。
（本题用穷举程序完整验证：全部 9! = 362880 种合法输入中，恰好 256 种使输出为 9。）
两组程序、10 个空，共 30 分。第一组第 38 空填的是结论；第二组的五个空全部围绕一个想法：把绝对值写成 max(±y)，再用格雷码枚举符号方案。
给定一张有 n 个顶点、m 条边的无向图，每条边带有符号 + 或 −。对于一条从顶点 s 到顶点 t 的路线（允许重复经过顶点和边），记 n₊、n₋ 分别为路线经过的 + 边数和 − 边数，则该路线的权值为 |n₊ − n₋|。
请计算从 s 到 t 的路线的最小权值。若不存在从 s 到 t 的路线，则输出 −1。
输入第一行为四个整数 n, m, s, t。接下来 m 行，每行给出两个整数 a, b 和一个字符 + 或 −，描述一条连接 a 与 b 的无向边及其符号。
数据满足 2 ≤ n ≤ 2×10⁵，1 ≤ m ≤ 4×10⁵，1 ≤ s, t ≤ n 且 s ≠ t，1 ≤ a, b ≤ n，可能出现重边。
01 #include <iostream>
02
03 constexpr int N = 200005;
04 constexpr int M = 400005;
05
06 int n, m, s, t;
07 int h[N], e[M << 1], ne[M << 1], w[M << 1], idx;
08 int q[N], d[N], c[N];
09
10 void add(int a, int b, int z) {
11 e[idx] = b;
12 w[idx] = z;
13 ne[idx] = h[a];
14 h[a] = idx++;
15 }
16
17 int main() {
18 std::cin >> n >> m >> s >> t;
19 for (int i = 1; i <= n; i++)
20 h[i] = d[i] = c[i] = -1;
21 for (int i = 0; i < m; i++) {
22 int a, b;
23 char op[2];
24 std::cin >> a >> b >> op;
25 int z = ①;
26 add(a, b, z);
27 add(b, a, z);
28 }
29 int hh = 0, tt = 0;
30 int p = 0, ng = 0, ok = 1;
31 q[tt++] = s;
32 d[s] = c[s] = 0;
33 while (②) {
34 int x = q[hh++];
35 for (int i = h[x]; i != -1; i = ne[i]) {
36 int y = e[i];
37 if (w[i] > 0) p = 1;
38 if (w[i] < 0) ng = 1;
39 if (d[y] == -1) {
40 d[y] = ③;
41 c[y] = c[x] ^ 1;
42 q[tt++] = y;
43 } else if (④)
44 ok = 0;
45 }
46 }
47 if (d[t] == -1) {
48 std::cout << -1;
49 return 0;
50 }
51 if (!p || !ng) {
52 std::cout << d[t];
53 return 0;
54 }
55 if (⑤) std::cout << 0;
56 else std::cout << 1;
57 return 0;
58 }① 处应填（ ）。
op[0] == '+' ? 0 : 1op[0] == '+'op[0] == '+' ? 1 : -1op[0] == '-' ? 1 : 0题目要算的权值是 |n₊ − n₋|，而程序后面既用 if (w[i] > 0) p = 1 判断「有没有 + 边」，又用 if (w[i] < 0) ng = 1 判断「有没有 − 边」，还要让 w 参与符号运算——所以 w 必须是 +1 / −1。
选项 B 是布尔值 1/0：负号边会被记成 0，w[i] < 0 永远不成立，判断直接失效；A、D 的值域只有 {0, 1}，同样不行。选 C。
② 处应填（ ）。
hh < ntt < nhh <= tthh < tt队列用 q[tt++] = y 入队、x = q[hh++] 出队，所以 hh 指向队首、tt 指向队尾的后一格，「队列非空」的条件就是 hh < tt。选 D。
选项 C 在队列已空时会多取一个位置（那里是全局数组的 0），程序会以「编号 0 的伪结点」继续跑；选项 A 在「t 不可达、图不连通」时会多转很多圈，同样会读到无效位置——本组测试里它读到的恰好都是 0，所以「看着没错」，其实是运气。
③ 处应填（ ）。
d[y] + 1d[x] + 1d[x]d[x] - 1d 数组记录从 s 出发经过的边数。y 是 x 的邻居，且此刻是第一次访问到 y，所以 d[y] = d[x] + 1，选 B。
A 里 d[y] 此刻还是 −1（未访问标记），写出来就是 −1 + 1 = 0；C 让所有点都停在第 1 层。
④ 处应填（ ）。
c[y] == c[x]w[i] == 1c[y] != c[x]d[y] + 1 != d[x]c 数组是 BFS 过程的染色：c[y] = c[x] ^ 1（相邻点异色）。若某条边连接的两个点颜色相同，就找到了一个奇数长度的环，图不是二分图。
程序用 ok 标记「图是二分图」，所以这里填 c[y] == c[x]，选 A。
⑤ 处应填（ ）。
ok && c[s] == c[t]ok && c[s] != c[t]!ok || c[s] == c[t]!ok && c[s] != c[t]情形一：图是二分图（ok 为真）。从 s 到 t 的所有路线长度同奇偶，权值 |n₊ − n₋| 也随之同奇偶（因为 n₊ + n₋ = 路线长度，而 n₊ − n₋ ≡ n₊ + n₋）。要把权值凑成 0 就必须是偶数——恰好对应 c[s] == c[t]（s、t 同色即距离为偶）；距离为奇数时，最小权值只能是 1。
情形二：图不是二分图（ok 为假）。存在奇环，奇偶两种长度的路线都能凑出来，再配合两种符号的边，一定能把权值调到 0。
两种情况合起来就是「ok 为假 或 s、t 同色时输出 0」，即 (!ok) || (c[s] == c[t])，选 C。
有 n 名学生参加一次考试，考试共有 m 道选择题，每道题只有 A、B 两个选项。第 i 名学生的作答用一个长度为 m 的字符串 aᵢ 表示。
若最终公布的标准答案与该学生在某道题上的作答相同，则该学生得 1 分，否则不得分；记第 i 名学生最终得到的总分为 rᵢ。
给定每名学生的目标分数 xᵢ。现在需要构造一份标准答案，使 Σ|rᵢ − xᵢ| 尽可能大。
数据满足 1 ≤ n ≤ 20，1 ≤ m ≤ 300，0 ≤ xᵢ ≤ m。对于非零整数 x，__builtin_ctzll(x) 返回 x 的二进制表示末尾连续 0 的个数；__builtin_popcountll(x) 返回 x 的二进制表示中 1 的个数。程序输出一组满足要求的标准答案。
01 #include <cstdlib>
02 #include <iostream>
03 #include <string>
04 #include <vector>
05
06 using namespace std;
07
08 typedef long long ll;
09 typedef unsigned long long ull;
10
11 int main() {
12 int n, m;
13 cin >> n >> m;
14 vector<ll> x(n), c(n);
15 for (int i = 0; i < n; i++) {
16 cin >> x[i];
17 c[i] = ①;
18 }
19 vector<string> a(n);
20 for (int i = 0; i < n; i++)
21 cin >> a[i];
22
23 vector<int> s(n, -1);
24 vector<ll> q(m, 0);
25 ll C = 0, S = 0;
26 for (int i = 0; i < n; i++) {
27 C -= c[i];
28 for (int j = 0; j < m; j++) {
29 if (a[i][j] == 'A') q[j]--;
30 else q[j]++;
31 }
32 }
33 for (int j = 0; j < m; j++) S += abs(q[j]);
34 ll ans = C + S;
35 ull best = 0, lst = 0;
36
37 for (ull mask = 1; mask < (1ULL << n); mask++) {
38 ull g = ②;
39 ull d = g ^ lst;
40 int k = ③;
41 C -= ④;
42 for (int j = 0; j < m; j++) {
43 ll old = q[j];
44 int v = (a[k][j] == 'A' ? 1 : -1);
45 q[j] -= 2ll * s[k] * v;
46 S += abs(q[j]) - abs(old);
47 }
48 s[k] = -s[k];
49 if (C + S > ans) {
50 ans = C + S;
51 best = g;
52 }
53 lst = g;
54 }
55
56 for (int i = 0; i < n; i++) {
57 if (best >> i & 1) s[i] = 1;
58 else s[i] = -1;
59 }
60
61 string res(m, 'A');
62 for (int j = 0; j < m; j++) {
63 ll v = 0;
64 for (int i = 0; i < n; i++) {
65 if (a[i][j] == 'A') v += s[i];
66 else v -= s[i];
67 }
68 if (⑤) res[j] = 'A';
69 else res[j] = 'B';
70 }
71 cout << res << endl;
72 return 0;
73 }① 处应填（ ）。
2 * x[i] - m-m + 2 * x[i] + 1m - 2 * x[i]m + 2 * x[i]程序的第一步是把「带绝对值的和目标」线性化：对任意整数 y 都有 |y| = max(σ·y)，σ 取 ±1。于是 Σ|r_i − x_i| = 在所有符号方案 σ 中取最大值 max Σ σ_i·(r_i − x_i)。
把 r_i 展开：第 i 名学生在第 j 题得分的贡献可以写成 (1 + u_ij·s_j)/2，其中 u_ij 表示该题作答是 A(+1) 还是 B(−1)，s_j 表示标准答案。两边同乘 2 后，σ_i 的系数就是 m - 2 * x[i]（即 c[i] = m − 2x_i），选 C。
C -= c[i] 且 s[i] 初值为 −1，符号正好相抵。② 处应填（ ）。
mask | (mask >> 1)mask ^ (mask >> 1)mask & (mask >> 1)mask ^ ((mask >> 1) + 1)程序用 d = g ^ lst 求「这一次相比上一次改变了哪一位」，再用 __builtin_ctzll(d) 取出那一位的下标——前提是相邻两个状态只差一位。满足这个条件的枚举顺序就是格雷码：g = mask ^ (mask >> 1)，选 B。
正因为每次只翻一位，程序才能「只更新一名学生」、用 O(m) 的时间增量维护 S，把原本 O(2ⁿ·n·m) 的枚举优化到 O(2ⁿ·m)。
③ 处应填（ ）。
__builtin_ctzll(d) + 1__builtin_popcountll(d)__builtin_ctzll(g)__builtin_ctzll(d)由格雷码的性质，d = g ^ lst 里恰好只有「本次变化的那一位」是 1，所以求 d 的末尾连续 0 的个数，就得到这一位的下标：__builtin_ctzll(d)。选 D。
选项 A 多 +1 会整体错位一位；C 用的是 g 而不是 d，g 里可能有多个 1，取出的位置与「本次改的是谁」无关；B 数的是 1 的个数，而 d 恰好只有一个 1，结果恒为 1，与下标无关。
__builtin_ctzll(0) 是未定义行为；这里因为相邻两次状态必不相同，d ≠ 0，可以放心用。④ 处应填（ ）。
2ll * s[k] * c[k]s[k] * c[k]2ll * (s[k] - c[k])2ll * c[k]C 变量维护的是 Σ σ_i·c_i 这一项。当第 k 名学生的符号从 s[k] 翻成 −s[k] 时，该项的变化量是 (−s[k] − s[k])·c[k] = −2·s[k]·c[k]。程序写的是 C -= ④，所以 ④ 应当填 2ll * s[k] * c[k]，选 A。
注意前面的 2ll：不要漏掉那个 2，否则 C 只更新了一半。
⑤ 处应填（ ）。
v >= (n & 1)v > (n & 1)v + (n & 1) >= 0v * (n & 1) >= 0最后一步要输出一组最优的标准答案。对第 j 题，令 v = Σ_i (a[i][j] == 'A' ? s[i] : −s[i])，选 'A' 还是 'B' 取决于 v 的符号：要让 v 与「选 A 时的 +1」同号。
关键在于 v 与 n 同奇偶——v 是 n 个 ±1 之和。n 为奇数时 v 必为奇数，永远不会等于 0；n 为偶数时 v 可能为 0（这时选 A 选 B 都一样）。「n 为奇数取 v ≥ 1，n 为偶数取 v ≥ 0」合起来正是 v >= (n & 1)，选 A。
同一天的两套卷子出自同一命题思路。把关键维度摆在一起，「孩子该练什么」会清楚很多。
初赛是入场券，分数在复赛。10 月 1 日—7 日，早 8:30 — 晚 18:00，上午精讲 · 下午带练 · 以赛代练 · 小班分层。
← 表格可左右滑动 →
| 日期 | 专题 | 上午 | 下午 |
|---|---|---|---|
| 10 月 1 日 | 数据结构 1 | 分块和根号分治 | 离线思想 & 莫队算法 |
| 10 月 2 日 | 数据结构 2 | 树链剖分及其应用 | 离线思想 & 扫描线 |
| 10 月 3 日 | 数据结构 3 | 平衡树入门 | 数据结构专题比赛 2.5h + 0.5h 讲解 |
| 10 月 4 日 | 组合数学 | 组合数及常见模型 | 容斥原理及应用 |
| 10 月 5 日 | 动态规划 1 | 计数 DP 专题 | 树形 DP 专题 |
| 10 月 6 日 | 动态规划 2 | 数据结构优化 DP | 状态设计优化 DP / 专题 |
| 10 月 7 日 | 图论 | 最短路及其复杂应用 | 比赛 2.5h + 0.5h 讲解 |
| 日期 | 专题 | 上午 | 下午 |
|---|---|---|---|
| 10 月 1 日 | 复赛基础与规范 | 复赛格式及注意事项 + 陷阱 | 公式计算、打表技巧、高精度加减乘除 |
| 10 月 2 日 | 排序算法与二分思想 | 重点排序与二分 | 快排、归并排序、二分模板、二分答案 |
| 10 月 3 日 | 搜索算法与贪心 | 搜索及贪心 | DFS、BFS、贪心与证明、哈密顿路径 |
| 10 月 4 日 | 动态规划专题 | 动态规划 | DP 分类、背包 DP、线性 DP、树形 DP、数位 DP |
| 10 月 5 日 | 树结构专题 | 树 | 二叉树建立与遍历、二叉树查找、二叉树平衡 |
| 10 月 6 日 | 集合与并查集 | 集合 | 并查集、Hash 表、集合综合应用 |
| 10 月 7 日 | 图论专题 | 图 | 图的建立与遍历、最短路、DAG 与拓扑排序 |