The 2024 ICPC Asia Pacific Championship

补题链接, 题面, 官方题解

题挺好的，猜结论还是要大胆一点，坚持训练！

ID	Difficulty (0-5)	Topic	Status	Code
A
B
C	2	Greedy, Implementation	Solved	C.cpp
D
E	2	Constructive Algorithms	Solved	E.cpp
F	3	Monotonic Queue	Upsolved	F.cpp
G	3	Pigeonhole Principle, Bitset	Solved	G.cpp
H	1	Greedy	Solved	H.cpp
I
J	2	Shortest Path	Solved	J.cpp
K	4	DSU on Tree, Segment Tree	Upsolved	K.cpp
L
M

C. Bit Counting Sequence

注意到每次进位都能确定数列中的一段，模拟即可。

E. Duplicates

假设不合法的行数是 $x$ ，不合法的列数是 $y$ ，那么答案至少是 $\max(x,y)$ ，存在构造达到这个下界。

矩阵内数字都在 $[1,n]$ 内，所以不合法的行列一定是 $n$ 的排列。

每次选一个不合法的行，一个不合法的列，在交点位置改成这一行列其他位置有的某个数就行了。

对于剩下的不合法的找一个合法的配对，分类讨论证明一定有解，然后暴力枚举交点换成谁即可。

复杂度 $O(n^3)$ 。

F. Forming Groups

给定数列 $b_1,b_2,b_3,\dots,b_{n-1}$ ，选一个位置把 $x$ 插进去（有 $n$ 种不同的位置），形成一个新数列 $a$ 。

然后选一个 $n$ 的因数 $k$ ，把 $a$ 分成 $k$ 组，$a_i$ 被分到第 $i\mod k + 1$ 组，记录第 $i$ 组的 $a$ 之和为 $w_i$ 。

找一个放 $x$ 和选 $k$ 的方案，最小化 $\displaystyle \frac{\max w_i}{\min w_i}$ 。

枚举 $k$ ，每个 $b_i$ 只有可能被分到第 $i\mod k + 1$ 组和第 $(i+1)\mod k + 1$ 组。

枚举 $x$ 的位置，每次只会有两个组的 $w$ 受到影响，线段树维护单点修改查询全局 $\min,\max$ 。

注意到随着枚举 $x$ 的位置，每次受影响的组的编号是连续的，可以把线段树换成单调队列。

再注意到 $k$ 其实只需要枚举 $n$ 的质因子，这样只需要试最多 $7$ 个不同的数了。证明如下：

如果把 $n$ 分成了某个合数 $k=pq$ 组，证明分成 $p$ 组不会变差：

相当于原来的 $pq$ 组每 $q$ 组合在一起，新的最小值 $\ge$ 原来最小值 $q$ 倍，新的最大值 $\le $ 旧的最大值 $q$ 倍。

因此比值乘了一个不大于 $1$ 的值，不会变差。

复杂度 $O(7\times n)$ 。

G. Personality Test

给 $n$ 个长度都是 $m$ 的字符串，找两个字符串 $i,j$ ，使得两个字符串至少有 $k$ 个位置对应字符相等。

有多个解的时候先最小化 $j$ ，再最大化 $i$ 。数据范围：$n\le 5000,m\le 3000,k\le 5$

官方做法是鸽巢原理。考虑每个字符串对有多少个位置一样，最开始都设置成 $0$ 。

每次找到一个位置一对字符串相等，就把他们的答案 $+1$ 。

我们最多加 $(k-1)\times{n\choose 2} + 1$ 次，就一定会有一对的答案 $\ge k$ 。

枚举 $j$ ，然后枚举每个位置，把这个位置上字符相同的那些 $i$ 贡献 $+1$ 。

总复杂度 $O(kn^2+nm)$ 。

---

有个暴力的做法可以求出所有符合要求的字符串对。

每次枚举一个当前的字符串 $j$，设 $S_{pos,t}$ 表示只看前 $pos$ 位，有至少 $t$ 个位置和当前串一致的字符串下标集。

每次转移形如 $S_{pos+1,t}=S_{pos,t}\cup (S_{pos,t-1}\cap T_{pos+1,str[j][pos]})$ ，其中 $T$ 表示这个位置和当前字符一致的字符串下标集。最终答案就是 $S_{m,k}$ 。

使用 bitset 加速这一过程，复杂度 $O(n^2mk/\omega)$ 。

H. Pho Restaurant

贪心，每桌都移走较少的那种就行。所有桌移走的颜色一致时特殊讨论下。

J. There and Back Again

首先证明一条肯定是最短路：

否则两条都不是最短路且两条边集不同，那么把其中一条换成最短路依旧满足边集不同。

因此先找出最短路，然后建立分层图，让第二条路经强制走一条不在最短路中的边就行了。

K. Tree Quiz

首先注意到这是个 $n$ 进制的三位数。因此 $x$ 可以直接从下标算出，$x=\lceil\frac{k}{n}\rceil$。

接下来求 $lca$ 转化成当前点到根的链上，每个点有一个权值（自己的子树大小减去对应儿子的子树大小），然后按照编号大小排序，找前缀和为某个值的位置，DFS 的同时线段树维护链上的点及其 size 信息，然后线段树上二分即可，复杂度 $O(n\log n)$。

接下来求 $y$ 就转化成了，询问 $lca$ 子树中，除了 $x$ 所在的这个子树以外的所有点中编号第 $k$ 大的是谁，可以 DSU on Tree + 线段树维护，每次询问线段树上二分。复杂度 $O(n\log^2 n)$ 。

总复杂度 $O(n\log^2 n)$ 。

---

对于最后一步，如果改成使用主席树在 DFS 序上维护节点编号集，每次从子树中扣掉一个儿子的子树，就变成了 DFS 序上的两段，四个节点并行在主席树上跑即可。

这样总复杂度降低到 $O(n\log n)$ ，并且不用讨论轻重儿子，实现起来简单很多。