icpc problems
Illuminati CERC 2024 problem I
题目大意：长度为 \(n\) 的 01 序列，每次按照一个排列置换，即每次第 \(i\) 的位置的元素移动到第 \(p_i\) 个位置，置换 \(k-1\) 次后得到一个 \(n\times k\) 的矩阵。给你这个矩阵，输出任何可行的排列，无解输出 "NO"。
数据范围：\(1\le N,K\le 10^5,N\cdot K\le 10^6\)。
solution
从列的角度来看这个矩阵，$p_i=j$ 相当于第 $i$ 列的前 $k-1$ 个元素依次等于第 $j$ 列的后 $k-1$ 个元素。把每一列的前 \(k-1\) 个元素形成的字符串按照字典序排序，把每一列的后 \(k-1\) 个元素形成的字符串也按照字典序排序，然后一一检查匹配。
Depth of Interval The 4th Universal Cup. Stage 13: Grand Prix of Ōokayama problem A
题目大意：给定一个长度为 \(n\) 的排列 \(P\)，定义函数
\[f(L,R)=\begin{cases} f(\min(a,b)+1,\max(a,b)-1)+1 & 1\le L<R\le N\\ 0 & \text{otherwise} \end{cases}\]其中 \(a\) 和 \(b\) 是 \(P\) 在区间 \([L,R]\) 中最小值和次小值的位置。
对于每一个 \(k=1,2,\cdots,n\)，输出有多少数对 \((L,R)\) 满足 \(f(L,R)=k\)。数据范围：\(1\le N\le 3\times 10^5\)。
solution
设 $P_0 = P_{n+1} = \inf$注意到，满足 \(\forall L\le i\le R,P_{L-1}\ge P_i\and P_{R+1}\ge P_i\) 的区间数目只有 \(O(n)\) 个（why?），我们称这种区间为好的区间。
注意到，好的区间有如下性质
- 好的区间只有 \(O(n)\) 个。（why?）
- 只有好的区间才会被别的区间转移到。
- 好的区间之间只会包含或者相离，不会交叉。
因此，我们可以由包含关系，为所有好的区间，构建出一颗树，可以在树上容易地得出，每一个节点的值，以及每一个节点转移到的区间的数量，统计答案即可。
Minimum Distance Tree The 3rd Universal Cup. Stage 39: Tokyo problem M
题目大意：给你一个 \(n\) 个点 \(m\) 条边的联通无向图，问是否存在一棵树，满足对于任意的点对 \(u,v\)，它们在图上的最短距离等于它们在树上的最短距离，只需要输出 "Yes" 或 "No"。
数据范围：\(2\le n\le 5\times 10^5,n-1\le m\le 5\times 10^5,1\le w_i(\text{边权})\le10^9\)
solution
注意到，如果存在一棵树满足条件，那么最小生成树一定满足条件。（why?）那么，随便找一棵最小生成树，然后判断每一条非树边的两个端点 \(u,v\) 都要满足它们在最小生成树上的距离小于等于该非树边的边权。
Imagined Holly The 2025 ICPC Asia Xi'an Regional Contest problem I
题目大意：给你一个 \(n\times n\) 的矩阵 \(A\)，构造一棵 \(n\) 个点的树，使得 \(u\) 和 \(v\) 路径上所有点编号异或和等于 \(A_{u,v}\)
数据范围：\(2\le n\le2000\)，保证 \(A\) 是对称矩阵，且 \(0\le A_{i,j}<2^{11},A_{i,i}=i\)。
solution
考虑三个不同的点 $i,j,k$，假设 $i$ 在 $j,k$ 的路径上，当且仅当 $A_{i,j} \bigoplus A_{i,k} \bigoplus A_{j,k} = i$，于是你可以知道每两个点之间的路径上有哪些点，接下来就变得很简单了。Expression CERC 2024 problem E
题目大意：给你一个只由 \(\max,\min,<=,<\) 和变量（小写英文字母）组成的表达式，问你能不能把它替换为只由 \(\min,<=\) 和变量组成的等价表达式。
能的话输出 "YES" 并且构造方案，不能输出 "NO"。
例如，((max a a) <= b)等价于(a <= b)数据范围：表达式包含最多 \(200\) 个二元运算符，最多包含十个不同的变量，变量的取值只会是 \(0\) 和 \(1\)。要求最后构造出来的表达式包含至多 \(40000\) 个二元运算符。
solution
假设存在一种操作取反(not)，那么
- \(\max(a,b)\) 操作等价于 \(a|b\)，可以转化成 \(!((!a)\&(!b))\) 即 \((\text{not}~(\min (\text{not}~a) (\text{not}~a)))\)。
- \(a<b\) 可以转化成 \(!(a<=b)\)，即 \((\text{not}~(a<=b))\)。
注意到 \(\text{not}~a\) 等价于 \(a<=0\)，于是只需要考虑如何构造 \(0\)。
首先，如果所有变量都取值为 \(1\)，我们是无论如何也构造不出 \(0\) 的。（why?）
否则，我们可以用 \(\min(a,b,c,\cdots)\)，即把所有变量取 \(\min\) 的方式来构造零。
Neo-Nim SEERC 2025 problem L
题目大意：现在有 \(n\) 堆石子，第 \(i\) 堆石子大小为 \(a_i\)。现在，Ana 和 Bob 在玩游戏，Ana 先手。
Ana 每次可以选择一堆大小至少为 \(2\) 的石子，从中选择移除至少两个，至多 \(k\) 个石子。
Bob 每次可以选择一堆大小不为零的石子，从中移除恰好一个石子。
不能操作的人输，问最后谁能赢。数据范围：\(1\le n,a_i\le 10^5,2\le k\le 10^5\)。
solution
首先，如果存在一堆石子大小为 \(1\) 或者两堆石子大小为 \(2\)，Bob 必胜。否则，当 \(k\ge 4\) 时，Ana 必胜。（why?）
以下讨论排除了存在一堆 \(1\) 和两堆 \(2\) 的情况。
当 \(k=3\) 时，分析不同大小的影响：
- 3：若 Ana 拿，必须一次拿完三个。若 Bob 拿，Bob 拿完一个 Ana 必须拿完剩下两个，先后手不变。Bob 会考虑优先拿完 \(3\)，因此 \(3\) 对于结果没有影响。
- 4：Ana 拿完两个或者三个都会输，因此 Ana 不会主动拿，必须等 Bob 先拿到 3，然后她再拿完。
- 5：若 Ana 拿，她必须拿两个，接下来 Bob 拿一个，她拿两个；若 Bob 拿，Bob 拿到一个之后变为 4，Ana 不能主动拿。另外，两个 5 可以互相抵消影响。
- 6：Ana 可以拿到 3，这对于 Ana 有利。
- >=7：Ana 必胜，因为她总是可以利用这一对来调整接下来的局面。
于是，排除掉 \(>=7\) 的情况，分为有 \(2\) 和没有 \(2\) 两种。
有 \(2\) 时，有两堆 6 或者偶数堆 5 的时候 Ana 必胜，否则 Bob 必胜。
没有 \(2\) 时，有一堆 \(3\) 或者一堆 \(6\) 或者奇数堆 \(5\) 的时候 Ana 必胜，否则 Bob 必胜。
当 \(k=2\) 时，显然存在一堆大小为 \(3t+1\) Bob 必胜，\(t\) 是一个自然数。
存在两堆 \(3t+2\) Bob 也必胜，因为 Bob 总可以制造一堆 \(3t+1\)。
然后，如果只有 \(3t\)，那么 \(Bob\) 也必胜；否则，Ana 必胜。
XOR-Excluding Sets SEERC 2025 problem C
题目大意：若一个集合的异或和不出现在该集合内，那么称其为 Xor-Excluding Set。（空集也是）
一开始有一个空集，每次往里面加一个元素 \(a_i\)，问加完之后有多少子集是 Xor-Excluding Set。数据范围：\(1\le n,a_i\le 2\times 10^5,1\le a_i\le 2^{60}-1\)，保证 \(a_i\) 互不相同。
solution
定义 Xor-Including Set 为不是 Xor-Excluding Set 的集合。
注意到，Xor-Including Set 可以由一个异或和为零的集合（可以是空集）再加上一个元素构造得到，因此，假设 \(S\) 中异或和为零，且大小为 \(i\) 的子集数目为 \(f_i\)，那么 Xor-Including Set 作为子集的数量为
考虑枚举 \(|S|-i\) 中的元素，相当于每次从集合中临时删去一个元素，问剩下的集合有多少异或和为零的子集。
动态维护线性基，把以及加入的元素分为三类，分别是不在线性基中的元素，在线性基中但是该元素在线性基中可以被其他元素替换，在线性基中且该元素在线性基中不能被其他元素替换。
第一类元素的个数就是总数减去线性基的大小，重点在于，如何求出第二类元素的个数。
考虑枚举线性基中的元素，每个元素记录它是由线性基中那些位置的原始值异或得到，当往线性基中插入元素失败时，可以得到这个元素是如何由线性基中的原始值异或产生，于是该元素可以替换这些元素，这样就可以知道那些元素属于第二类。
我们知道每一类元素删去之后的线性基大小，设其为 \(s\)，此时异或和为零的子集数目为 \(2^{|S|-1-s}\)。
One Permutation Petrozavodsk Summer 2025. Day 4. Polar Bear Transform Contest problem J
题目大意：定义一个排列 \(p\) 的分划的代价为，分划中每一段 LIS 的长度之和。
设 \(a_k\) 表示把排列分划成 \(k\) 段的最大代价，对于 \(k=1,2,\cdots,n\)，输出 \(a_k\)。数据范围：\(1\le n\le10^5\)。
solution
注意到（大胆猜测），\(a_k\) 是凸的，即 \(2a_k\ge a_{k-1}+a_{k+1}\)。于是，可以通过 wqs 二分求出单个 \(a_k\)。
设定阈值 \(B\)，把 \([1,n]\) 分成两段，其中 \(a_i-a_{i-1}<=B\) 的为第一段，即斜率小的一段；\(a_i-a_{i-1}>B\) 的为第二段，即斜率大的一段。
注意到斜率小的段可以枚举斜率，然后找到该斜率段的左右端点；斜率大的段不会太长，可以枚举 \(k\) 然后暴力做。（具体维护可以自行考虑）
Language Barrier SEERC 2025 problem F
题目大意：大小为 \(n\) 的树，每个点上面有一个人，第 \(i\) 个点上的人会的语言（语言用整数表示）是一个区间 \([l_i,r_i]\)。
现在有一个纸条要从第一个人传到第 \(n\) 个人，每一轮可以进行以下操作之一：
- 把纸条传递给相邻的节点。
- 如果持有纸条的人认识纸条上的语言，那么他可以把纸条翻译成任何他会的语言。
初始纸条的语言可以为第一个人会的任何语言，问至少要多少轮才能使得纸条传递到第 \(n\) 个人手中，并且他会纸条上的语言。数据范围：\(2\le n\le2\times10^5,1\le l_i\le r_i\le10^9\)。
solution
设 \(\text{dis}(u,v)\) 表示树上 \(u\) 和 \(v\) 直接的距离。
考虑一种朴素的思路，构建一张新图，如果 \(u\) 和 \(v\) 会的语言有交，那么在新图中将 \(u\) 和 \(v\) 之间连一条权值为 \(dis(u,v)+1\) 的边，最后答案就是 \(1\) 到 \(n\) 的最短路减 \(1\)。
考虑优化建图，点分治，对于一个大小为 \(S\) 的连通块，先把所有点的 \(l_i\) 和 \(r_i\) 放在一起离散化，设离散化后的值域大小为 \(T\)，另开 \(T\) 个点，第 \(i\) 个点连向第 \(i-1\) 个点，权值为 \(0\)。
设 \(d_u\) 表示重心到 \(u\) 的距离，于是 \(u\) 向第 \(r_u\) 个点连边，权值为 \(d_u\)；第 \(l_u\) 个点向 \(u\) 连边，权值为 \(d_u+1\)。
这样建出来的图边数为 \(O(n\log n)\)。
Hashing CCPC 2025 Jinan Site problem H
题目大意：定义 \(\text{sz}_u\) 表示 \(u\) 的字数大小，\(\text{son}_u\) 表示 \(u\) 的儿子集合。
对于一颗以 \(r\) 为根的有根树，定义其哈希值为\[h(r)=1+\sum_{v\in\text{son}_r}h(v)\times f(sz_v) \]其中 \(f\) 代表任意一个从正整数到正整数的映射。对于两棵有根树，如果对于任意 \(f\)，其哈希值都相等，那么认为这两棵有根树是不可区分的。问有多少个大小为 \(n\) 的有根二叉树，它们之间是两两可区分的。
答案模 \(p\) 后输出。数据范围：\(1\le n\le 3000\)。
solution
注意，本题中的不可分不意味着同构，如下图，\(S_1\) 和 \(S_2\) 代表两个大小相同但是结构不同的二叉树。
不难发现，某个点加的 \(1\) 对于总哈希值的贡献只在与它和它的祖先的子树大小，于是可以设 \(f_{i,j}\) 表示有 \(j\) 个大小为 \(i\) 树，可以形成的两两可分的结构数量，最后的答案就是 \(f_{n,1}\)。
考虑这 \(j\) 棵树是如何分裂的，假设分裂成了两颗子树，大小分别为 \(s_1,s_2\)，且 \(0\le s_1\le s_2,s_1+s_2=i-1\)，于是
状态数只有 \(O(n\log n)\)，单次转移为 \(O(n)\)。
Cipher CCPC 2025 Jinan Site problem A
题目大意：\(n\) 次询问，每次给定两个整数 \(a,b\)，找出最小的非负整数满足 \(a^x\equiv b\mod 2^{64}\)，或者指出 \(x\) 不存在。
数据范围：\(1\le n\le 10^5,0\le a,b<2^{64}\)
solution
当 \(a\) 是偶数时，由于 \(2^{64}\mod 2^{64}=0\)，所以只要检查 \(x=0,1,2,\cdots,63\) 即可。
当 \(a\) 时奇数时，考虑倍增地求出答案。
假设已经找出了最小的 \(x_i\) 使得 \(a^{x_i}\equiv b\mod 2^i\)，考虑求出 \(x_{i+1}\)。
设 \(2^i\) 的阶为 \(2^{t_i}\)，于是可以得到 \(t_{i+1}\le t_i+1\)，注意到 \(a^{x_{i+1}}\equiv b\mod 2^{i+1}\) 至少要满足 \(a^{x_{i+1}}\equiv b\mod 2^i\)。
由于 \(x_i<2^{t_i},x_{i+1}<2^{t_{i+1}}<2\times 2^{t_i}\)，于是 \(x_{i+1}\) 只有 \(x_i\) 和 \(x_i+2^{t_i}\) 两种取值，取其中满足条件的一个即可。
Increasing Swaps The 4th Universal Cup. Stage 13: Grand Prix of Ōokayama problem B
题目大意：给定一个长度为 \(n\) 的排列 \(P\)。对于一个长度为 \(n-1\) 的序列 \(T=(T_1,T_2,\cdots,T_{n-1})\)，定义 \(f(T)\) 如下
1.\(t\leftarrow 0\)
2.while \(P\) is not sorted in ascending order:
\(\quad\quad\) \(t\leftarrow t+1\)
\(\quad\quad\) let \(S = (S_1,S_2,\cdots,S_k)\) be the indices \(i\in\{1,2,\cdots,n-1\}\) where \(T_i\le t\), sorted increasingly
\(\quad\quad\) for \(j = 1\) to \(k\):
\(\quad\quad\quad\quad\) \(i \leftarrow S_j\)
\(\quad\quad\quad\quad\) swap \(P_i\) and \(P_{i+1}\)
\(\quad\quad\) if \(t\ge 10^{100}\):
\(\quad\quad\quad\quad\) return \(10^{100}\)
3.return \(t\)
你可以任意选择 \(T\)，输出最小的 \(f(T)\)。
solution
以上伪代码的过程是，每个时刻激活若干个位置，然后连续的激活位置形成一个区间，每个区间内循环置换。
可以把整个过程倒过来考虑，由 \((1,2,\cdots,n)\) 推到 \(P\)。于是上面区间的合并就变成了区间的分裂，什么时候把区间分裂呢？
首先，每次分裂一个区间肯定是分裂成两个，因为分裂成多个可以看作多次分裂，于是一个区间会分裂成一个前缀和一个后缀。
其次，分裂出来的区间要能通过重新排列得到 \(P\) 的对应区间。
最后，分裂区间一定是越早越好，因此一定会把当前区间循环置换最少的次数，使得该区间可以分裂。
我们由此可以得出做法，分治，每一个区间 \([l,r]\) 找到最早的循环置换次数 \(t\)，以及分裂的位置 \(p\)，设该区间的答案为 \(g(l,r)\)，可以得出 \(g(l,r)=t+\max(g(l,p),g(p+1,r))\)。
如果 \([l,r]\) 完全匹配 \(P\)，那么 \(g(l,r)=0\)。
浙公网安备 33010602011771号