IOI2025 集训队互测记录

yyyyxh / 2024-10-19 / 原文

Round 1

87.5+0+25，垫底了，我怎么能这么唐的。

飞带长队怎么这么牛，三个题都好厉害！点赞了。

开场开 T1，做了一会之后发现会了 40 分的判定。于是逮住这个判定研究了大半天，手动模拟之后猜到了划分出来的每个串的数量的条件大概是 $\ge \max b_i-a_i$ 这种形式的，发现可以很容易 $O(n^5)$ DP 这个东西。然后这个题采取了一种奇妙的回答方式，你只需要在一个测试点的不同的测试组中选一个作答就行了，但是我以为你需要回答一个前缀，于是我的算法就变成 $O(n^5 T)$ 的了，只拿了 87.5 分。考完问 zhy 他是怎么切的，他告诉他也是五方，原来我已经想到正解了，气急败坏……气急败坏……

中途去看 T2，写了几个判定都假了，没有想到直接取序列的前若干项暴力就可以拿很多分了。T2 做了许久还是 0 分，发现时间只剩下半个小时了，最后疯狂 rush 完了 T3 的 25 分暴力。

这场比赛寄就寄在一直在纠结是继续做 T2 的判定还是去想 T1 那根本不存在的更低复杂度做法，从而整场考试都有点心神不宁，没有冷静下来复盘。如果能仔细冷静的观察局势，无论是 T1 理解错出题人的意思还是 T2 部分分一分没拿都是可以避免的。

《基础 ABC 练习题》 from 方心童

AGC055D 加强，查了一下自己水表发现自己某天心血来潮做了 AGC055 两个题就是没做这个题。

考虑一下判定一对 $(x,y)$ 是否合法，记录你目前拥有的 ABC，BCA，ACB，AB，BC，CA，A，B，C 个数，初始 ABC $x$ 个，BCA $y$ 个，CAB $n-x-y$ 个，你发现假设现在你想填入一个 A，那么从 ABC，AB，A 中选一个去掉开头的字母，这样永远只可能会增加以 B 开头的串，于是不难证明先取长的更优，写一写这个判定发现可以拿 40 分。

更仔细地考虑这个过程。在这个过程中，为了保证碰到对应的字母时串的数量是够的，也就是你之前遇到的 C 的数量加上 $x$ 不少于 A 的数量。这个过程中遇到的这些 C 可以认为他们都解放了一个 A，如果没有，说明这些 C 是从 ABC 转化成 BC 再转化成 C 的，那么在此之前，一定有个 BC 转化成了 C，也就是说所有的 BCA 已经消耗完了，那么所有的 CA 已经完全转化出来了，因此你需要优先消耗 CA 中的 C。综上所述你可以认为消耗单独一个 C 的时刻一定是一段后缀，那么在转化单独的 C 之前，所有的以 A 开头的字符串都已经被转化出来了，不需要继续考虑判定条件了。同理，对于 B 的数量和 C 的数量也是差不多的要求，可以发现这三个条件合起来是充要的。

接下来 DP 就很简单了，记 $a_i,b_i,c_i$ 表示前 $i$ 个字符中 A、B、C 的个数，考虑记录 $\max(a_i-c_i),\max(b_i-a_i),\max(c_i-b_i)$ 是复杂度高的，我们考虑计算 $a_i-c_i\le X,b_i-a_i\le Y,c_i-b_i\le Z$ 方案数是容易的，简单差反演一下就得到了最大值的方案数了，$O(n^5)$。

Code。

《基础 01? 练习题》 from 郑钧

首先题目中给出的序列就是 Thue-Morse 序列，也就是常见的 $\operatorname{popcount}(i) \bmod 2$ 构成的分形序列。在连续子序列这道题中，zj 给出了一个刻画 TM 序列所有可能的子串结构的方式。

具体地，如果一个串是 TM 序列的前缀或者是其取补的前缀，那么称这个串是好的，一个串的 TM 拆分即将一个串拆分成两个非空串 $A,B$，使得 $A$ 的翻转 $\operatorname{rev}(A)$ 以及 $B$ 串都是好的。

我们断言，所有 TM 序列的子串只有三种情况，且满足这三种情况之一的一定是 TM 序列的子串：

单个字符构成的串 $0/1$。
具有唯一的 TM 拆分点。
具有两个 TM 拆分点，满足将串拆分成了三个子串 $A,B,C$，使得 $|A|,|C|\le |B|$，$B$ 的长度是二的次幂，$\operatorname{rev}(A+B)$ 和 $B+C$ 都是好串。

可以看到 TM 拆分的本质是用 $\operatorname{popcount}$ 奇偶性来刻画 TM 序列时，找到 $\operatorname{lowbit}$ 最大的那个点拆分序列。上面的性质详细的证明可以看 zj 题解。

如何寻找 TM 拆分呢？发现你只需要求出每个位置最多向左/向右多少位依然是好串。这似乎是带通配符的 LCP 问题，怎么做？

不要被字符串思维束缚了！考虑 TM 序列的性质，其匹配结构是可以倍增求出的。预处理每一个长度为 $2^k$ 的串是否与 TM 序列或其取反后的前缀相同。

于是先枚举 TM 拆分点往左右扩展，然后容斥掉拥有两个拆分点的情况，这个可以枚举中间 $B$ 串长度往两边扩展。

接下来计数还是比较 trivial 的。经典的套路，考虑求所有的子串的答案和，相当于若干次区间加之后求历史和，线段树维护即可。

Code。

《基础 01 练习题》 from 刘海峰

很有想法的题！可以看作对于二分竞赛图性质深入研究的例题。

题意大概是说每一行 $A$ 矩阵中等于 $0$ 的集合包含了 $B$ 矩阵中等于 $0$ 的集合，或是 $A$ 矩阵中等于 $1$ 的集合包含了 $B$ 矩阵中等于 $1$ 的集合。列的话 $B$ 矩阵中的 01 得反过来。

我们不妨转化一下题意，由于我们每次是将一些位置变成 $1$，考虑一个位置变成 $1$ 之后还会有哪些新的要求，如果 $A$ 矩阵中为 $1$ 的位置在 $B$ 矩阵中变成了 $1$，那么 $A$ 矩阵同一列的 $0$ 在 $B$ 矩阵中一定也要同时变成 $1$ 才行；如果是 $A$ 矩阵中为 $0$ 的位置在 $B$ 矩阵中变成了 $1$，那么就对 $A$ 矩阵同一行中的 $1$ 作出同样的要求。

这样就转化成了一个图论问题。优化建图之后，相当于每个 $1$ 连出到列点，被行点连入，每个 $0$ 连出到行点，被列点连入。题目就是让我们求有多少个包含非行列点的 SCC，暴力 tarjan 获得 25 分。

考虑到每个非行列点只有一个入度一个出度，可以直接看成一条边，那么原图就变成了左右各 $n$ 个点，中间 $n^2$ 条不重也不相对的有向边的二分竞赛图。

对于普通竞赛图，SCC 问题是老生常谈的，我们知道竞赛图 SCC 缩点之后的形态是一条链，而且根据兰道定理，我们将出度排序可以构建出一条哈密顿链，每一个强连通分量是一段区间，通过判断一段长为 $i$ 前缀的度数和是否是 ${i\choose 2}$ 可以判断其是否是 SCC 的右边界。

对于二分竞赛图，是否有同样优美的性质呢？首先考虑缩点之后，很明显缩出来的很有可能不是一条链，但是这种情况之发生在有两个同侧且出邻域一模一样的点时才有可能出现。如果我们不断删去出邻域相同的其中的一个点，将删去的那个视为没删去的点的附属点，它们在图中一定保持相同的可达性地位，然后 SCC 缩点，可以保证缩出来一条链。

证明 copy from sol：

考虑删点求拓扑序的过程中，如果存在某一时刻有两个强连通分量入度为 $0$，首先这两个强连通分量一定是同侧单点。如果不是单点，就存在至少两种颜色，那么这两个强连通分量之间就有连边了，此时这两个点都连向了没被删的异侧,所以这两个点完全相等，于是矛盾。

接下来我们考虑同样地通过度数序列刻画可达性性质。对于度数相同的所有点，它们之间有可能是之前去重时删去的点，恰有一个留在原图中的点单独构成 SCC，这样它们之间一定互相不可达；也有可能一部分留在了原图中，这样所有度数相同的点一定在同一个 SCC 中，一定互相可达。因此，我们给度数相同的点添加一条有向链一定不影响 SCC 的形态。

对于度数不同的点，由于删点后 SCC 成一条链的状态，所以度数大的点一定能到度数小的点。

考虑如何解决本题。对于两行，从左往右扫描列，找到它们第一个不同的位置，此时该位置为 $1$ 的行（设为 $x$）出度大于该位置为 $0$ 的行（设为 $y$），那么有可达性 $x\to y$。由于往右扫描列的过程不会破坏原有可达性（这个观察非常关键！），所以你把所有行按照字典序排序之后，所有包含行点的 SCC 在之上构成若干个区间！主席树维护哈希直接排序就可以得到一个 $O(n\log^2 n)$ 的做法，常数不大。

接下来的事情比较好处理了，考虑得到字典序顺序之后，每一次加入一个列点，观察其对可达性的影响。求出能直接到达其在序列中最靠前的行点，以及其能直接到达在序列中最靠后的行点，如果这个东西构成了区间，那么中间所有点一定在同一个 SCC 里，用并查集并起来；否则利用可并堆维护一下这个列点处于哪两个 SCC 之间，如果这两个 SCC 并起来了，这个列点也要加入这个新的 SCC。

注意算答案是把边看成点算包含边的 SCC 个数，所以设一个 SCC 中有 $x$ 个行点 $y$ 个列点，对答案的贡献是 $\min(1-xy,0)$。

Code。