2025 ICPC WF

· · 题解

A

考虑根被插入的时间，在根被插入之前的数都会放到同一个儿子，插入之后的数会交替往两边插入，形式一定形如 \texttt{LLLLXRLRL} 或 \texttt{RRRRXLRLRL}，这样我们就递归到了儿子的子问题。合并的时候分类讨论一下 sz_{ls} 和 sz_{rs} 的大小关系，暴力合并的复杂度只有 O(\min(sz_{ls},sz_{rs}))，时间复杂度 O(n\log n)。

D

每走一步就能得到走的方向和其他空地方向的优先级关系，暴力维护有没有出现环就做完了。O(rc+|s|)。

E

题目相当于每次连 (a+n,b) 的双向边，询问有多少 (u,v) 满足有 x\in\{u,u+n\},y\in\{v,v+n\}，(x,y) 连通。

考虑并查集合并的时候启发式合并连通块的颜色数，然后我们先认为答案是每个连通块的 \binom{sz}2 的和，这样只有一个点对在两个连通块同时出现的时候才会算重，考虑维护这样的点对个数。

合并两个连通块 S,T（|S|\ge|T|） 的时候，首先个数要减去 \binom{|S\cap T|}2，然后对于 x\in T,x\notin S，如果 x 在第三个集合 U 中出现，个数要加上 |S\cup U|。由于每个数只出现两次，可以离线下来把每个相同的数对放在平面上 DFS 序对应的点二维数点。时间复杂度 O(n\log^2n+m\log n)。

F

按 p 从大到小贪心考虑，p 的位置必定填的是一个所有猫的位置集合的交中的数，如果交中所有数都已经在更大的 p 中出现过或者不同的数已经超过 m-p+1 个那就不合法，否则显然存在方案。时间复杂度 O(n+m) 或 O(n+m\log m)。

H

考虑小凯的疑惑，设 g_i=\gcd(a_1,\dots,a_i)，所有 kg_n+\sum\limits_{i=2}^n[g_{i-1}\nmid a_i]g_{i-1}a_i 肯定能被表示出来，这个东西只有 O(V^2)。如果 m 只有 O(V^2) 这个级别就暴力，否则数位 DP 算所有 g_n 的倍数。O(V^2+V\log m)。

I

首先对于每个 i 做 n 次 (i,1) 尝试让 k 增加，这样可以使序列变成一个排列。

对于 i\in[1,n-1]，我们尝试确定 a_1-i 的位置。我们把 a_2\sim a_n 都 +i 之后 k 显然是 n-1，然后序列中没有 a_1+i，对每个 j 询问 (j,i) 即可检查他的值是不是 a_1-i。询问次数大约 3n^2。

J

首先我们需要 k\in[2n-1,n^2]。打表发现 k\ne n^2-2。

考虑递归构造，如果 k\le4n-4 就把 n 放在最下面，否则放在最上面，这样在 n 足够大的时候 k\in[2n-1,n^2]\setminus\{n^2-2\}，n\le 10 的时候暴力全排列。O(n)。

K

我们需要 d_{i,j}+d_{i+1,j+1}-d_{i+1,j}-d_{i,j+1}=0。我们可以把这些等式随意加起来，这样就是“一个环，每个点都是直角，奇数位和等于偶数位和”的限制。对每个行列赋权使得 f_i+d_{i,j}=g_j，要求 \max f_i\le\min g_j，连边 DFS 讨论一下即可。O(n+m+k)。

L

往下走肯定是直着往下走，差分覆盖一下能躲太阳的 y。O(n+V)。