2026 CCF CSP-S 第一轮（提高级 C++）

先理解 x & (x-1) 的作用：x 减 1 时，最低位的 1 变成 0，它右边的 0 全变成 1；再与原来的 x 按位与，就恰好清除了最低位的那个 1，其余高位保持不变。

2026 的二进制是 11111101010，其中有 8 个 1，所以需要清除 8 次才能变为 0。

也可以直接跟踪 x：2026 → 2024 → 2016 → 1984 → 1920 → 1792 → 1536 → 1024 → 0。每次循环 cnt 加 1，最终 cnt=8，选择 D。

哈夫曼算法每次从“当前全部权值”中取最小的两个合并，并把新权值放回集合。

本题合并过程为：1+2=3；3+3=6；4+5=9；6+6=12；7+8=15；9+12=21；15+21=36。

每次合并都会使两个子树内所有叶子的深度增加 1，因此本次对带权路径长度的贡献，就是两棵子树的权值之和。把所有合并代价相加即可得到 WPL。

所以 $WPL=3+6+9+12+15+21+36=102$，选择 D。

把 0 到 999 都补成三位数，即 000、001、……、999。补在前面的数字只有 0，不会增加数字 1 的出现次数，因此这样计数与原问题的 1 到 999 等价。

固定个位为 1 时，百位、十位各有 10 种选择，共出现 $10\times10=100$ 次；固定十位或百位为 1，同理各出现 100 次。

因此 1 到 999 共出现 $3\times100=300$ 个 1。最后再计入 1000 中千位上的一个 1，总数为 301，选择 C。

例如 111 会在三个数位的统计中各贡献一次，这正是题目所要求的出现次数。

“恰好有 2 封装对”可以分为两个独立步骤。

第一步，从 5 封信中选出装对的 2 封，有 $\binom{5}{2}=10$ 种选择，并将它们放入对应信封。

第二步，余下 3 封必须全部装错。把这三封信记作 A、B、C，按对应信封顺序写出装入的信，只有 BCA、CAB 两种排列没有任何一封装对。

由乘法原理，总方案数为 $10\times2=20$，选择 D。若用 $3!=6$ 作为第二步的方案数，就会把有额外信件装对的情况也计入。

先找一个可以缩小指数的模幂周期。由 $3^5=243\equiv43\pmod{100}$，得到 $3^{10}\equiv43^2=1849\equiv49\pmod{100}$，再平方得 $3^{20}\equiv49^2=2401\equiv1\pmod{100}$。

把指数写成 $2026=20\times101+6$，则 $3^{2026}=(3^{20})^{101}\times3^6\equiv3^6\pmod{100}$。

最后 $3^6=729$，除以 100 的余数是 29，选择 A。这里不必证明 20 是最小周期，只要证明这个周期可用即可。

由于只能合并相邻两堆，每个中间结果都对应原序列的一个连续区间。设 $dp[l][r]$ 为合并第 l 到第 r 堆的最小代价，单堆时 $dp[i][i]=0$。

若最后一次在 k 与 k+1 之间分开，则先分别合并左右两段，再支付整个区间的重量和。因此 $dp[l][r]=\min_{l\le k<r}(dp[l][k]+dp[k+1][r])+\sum_{i=l}^{r}a_i$。

按区间长度递推：长度 2 的代价依次为 5、4、5、7；长度 3 的代价为 12、10、15；长度 4 的代价为 20、21。

最后合并全部 5 堆时，区间总重量为 15。四个分割点对应总代价为 0+21+15=36、5+15+15=35、12+7+15=34、20+0+15=35，最小值是 34。

一种达到 34 的顺序是：先合并中间的 1 和 3，代价 4；再与左端 4 合并，代价 8；合并右侧 2 和 5，代价 7；最后合并 8 和 7，代价 15。合计 4+8+7+15=34，选择 C。

树状数组中，lowbit(i)=i&(-i)，表示 i 的二进制最低位 1 所对应的数值。

查询前缀和时执行 i-=lowbit(i)：从 11 开始，lowbit(11)=1，转到 10；lowbit(10)=2，转到 8；lowbit(8)=8，转到 0 并停止。因此实际访问 11、10、8，共 3 个下标。

单点修改时执行 i+=lowbit(i)：从 3 开始依次转到 4、8、16、32。由于 n=16，到 32 时停止，不再访问。

所以修改访问 3、4、8、16，共 4 个下标，选择 A。

拓扑序要求每条有向边的起点出现在终点之前。两条边只要求 1 在 2、3 之前，2 与 3 之间没有先后限制。

先只排列 1、2、3，合法顺序是 123 和 132，共 2 种。

结点 4 是孤立点，可插入这三点顺序的任意一个空隙：最前面、第一与第二点之间、第二与第三点之间、最后面，共 4 个位置。

于是总数为 $2\times4=8$，选择 B。例如由 123 得到 4123、1423、1243、1234，另一种顺序同样产生 4 个不同结果。

用递归树分析：规模为 u 的问题拆成 u/3 和 2u/3，两者之和仍为 u，所以在尚未出现叶子的层上，该层所有子问题的规模之和为 n，非递归工作量为 $\Theta(n)$。

最长分支每次保留原规模的 2/3，经过 $\Theta(\log n)$ 层降到常数，因此整棵递归树高度为 $O(\log n)$。每层工作量至多 $O(n)$，总工作量上界为 $O(n\log n)$。

另一方面，最短分支每次保留 1/3，也需要 $\Theta(\log n)$ 层才到常数。在最初这数量级的完整层中，每层都需要 $\Theta(n)$ 工作量，给出 $\Omega(n\log n)$ 的下界。

上下界一致，故 $T(n)=\Theta(n\log n)$，选择 A。不能直接把两个不等大的子问题当成两个 n/2 的子问题套式子。

直径是树中最长简单路径的边数。先找叶子：4、8、9。三对叶子之间的距离分别为 dist(4,8)=6、dist(4,9)=3、dist(8,9)=7。

因此最长路径是 9—5—2—1—3—6—7—8，经过 8 个结点、7 条边，直径为 7。

重心要求删除该点后，每个剩余连通块的结点数都不超过全树的一半。删除结点 1 后，两个连通块为 {2,4,5,9} 和 {3,6,7,8}，大小都是 4，满足 $4\le9/2$。

若删除其他点，包含结点 1 及另一侧四个结点的连通块至少有 5 个结点，不能成为重心。因此唯一重心为 1，选择 D。

先将原图的每个强连通分量缩成一个点，内部已经互相可达，只需考虑这些分量之间如何连通。

缩点后的图有 6 个点，不能使用“本来就只有一个强连通分量”的特殊情况。每个零入度点都需要至少一条新增入边，否则其他分量无法到达它；每个零出度点都需要至少一条新增出边，否则它无法到达其他分量。

因此新增边数至少同时达到 3 和 4，也就是至少 4 条。一条从汇点连到源点的边，可以同时补上一个汇点的出边和一个源点的入边，所以两个数量不应相加。

对于含多个点的缩点 DAG，按可达关系适当安排汇点到源点的连接，可以用 $\max(\text{零入度点数},\text{零出度点数})$ 条边达到强连通；这里是 $\max(3,4)=4$，选择 C。注意不能随意配对，否则可能只连成多个互不连通的环。

设 $C_n$ 为 n 个无标号结点、区分左右子树的二叉树形态数，并规定空树 $C_0=1$。

固定根后，剩余 n-1 个结点分给左右子树。若左子树有 k 个结点，右子树就有 n-1-k 个，形态数为 $C_kC_{n-1-k}$；枚举 k 得到卡特兰递推 $C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}$。

由此依次得到 $C_0,C_1,\ldots,C_5=1,1,2,5,14,42$，于是 $C_6=42+14+10+10+14+42=132$。

也可用通式 $C_6=\frac{1}{7}\binom{12}{6}=132$，选择 C。这里统计形态，不需要再乘结点标号的排列数。

字符串长度为 9，“非空真前缀”限定待检查长度为 1 到 8。

长度 2 时，开头和结尾都是 ab；长度 4 时，开头和结尾都是 abab，因此 2、4 都符合。

还要排除其他长度：长度 1 为 a 与 b，长度 3 为 aba 与 bab，长度 5 为 ababa 与 aabab，长度 6 为 ababaa 与 baabab，长度 7 为 ababaab 与 abaabab，长度 8 为 ababaaba 与 babaabab，均不相同。

所以所有符合条件的长度之和为 2+4=6，选择 B；长度 9 对应整个字符串，不满足“真”的要求。

合并时，左右两段都已经有序。原条件 a[i]<=a[j] 会在相等时优先取左段元素，因此只有 a[i]>a[j] 才进入 else，累加严格逆序对。

改为 a[i]<a[j] 后，进入 else 的条件变为 a[i]>=a[j]。由于左段有序，从 i 到 mid 的每个剩余元素都不小于 a[i]，因而也都不小于当前右段元素 a[j]，应计入 mid-i+1 对。

这些左段元素在原数组中的位置都早于右段元素；递归合并又会保证每一对跨段元素恰好在相应的一次合并中被计算。

于是最终统计的是原下标满足 i<j、数值满足 a[i]>=a[j] 的所有数对，选择 C。例如数组 [2,2] 原结果为 0，修改后为 1，新增的正是相等数对。

函数是二进制快速幂：a 每轮平方，b 每轮右移；若当前 b 的最低位为 1，就把当前 a 乘入 r。因此它计算的是 $2^{100}\bmod1000$。

把 100 拆成 $64+32+4$。连续平方并取模得到：$2^4\equiv16$，$2^8\equiv256$，$2^{16}\equiv536$，$2^{32}\equiv296$，$2^{64}\equiv616\pmod{1000}$。

按照程序的低位到高位顺序，b 依次为 100、50、25、12、6、3、1，只有 b=25、3、1 时乘入 r，对应指数位 4、32、64。

所以 r 依次变为 16、$16\times296\bmod1000=736$、$736\times616\bmod1000=376$，最终返回 376，选择 B。

输入的前 32 位都是 0，第 12—14 行又将后 12 位设为 0，因此进入消元循环前 a[0] 到 a[43] 全为 0。

处理每个 i 时，a[i]==0 都成立，执行 continue 跳过整个异或循环，所以没有任何元素发生变化。

最后输出循环只访问 a[32] 到 a[43]，共 12 个位置，输出为 000000000000。故断言正确。

考察消元循环处理位置 i 的瞬间：若 a[i]=0，程序直接跳过，该位保持 0；若 a[i]=1，则 j=0 时执行 a[i]^=gen[0]，而 gen[0]=1，所以该位变为 1 XOR 1=0。

同一轮后续 j>0 的操作只影响 i 之后的位置。以后处理 i+1、i+2 等位置时，写入下标也只会更大，不会再次修改 a[i]。

因此“每轮结束后，a[0] 到 a[i] 全为 0”是循环不变量。32 轮结束后，a[0] 到 a[31] 必然全为 0，断言正确。

数组 a 定义在 main 函数外，是具有静态存储期的全局数组；程序开始执行前，它的全部元素已经被初始化为 0。

读入循环只覆盖 a[0] 到 a[31]，没有改动 a[32] 到 a[43]。所以即使删除显式补零循环，后 12 个元素在进入消元前仍然都是 0。

删除前后消元的初始数组完全一样，后续程序也一样，输出自然不会改变。因此“会改变结果”的断言错误。

本程序只处理一次输入；不能把这一结论直接推广到重复使用且已被修改的数组。

gen[13] 声明了 13 个元素，下标为 0 到 12，对应二进制串 1100000001111。

程序从左到右消去被除数的高位：当 a[i]=1 时，将 gen[0] 与 a[i] 对齐，gen[1] 与 a[i+1] 对齐，依此类推。gen[0]=1 正好用于消去当前最高的非零位，因此 gen[0] 是除数最高位。

若按多项式理解，gen 表示 $x^{12}+x^{11}+x^3+x^2+x+1$，最高次数为 12，但系数共有 13 个。它是参与除法的生成多项式，而不是被除数。

所以选择 C；13 位除数最终留下的余数最多为 12 位，两者不要混淆。

先看输入如何变为被除数：程序把 32 位输入放在 a[0..31]，再在后面补 12 个 0，得到一个 44 位串，即题目中所写的 $M\times2^{12}$。

随后从最高位开始扫描。当前位为 0 时跳过；为 1 时，将 13 位 gen 与当前位置对齐并逐位异或，把当前最高位消为 0。这正是模 2 多项式长除法，其中减法使用 XOR，不产生借位。

全部 32 个位置处理后，前 32 位均为 0，后 12 位就是次数小于 12 的余式的系数，程序将它们完整输出。因此选择 B。

这里不是只与 gen 异或一次，也不是普通整数除法取模；模 2 除法的运算规则是关键。

删除 continue 判断后，不论 a[i] 是 0 还是 1，每个 i=0..31 都会对 a[i..i+12] 执行一次固定的异或。

于是每个最终数组元素都等于“该位置初值”异或“所有覆盖该位置的 gen 元素”。覆盖哪些位置只由两个循环的下标决定，不再受输入影响。

程序输出的 a[32..43] 初值全为 0，且 XOR 不会把别的位置的 a 值传递过来，因此这 12 位完全由固定操作决定，与输入 s 无关，选择 C。逐位合并这些固定异或，输出为 100000000101。

下标最大为 31+12=43，没有数组越界；a[0] 最终是输入首位 XOR 1，未必为 0。

查询区间是 [2,5]，包含 2、6、3、3，长度 x=4。注意本程序的对数表在 i=4 时仍满足 pw[2]>=4，所以 lg[4]=1，查询采用长度 $2^1=2$ 的表项。

左段起点为 L=2，对应 dp[2][1]=gcd(2,6)=2；右段起点为 $R-2^1+1=4$，对应 dp[4][1]=gcd(3,3)=3。

最终输出 gcd(2,3)=1，断言正确。这两段恰好拼成整个查询区间，因此这里虽然 lg 的定义与常见写法不同，仍能得到正确 GCD。

当 L=R 时，区间长度 R-L+1=1。对数表初始化 t=0，而 pw[1]=2>=1，所以 lg[1]=0。

左边取 dp[L][0]；右边的起点为 R-pw[0]+1=R-1+1=R=L，因此右边也取 dp[L][0]。

建表时 dp[L][0]=a[L]，故输出 gcd(a[L],a[L])=a[L]，断言正确。虽然同一个数被合并了两次，但 GCD 具有幂等性，不会改变结果。

程序查询的是区间内所有数的最大公约数。对于正整数，公约数必须整除每一个数，因此最大公约数不可能大于区间的最小值；题目中的“不小于”方向相反。

例如取长度为 2 的区间 [2,3]。此时 lg[2]=0，程序合并两个单点表项，输出 gcd(2,3)=1，而区间最小值为 2，满足 1<2。

一个反例即可否定“一定”的说法，所以断言错误。当区间最小值恰好整除所有其他数时，GCD 才等于这个最小值。

先看初始状态 dp[i][0]=a[i]，表示从 i 开始、长度为 $2^0=1$ 的区间 GCD。

递推时，dp[i][j-1] 对应左半段 $[i,i+2^{j-1}-1]$，dp[i+2^{j-1}][j-1] 对应右半段 $[i+2^{j-1},i+2^j-1]$。

两段长度都为 $2^{j-1}$，首尾相接且没有遗漏。利用 GCD 的结合性，将两段 GCD 再求一次 GCD，就得到整个长度 $2^j$ 区间的 GCD。

因此 dp[i][j] 保存从 a[i] 开始连续 $2^j$ 个数的最大公约数，选择 B。例如 dp[i][2] 对应 4 个数，而不是 2 个数。

初始化第 0 层需要 n 次赋值，代价为 $\Theta(n)$。之后 j 从 1 增加到 lg[n]，有效层数为 $\Theta(\log n)$。

在第 j 层，i 需满足 $i+2^j-1\le n$，因此恰有 $n-2^j+1$ 个合法起点。题目规定每次 GCD 按常数时间计算，所以总工作量为 $n+\sum_{j=1}^{\mathrm{lg}[n]}(n-2^j+1)$。

各层最多处理 n 个起点，得到 $O(n\log n)$ 上界；前面约 $\log_2 n-1$ 层，每层又至少处理约 n/2 个起点，得到 $\Omega(n\log n)$ 下界。

因此建表复杂度为 $\Theta(n\log n)$，选择 B。查询次数 m 不参与建表，且本题不额外计入欧几里得算法自身的复杂度。

关键是第 15 行写的是 pw[t+1]>=i：当 i 恰好等于下一个 2 的幂时，t 还不增加；只有超过它才增加。

例如 lg[1]=lg[2]=0，lg[3] 到 lg[4] 为 1，lg[5] 到 lg[8] 为 2。由此可见，t=5 对应的区间是 $2^5<i\le2^6$。

检查两端：i=32 时仍为 t=4；i=33 时增加到 5；i=64 时仍满足 64>=64，保持 5；i=65 时才增加到 6。

因此 lg[x]=5 当且仅当整数 x 属于 [33,64]，选择 D。

fa[2..5]={1,2,3,4} 表示 2 接在 1 下、3 接在 2 下、4 接在 3 下、5 接在 4 下，整棵树是一条 1—2—3—4—5 的链。

全局数组 f 和 ans 初始为 0。倒序处理 i=5 时，候选值为 0+0+1=1，随后 f[4]=1；处理 i=4 时，候选值为 0+1+1=2，随后 f[3]=2。

继续处理 i=3、2，候选值依次为 3、4，f[2]、f[1] 也依次更新为 3、4。

所以最终 ans=4，断言正确；它统计路径边数，不是链上 5 个结点的数量。

f[1] 记录从根结点 1 向下出发能走到的最远距离，即树高；ans 则会把来自不同子树的两条路径接起来，记录任意两点之间的最长距离。

取最小反例 n=3、fa[2]=fa[3]=1。处理 i=3 后，f[1]=1、ans=1；再处理 i=2 时，候选值 f[1]+f[2]+1=1+0+1=2，ans 变为 2，而 f[1] 仍为 1。

对应最长路径是 2—1—3，两条边；根到任一叶子只有一条边。因此 f[1] 不一定等于 ans，断言错误。

原程序先用 f[fa[i]]+f[i]+1 更新 ans，再把当前子树的高度加入父结点。此时旧的 f[fa[i]] 只来自已经处理的其他子树，或父结点自身，能与当前子树组成合法路径。

如果先更新父结点，f[fa[i]] 可能已经包含当前 i 的贡献；随后再加 f[i]+1，就可能把同一条分支重复计算两次。

例如 n=2、fa[2]=1：原顺序先得到候选 0+0+1=1，再令 f[1]=1，输出 1。交换后先令 f[1]=1，再算 1+0+1=2，错误地输出 2。

所以交换会影响结果，断言错误。状态合并时要区分“加入当前子树之前”和“加入之后”的含义。

条件 fa[i]<i 保证每个后代的编号都大于祖先，因此按 i 从 n 到 2 倒序处理时，当前结点 i 的全部子树都已处理完，f[i] 已是它到最远后代的距离。

设父结点为 p。合并 i 之前，f[p] 是 p 经过此前已处理分支能达到的最大距离；当前分支提供的距离为 f[i]+1。将两者相加，就得到一条经过 p、连接两个不同方向的合法路径。

程序先用这个候选值更新 ans，再更新 f[p]，避免重复使用当前分支。任意最长路径都可在两端的最近公共祖先处拆成这样两段，所以枚举各子树合并时不会漏掉直径。

因此 ans 是树中距离最远两点之间的边数，选择 A；根到最远叶子的边数只是 f[1]。

父结点序列说明：根 1 的孩子为 2、3；2 的孩子为 4、5；3 的孩子为 6、7。因此左右两棵子树的高度都是 1，根到叶子的距离为 2。

倒序处理 7、6 后，f[3]=1，子树内部最长路径 6—3—7 长度为 2；处理 5、4 后，同理 f[2]=1。

处理 i=3 时，根的已有高度为 0，候选为 0+1+1=2，并更新 f[1]=2。再处理 i=2 时，候选为 2+1+1=4，ans 更新为 4。

一条实际达到该长度的路径是 4—2—1—3—6，共 4 条边，所以选择 C。

10 个结点的树一共只有 9 条边。要让直径达到 9，某条简单路径必须经过全部结点和全部边，所以整棵树必须是一条链，不能存在旁支。

由于每个结点满足 fa[i]<i，从根 1 向任意一端走时，编号必须严格递增。因此只要决定每个结点位于根的哪一侧，该侧的排列就只能按编号从小到大，父结点也随之唯一确定。

为避免左右两侧交换造成重复，可以规定结点 2 所在的一侧为固定侧。剩余结点 3 到 10 共 8 个，各自独立选择放在这一侧或另一侧；同侧按升序串接即可，全部满足父编号较小的条件。

于是共有 $2^8=256$ 种不同的父结点输入，选择 C。某侧为空也允许，此时根 1 位于整条链的端点。

路线的目标权值是正边经过次数减去负边经过次数后取绝对值，因此每次走正边应贡献 +1，走负边应贡献 -1。

后面 BFS 遍历边时，用 w[i]>0 设置 p=1，表示所在连通分量出现正边；用 w[i]<0 设置 ng=1，表示出现负边。因此两类边的编码必须分居 0 的两侧。

表达式 op[0]=='+' ? 1 : -1 正好满足要求，选择 C。它还会通过两次 add 把相同符号写入无向边的两个方向，反向走并不会把正边变成负边。

若把负边编码成 0，w[i]<0 永远不成立，程序会误判该分量没有负边，后面的分类讨论也就失效。

数组队列采用左闭右开的有效区间 [hh,tt)：hh 指向下一项待取元素，tt 指向下一次入队应写的位置。

执行 q[tt++]=s 后，hh=0、tt=1，队列中有一个元素。只要 hh<tt，就至少还有一个元素可处理；取出时执行 q[hh++]。

当 hh==tt 时，所有已入队的元素均已取完，应结束循环。因此条件应为 hh<tt，选择 D。

例如图中只有起点所在的小连通分量，BFS 不会访问全部 n 个点，所以不能以 hh<n 或 tt<n 判断队列是否为空；hh<=tt 则会在空队列时多取一次。

d[y]==-1 表示结点 y 尚未被 BFS 发现；当前从已出队的 x 沿一条边到达 y，因此这条路径的长度为 d[x]+1。

BFS 按距离从小到大处理结点，第一次发现 y 时已经找到边数最少的路径，所以应赋值 d[y]=d[x]+1，选择 B。

这里 d 统计无权图中的边数，不累加边的正负号。当所在连通分量只有一种符号的边时，任意路线的绝对权值就等于其长度，程序才直接用 d[t] 作为答案。

赋值 d[y] 后立即入队，也保证同一个结点不会被反复加入队列。

c 数组做二染色：起点颜色为 0，每发现一个新点 y，就令 c[y]=c[x]^1，使树边两端颜色相反。

如果 y 已经被访问，则需要检验当前这条边是否仍满足“两端异色”。若 c[y]==c[x]，这条边连接了同色点，与二分图要求冲突，应令 ok=0。

从 BFS 树看，同色两点之间的树上路径长度为偶数，再加入当前这条边，就得到一个奇环；而二分图恰好不能含奇环。因此应填 c[y]==c[x]，选择 A。

正负边只影响路线的符号和；二分图性质只由图的连接关系决定，与 w[i] 的正负无关。

执行到⑤时，程序已经排除了 t 不可达，以及连通分量中只有一种符号边的情况。现在 s、t 连通，而且该分量同时存在正边和负边。

先看奇偶性：每走一条边，符号和增加 +1 或 -1，两者模 2 都等于 1。因此符号和的奇偶性与路线长度相同。若图是二分图，s、t 同色时所有路线长度都为偶数，异色时都为奇数；若含奇环，则可以绕该奇环改变路线长度的奇偶性。

再说明为什么能把绝对值降到 0 或 1：取一条经过正、负两类边并最终到达 t 的路线。在经过正边时插入一次“沿该边走过去再走回来”，符号和增加 2；在负边处插入同样的往返，符号和减少 2。重复这些往返，就能在保持奇偶性的前提下把符号和调整到最靠近 0 的值。

为了经过两类边而增加的往返路段长度是偶数，不改变原路线奇偶性；若需要翻转奇偶性，可以再通过奇环。因此存在偶数长度路线时最小绝对值为 0，否则为 1。

所以输出 0 的条件是“不是二分图，或者 s、t 同色”，即 !ok || c[s]==c[t]，选择 C。