2026 CCPC 长春 (热身赛 + 正赛)

board

VP alongside ctt & 奶灰 under 新赛制

1. 新赛制全错。开赛看了一圈感觉 DEGIL 可能可做，完美避开签到。
2. 有几个题看着吓人就觉得不能做了。得先想想再判断，每题至少先转化几层，思考五六分钟，比如本场的 M，从完全读懂到出思路到写代码也就十几分钟。
3. 已经知道通过率很高，那这题肯定不难，不可能用到主席树这类数据结构。
4. 没想清楚觉得大概率错的就不要上机，除非机子闲着也没题可做的时候。相反，有点思路就别犹豫，五小时的时间十分有限。

ID	Diff	Description	Solution	Penalty	Review
热身赛 C	Hard	【交互】长度为 $N$ 的隐藏排列 $p$ 和隐藏颜色。$\lceil N/2\rceil$ 次询问下标 $i,j$，若颜色为黑，返回 $p_i+p_j$，若颜色为白，返回 $p_i p_j$。确定颜色。	依次询问 $(2i-1, 2i)$，计算结果之和。白色下界：排序不等式，逆序和最小，$R=\sum \limits_{i=1}^{m}i(2m+1-i)$；黑色上界：$N=2m$ 时 $B = \frac{N(N+1)}{2}$，$N=2m+1$ 时 $B = \frac{N(N+1)}{2}-1$。$N\ge6$ 即 $m \ge 3$ 时都有 $R>B$。	AC
热身赛 D	Hard	【润两次】first 根据 $N$，输出串集合，字母只能使用一次，jury 打乱集合，打乱每个串，second 根据串集合还原 $N$。	Bell numbers / Restricted Growth String (RGS)。	AC
A	Medium	$N$ 行 $M$ 列非负整数矩阵 $A_{i,j}$。任意操作：对 $i \in [l, r]$，满足 $p_i \le p_{i+1}$，将 $A_{p_i, i}$ 分别减去 $1$。最小化操作次数，将 $A$ 变为全零。	设 $S_{j, i}$ 是第 $j$ 列的前 $i$ 项和，答案为 $\sum_{j} \max_{k} (S_{j, k}-S_{j-1, k})$。	103
		$N$ 点有根树，非叶子有权值 $Q_u$，且 $Q_0 = 0$，$Q_u \ge Q_{p_u}$。叶子有集合 $S_v$。选择 $K$ 个叶子，并为每个选中的叶子 $v$ 从 $S_v$ 中各选一个元素，满足选出的元素互不相同。最小化选出的 $K$ 个叶子两两之间 LCA 权值之和。	奇怪的限制直接流。考虑费用，设 $d_u = Q_u - Q_{p_u}$，则所求即 $\sum_u d_u \binom{s_u}{2}$。
C	Medium	长度为 $N$ 的序列。最小化修改位置，使 $A'$ 是一个长度为 $K$ 的循环排列不断重复后截取的前 $N$ 项。	只有 $A_{i}-i \equiv A_{0}$ 时，$A_{i}$ 不需要修改。用桶 $c_j$ 统计当 $A_{0}=j$ 时有多少个数不需要修改，即给 $c_{A_{i}-i}$ 自增。$\mathcal{O}(N)$。	27	比较巧妙。
		给定 $S=\{A, B, C\}$。每秒向 $S$ 中加入尽可能多的 $S$ 的两个数的中点（若为整数）。$Q$ 次询问 $X$ 的加入时间。	(1) 不妨设 $A=0<B<C$，枚举 $k$ 并解 $B p + C q = 2^k X$，得到最小的非负 $p$，若满足 $p+q \le 2^k$ 则答案为 $k$。 (2) 构造
E	Hard	构造 $N$ 点树，使得对 $k=1,2,3$，有恰好 $A_k$ 个下标 $i$ 满足 $\operatorname{dist}(i, i+1) = k$。	若仅有 $k=2$，由奇偶性知无解。对于 $N \le 8$，本地打表出所有可能。对于剩下的点，在一个点上挂叶子造 2，在相邻两个点上挂叶子造 3，在任意点上挂链造 1。	*	构造题不一定要构造。
		对排列 $p$，每秒删掉除端点外所有的谷。记 $a_{i}$ 为位置 $i$ 被删的时间。给定若干 $a_{X}=T$ 的限制，求合法排列数量。
G	Expert	长度为 $N$ 的 01 串 $A$，$M$ 个操作 $[L_{i}, R_{i})$ 表示 01 翻转。对于每个操作 $i$，回答若不使用 $i$，其余任意操作，能否将 $A$ 变为全 0。	对 $A$ 差分得到长度为 $N+1$ 的串，操作即同时翻转 $L_i, R_i$。连边 $L_i, R_i$，条件即每个连通块的异或和皆为 0。 (a) 若 $i$ 是割，则删去不影响答案，否则需要计算两个新连通块的异或和。用 EBCC 或 XOR-hash 判割，并处理缩点后子树权值。 (b) 线段树分治，回滚并查集维护：连通块的异或和；异或和为 1 的连通块数量。	XOR-hash / EBCC / DSU	建模。
		大小为 $N$ 的多重集，元素 $i$ 的重数 $A_i$。每秒随机选择一对不等的元素，并随机把一者改为另一者。求停时的方差。	方差太难了，这里求期望。设 $\Phi(A) = \sum_{i<j} A_i A_j$，则 $\Phi(A)-\Phi(A')=1$，因此停时期望即 $\Phi(A)$。		一眼不可做，求期望已经是 3000 分难度。
I	Hard	【润两次】first 根据二进制串 $P$，输出 $Q$，要求 $\lvert Q \rvert\leq \lfloor \frac{3 \lvert P \rvert}{2} \rfloor$，且没有子串 000、111；second 通过 $Q$ 还原 $P$。	(1) $Q$ 的差分不存在相邻的 0。3 位 $Q$ 的差分编码 2 位 $P$，令每组的最后一位是 1 以衔接。 (2) 更聪明的方法：规定 $Q[0] = P[0]$，后面用极长连续段的长度编码 $P$ 的每一位，其中，$P$ 中出现较少的字符编码为 2 长度，否则为 1 长度。	176+1	WA：没有还原前缀和。
J	Easy	长度为 $N$ 的序列 $a$ 满足 $M$ 个条件 $a_X \land a_Y=Z$，最小化 $\sum a$。	按位处理，先满足 1，其它填 0，同时检查是否满足 0。按位是不必要的。$\mathcal{O}(M)$。	38	唯一正确开出的签到。
K	Hard	长度为 $N$ 的全零数组 $a$。$M$ 次操作：第 $i$ 次将前缀 $[1, X_{i}]$ 或后缀 $[X_{i}, N]$ 全部赋值 $i$。$Q$ 次询问 $[L, R)$，全零数组开始依次执行第 $L$ 至第 $R$ 次操作，求最终不同数值个数。	双端队列模拟求出操作 $i$ 的有效时间 $[i, t_i]$，查询即二维偏序 $L\leq i <R \leq t_{i}$。$\mathcal{O}((M+Q)\log M)$。	*	类似 Chtholly 的均摊思想，不是什么高级数据结构。
		01 串。任意操作：把偶数长度回文子串替换成一个 0。最小化最终长度。
M	Easy	数组 $A$ 和值域 $M$，统计区间 $A[l,r]$ 的每个元素对 $2\leq m\leq M$ 取模后回文。	枚举中心 $c$，向外扩展半径 $r$，维护 $d = \gcd_{r}(A_{c+r} - A_{c-r})$，答案贡献 $d$ 的约数个数，特判 $d=0$。考虑到对数组求 $\gcd$ 的时间是 $\mathcal{O}(N+\log V)$ 而非 $\mathcal{O}(N \log V)$，因此总时间 $\mathcal{O}[N(N+\log M)]$。	212	模拟题。特判 0 的约数个数。