2026 ICPC 西安 / UCUP 5. Stage 4: GP of Xi'an

VP。

ID	Diff	Description	Solution	Penalty	Review
C	Medium	空序列 $c$，任意操作：花费 $X$，将 $A$ 的所有元素按顺序追加到 $c$ 的末尾；花费 $Y$，将 $c$ 中某一个元素加 $1$ 或减 $1$；花费 $Z$，从 $c$ 中删除一个元素。最小化将 $c$ 变为 $B$ 的总花费。	(1) $f(i,n)$：已经生成 $B$ 的前 $i$ 个元素，$B_i$ 使用 $A_k$ 生成。$f(i,0)$：已经追加了一份新的 $A$，但还没有处理其中任何位置。$\mathcal{O}(MN^2)$。 (2) 定义 $g(i,k)=f(i,k)-k Z$ 优化转移，$\mathcal{O}(MN)$。	73	公式的优化 DP。
D	Hard	求 $1 \sim N$ 的排列 $P$，满足 $A_i=1/0/?$ 表示 $P[1,i]$ 是连续集 / 不是连续集 / 随便；$B_i=1/0/?$ 表示 $P[i,N]$ 是连续集 / 不是连续集 / 随便。	(1) 令 $A_1=B_N=A_N=B_1=1$。若 $2\le j\le i\le N-1$，且 $B_j=A_i=1$，那么 $A_{j-1}=B_{i+1}=1$。如果冲突则无解。 (2) 构造。若 $A_i=B_{i+1}=1$，从 $i$ 处切成两块，左右两侧值域不交。按顺序给各块分配数字，每块内部先降序排列，再微调：第一块只需额外满足 $A$；最后一块只需额外满足 $B$，其它块内部无 1，自然已经满足。 (3) 特判没有分界（如 1?001, 1?111），设 $l=\max\{i<N:A_i=1\}$，$r=\min\{i>1:B_i=1\}$，一定有 $r-l\ge2$，否则切成了两块。(a) 若 $r=l+2$，中间唯一的位置 $c=l+1$ 必须满足 $A_c=1$ 或 $B_c=1$，否则两者都是 $0$ 时前后两个连续集只剩一个数没放，至少一边会连续，无解（如 11001, 10011）。把可用的 $?$ 补成 $1$，按 (2)。(b) 若 $r-l>2$，在 $l+1$ 放 $1$，在 $r-1$ 放 $N$，其余的三块按 (2)。$\mathcal{O}(N)$。	*	没有分界的情形要考虑清楚。
G	Master	长度为 $2^N$ 的序列 $A$。任意操作：选择 $m$ 和 $k$，对 $0 \le i \le m$，将 $A[i \oplus k]$ 减少 $1$。最小化操作次数，使变为全 0 数组。			非常困难。
H	Medium	初始 $M=0, P=0$。回合开始时，可花费 $X$ 将 $M$ 增加 $1$，或花费 $Y$ 将 $P$ 增加 $1$。第 $A_i$ 回合须 $M+P \ge B_i$。每个回合结束时，$P$ 变为 $\max(P-1, 0)$。最小化总花费。	先算仅使用 $P$ 的方案，再枚举 $M$。把 $M$ 增加到 $M+1$ 时，若之前某次操作把 $P$ 补到 $B$，且 $P\le M<B$，那么现在就能少买 $1$ 单位 $P$。设这种操作共有 $c$ 次，那么节省 $cY$，净成本是 $X-cY$，$\mathcal{O}(Q \log V)$。	162	图形化更容易发现性质。
J	Hard	长度为 $2N$ 的整数序列 $A$，每个整数恰好出现两次。构造长度为 $2N$ 的 RBS $S$，使分别连接匹配的左右括号，连接 $A$ 中的每个值的两次出现后，得到包含 $2N$ 条边的环。	先随便构造一个 RBS，得到的图是若干互不相交的环。考虑把两个环合并的方法，即从两个不同的环中各删去一条边，再交叉连接这四个端点。在 RBS 中，将相邻的 )( 改为 ()。用并查集判断是否属于同一个环，$\mathcal{O}(N)$。	46	很困难，不好想。
		$N$ 点 $M$ 边无向简单图 $G$。称一个 $1 \sim N$ 的排列 $P$ 为图 $G$ 的合法标号，当且仅当对边 $(u, v)$，均满足 $P_u + P_v \le N + 1$。first 依据图 $G$ 和合法标号 $P$，输出非空二进制串 $S$。second 依据 $G$ 和 $S$，输出任意合法标号 $P'$。
		隐藏 $N$ 节简单连通边仙人掌（每条边至多属于一个简单环）。询问两个节点 $x, y$ 和集合 $S$，交互器返回在删除 $S$ 中所有点及其关联边后 $x, y$ 是否连通。询问代价 $\lvert S \rvert -1$。总询问次数 $\le 3N^2$，总代价 $\le N\lceil \log_2 N\rceil + 2N$。回答图结构。
M	Easy	模拟。	模拟。	38

G (draft)

建立满二叉字典树。

对某棵子树，称

• 整操作：操作覆盖这子树的全部叶子；
• 零操作：操作位于这棵子树内但不覆盖全部叶子。

合法操作的转化

需要最少的区间覆盖整个字典树。

考虑合并两个子节点的操作：

• 左整操作与右整操作：可以合并；
• 整操作与另一边的零操作：可以合并；
• 左右零操作：不能合并。

DP

对子树 $u$，定义

• $a$：最多有多少个整操作，$a=\min_{c \in \text{children}(u)} A_{c}$。
• $c$：最少需要多少个零操作，即无论整操作怎么安排，都至少需要 $c$ 次零操作。
• $b$：零操作为 $c$ 不变的情况下，整操作可以从 $a$ 降到 $a-b$，而且对任意 $0\le t\le b$，都存在方案满足 $(a-t)$ 次整操作 + $c$ 次零操作。也就是说，可以把整操作拆开并重新分配给零操作，使零操作的数量不增加，但整操作少了一次。

答案是 $a-b+c$。

转移步骤：

1. 左右整块先配对，得到 $a \gets \min(a_L,a_R)$。
2. 整块若有剩余，只会出现在一侧，设为 $a_L',a_R'$，有两个去向：
   • 和另一边的零操作合并，$c \gets \min(a_L',c_R)+\min(a_R',c_L)$；
   • 使用所在子节点的 $b$，在子节点内部吸收掉，$c \gets \min(a_L',b_L,c_L)+\min(a_R',b_R,c_R)$。
3. 整块、零块若还有剩余，加到 $c$ 上。
4. 计算父节点还能减少多少整块，$b \gets \min(a, \ b_L+c_R,\ b_R+c_L)$。