2026 ICPC 西安

ID	Tag	Diff	Description	Solution	Code	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$，但还没有处理其中任何位置。$O(MN^2)$。 (2) 定义 $g(i,k)=f(i,k)-k Z$ 优化转移，$O(MN)$。	AC	公式的优化 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)。$O(N)$。	AC	没有分界的情形要考虑清楚。
G		Master	长度为 $2^N$ 的序列 $A$。任意操作：选择 $m$ 和 $k$，对 $0 \le i \le m$，将 $A[i \oplus k]$ 减少 $1$。最小化操作次数，使变为全 0 数组。		AC	非常困难。
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)$。	AC	图形化更容易发现性质。
J		Hard	长度为 $2N$ 的整数序列 $A$，每个整数恰好出现两次。构造长度为 $2N$ 的 RBS $S$，使分别连接匹配的左右括号，连接 $A$ 中的每个值的两次出现后，得到包含 $2N$ 条边的环。	先随便构造一个 RBS，得到的图是若干互不相交的环。考虑把两个环合并的方法，即从两个不同的环中各删去一条边，再交叉连接这四个端点。在 RBS 中，将相邻的 )( 改为 ()。用并查集判断是否属于同一个环，$\mathcal{O}(N)$。	AC	很困难，不好想。
			$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	模拟。	模拟。	AC