普及组 CSP-J 2026 初赛模拟卷 10

当前目录通常不在命令搜索路径中，因此运行其中的可执行文件要写成 `./main`。

`vector<int> a(5,2)` 创建 5 个元素且每个值为 2，累加结果为 $5\times2=10$。

连续取余：$54321\bmod12345=4941$，$12345\bmod4941=2463$，$4941\bmod2463=15$，$2463\bmod15=3$，最终余数为 0，因此最大公约数是 3。

$100!$ 中因子 2 远多于因子 5，末尾零的个数等于因子 5 的总数：$\lfloor100/5\rfloor+\lfloor100/25\rfloor=20+4=24$。

`push_back('j')` 在字符串末尾追加一个字符，因此 `s` 变为 `cspj`。

字符串下标从 0 开始，子串 `go` 的首字符 `g` 位于下标 2，因此 `find` 返回 2。

5 个有标号顶点之间共有 $\binom{5}{2}=10$ 对可能的边，每条边都可独立选择存在或不存在，因此图的总数为 $2^{10}=1024$。

外层执行 $n$ 次，内层每次将 `j` 除以 2，执行 $O(\log n)$ 次，总复杂度为 $O(n\log n)$。

最高位为 1，表示负数。按无符号数计算 `10101011` 为 $171$，8 位补码对应的有符号值为 $171-2^8=-85$。

计数排序在按原顺序写入或使用前缀位置的常见实现中可以保持相等元素的相对顺序；其余三种常见实现不稳定。

$3=(011)_2$，$5=(101)_2$，所以 `a|b` 为 7、`a&b` 为 1，二者异或得到 6。

第一个弹出 3 时，栈内仍有 1、2，且栈顶是 2。第二个数可以立即弹出得到 2，也可以先继续入栈到任意 $k\in[4,n]$ 再弹出 $k$；共有 $1+(n-3)=n-2$ 种。

无向树必然连通、无环，并恰有 $n-1$ 条边；这些都可作为必要条件。若 $n=1$，唯一顶点的度数是 0，仍构成一棵树，因此“每个点度数都大于 0”不是对所有 $n$ 都成立的必要条件。

邻接矩阵需要保存 $n\times n$ 个位置，因此空间复杂度为 $O(n^2)$。

若最优拆分中出现加数 5，可把它替换成 2 和 3，和仍为 5，而乘积由 5 增大为 $2\times3=6$，与最优性矛盾。因此最优拆分中不可能保留 5。

`x[i]` 可以重复而最终仍无 0，例如本题 Q21 的输入位置序列 `1 1 2 3 1 1 2 3` 含重复值，程序却输出 `6 7 8 5 2 3 4 1`，恰好覆盖 1 到 8。

当 `x[i] > i` 时，第 9 行不会移动已有元素，却会向尚未纳入当前序列的位置写入。比如 $n=2,x=[2,2]$ 时最终 `q` 为 `[0,2]`，既含 0 又缺少 1，不是排列。

第 $i$ 轮写入的新值就是此前未出现过的编号 $i$；右移只复制已有非零值并覆盖原位置，不会把一个旧编号分裂成两个保留副本。某些编号可能被覆盖掉，但所有仍非零的编号保持互不相同。

即使 `x[i]` 单调不降，新写入的编号 $i$ 也可能插到较小编号前面。例如 $n=3,x=[1,1,2]$：前两轮得到 `[2,1]`，第三轮后为 `[2,3,1]`，输出并非单调不降。

若每轮都有 `x[i] >= i`，内层循环不执行，总时间为读写和外层循环的 $O(n)$。若始终 `x[i]=1`，第 $i$ 轮移动 $i-1$ 次，总移动数为 $\sum_{i=1}^{n}(i-1)=\Theta(n^2)$。

依次把编号 $i$ 插到位置 `x[i]`，前四轮得到 `[2,3,4,1]`；再在位置 1 插入 5、6，得到 `[6,5,2,3,4,1]`；最后把 7 插入位置 2、8 插入位置 3，结果为 `[6,7,8,5,2,3,4,1]`。

初始化后每个 `nxt[i]` 都是 $1..n$ 中的后继编号；删除节点时执行 `nxt[cur]=nxt[nxt[cur]]`，写入的仍是另一个正编号。程序从未给 `nxt` 赋 0，因此其他位置不会都变成 0。

原代码先把 `nxt[nxt[cur]]` 赋给 `nxt[cur]`，随后再把更新后的 `nxt[cur]` 赋给 `cur`。合并式右侧先求出同一个新后继，再依次赋给 `nxt[cur]` 和 `cur`，状态变化相同。

原循环在剩 1 个节点时结束；改为 `n > 0` 后只多执行一次。此时 `nxt[cur]=cur`，故两条语句都仍令其等于 `cur`，随后 `n` 减为 0，最终输出不变。

输入 `n=-1` 时，初始化循环的条件 `i<=n` 一开始就不成立，主循环条件 `n>1` 也不成立；程序不会访问 `nxt`，而是直接输出初始化后的 `cur=1`，不会因此异常退出。

初始化 `nxt[1..n]` 需要 $n$ 次操作；主循环每轮让 `n` 减 1，从 $n$ 执行到 1，共 $n-1$ 轮，且每轮为常数操作。因此总时间复杂度为 $O(n)$。

程序每次删除当前节点的下一个节点，是步长为 2、从 1 开始的约瑟夫问题。设 $2^p\le n<2^{p+1}$，幸存编号为 $2(n-2^p)+1$；$10000-8192=1808$，故输出 $2\times1808+1=3617$。

虽然单个 `x[i]` 和下标都在 `int` 范围内，但一个等差位置序列最多累加 10000 个数，和可达 $10000\times1000000=10^{10}$，超过 32 位有符号整数上限，改成 `int` 会溢出。

条件只保证末项下标不超过 500，并未保证不超过实际的 `n`。例如取 $n=100,i=50,d=2,k=100$，末项下标 248 不超过 500，且 `k <= n`；原程序会把 `k` 截为 26，去掉截断后却读取未预处理的 `s[2][248]`，结果随之改变。

数组 `s` 含 $509\times10009$ 个 `long long`，仅它就占约 $509\times10009\times8\approx40.8$ MB；再加上 `x` 等变量，显然远大于 5 MB。

可先存下 $m$ 个询问并按小步长 `d` 分组，每次只用一个长度为 $n$ 的数组计算当前 `d` 的前缀和，回答该组后复用空间；大步长询问仍直接枚举。这样时间量级不变，存储输入、询问和答案只需 $O(n+m)$。

令 $D=\Theta(\sqrt m)$，预处理 $D$ 种步长各扫 $n$ 个位置，耗时 $O(n\sqrt m)$。当 $d>D$ 时，每次查询至多枚举 $n/d<O(n/\sqrt m)$ 项，$m$ 次合计仍为 $O(n\sqrt m)$，小步长查询为 $O(1)$。

若 `d` 为负数，必有 `d <= D`，程序进入小步长分支并访问 `s[d][...]`，第一维下标直接为负，必然越界。`i` 或 `k` 为负时，相关算式仍可能因其他正变量而得到合法下标；`n` 为负也可能使循环直接跳过。

拆分至少包含两个连续正整数。若首项 $i>n/2$，则最小的两项和 $i+(i+1)>n$，不可能形成方案；枚举到 `n / 2` 已覆盖所有可能首项。

每更换一个首项 $i$，都要重新累计序列 $i+(i+1)+\cdots$，因此进入内层循环前必须执行 `sum = 0`。否则 `sum` 会保留上一个首项枚举结束时的值。

内层循环应在 `sum < n` 时继续把当前 `j` 加入；一旦 `sum` 达到或超过 $n$ 就停止，再由后续判断是否恰好等于 $n$。因此条件应为 `sum < n`。

内层循环结束时，`sum` 是以 $i$ 为首项的连续整数和中第一个不小于 $n$ 的值。只有 `sum == n` 才表示找到了一种合法拆分，应执行 `ans++`。

固定首项 $i$ 时，需累加的项数满足 $ti+\frac{t(t-1)}{2}=O(n)$；当 $i\ge\sqrt n$ 时有 $t=O(n/i)$，求和得到 $\sum_{i=\sqrt n}^{n/2}O(n/i)=O(n\log n)$，较小的 $i$ 共贡献 $O(n)$。故总复杂度为 $O(n\log n)$。

`cnt` 表示当前候选值尚未被抵消的票数；当 `cnt == 0` 时，旧候选已完全抵消，应把当前读入的 `x` 选作新候选。故条件填 `cnt == 0`。

触发①说明当前没有有效候选，刚读入的数 `x` 应成为新候选，因此执行 `s = x`。之后同一轮比较 `x == s`，会给新候选记 1 票。

读入值与当前候选相同就应增加支持票，不同则用一票相互抵消，所以分支条件必须是 `x == s`。

当 `x == s` 时，当前元素支持候选值，应执行 `cnt++`。特别地，刚在 `cnt == 0` 时选定的新候选也会通过这里把票数从 0 加到 1。

当 `x != s` 时，可将当前元素与一个候选元素配对抵消，因此执行 `cnt--`。绝对众数出现次数超过一半，所有异值配对后它仍有剩余票，最终候选 `s` 就是答案。