（补档）IOI2020国家集训队作业 Part 1

· · 算法·理论

来自 2022.8.9，不知道为啥当时没公开，今天突然翻到，现在放出来希望能对后人有用。

IOI2020国家集训队作业 Part 1

我会给每个题一个 1\sim16 的主观难度评分。

如果一个题的定数是 114514，那么说明这题是计算几何或者多项式，我跑路了。

1.CF504E Misha and LCP on Tree(5)

就这也 *3000？

序列上大家都会二分哈希，那么直接树剖一下就到树上了。具体实现时把路径拆成 \log 个区间，每次最靠前的两个区间长度取 \min 算哈希，如果一样就消掉这个区间，否则在这个区间二分。

时间复杂度 O(n\log n)，找了个不太常用的 NTT 模数没有被卡，就不需要双模了。

2.CF505E Mr. Kitayuta vs. Bamboos(8)

一眼丁真鉴定为二分答案，然后发现正着做取 \max 很困难，考虑到过来。

现在问题变成了每轮每根竹子会变短 a_i，你每次可以选 k 根长高 p，中间过程中不能有竹子的高度是负数，最终所有竹子高度要大于等于 h_i。

直接堆维护最终时刻高度不到 h_i 的竹子高度变成负数的时刻，每轮贪心选最快变成负数的拔高即可，最后如果堆空了就合法。

时间复杂度 O((n+mk)\log n\log(m\max a))。

3.CF506E Mr. Kitayuta's Gift(15)

我的评价是 *3000 之间亦有差距，太困难了这题。

首先考虑一个匹配方法使得每个串只会被算一次。由于是回文串自然想到从两边往中间匹配。

先假设 n+|S| 是偶数。

记 dp_{i,l,r} 表示前后已经各确定了 i 位，左边匹配了 1\sim l-1，右边匹配了 r+1 \sim n 的方案数，另外记 f_i 表示左右考虑了 i 位已经匹配的方案数。

转移是 trivial 的：

直接做是 O(n|S|^2) 的，过不了。

发现这是个线性变换，暴力矩乘可以做到 O(|S|^6\log(|S|+n))，还是过不了。

考虑优化，我们的 dp 可以看成在一个自动机上走的过程，具体来说我们把 (l,r) 相同的状态看成等价类，转移改成连系数条边，那么大概会是下图这样的东西（图是嫖来的）：

注意到如果我们走了 i 个有 24 个自环的点，那么我们会走 \lceil\frac{|S|-i}2\rceil 个有 25 个自环的点，这些路径的贡献是相同的，也就是说本质不同的路径只有 O(|S|) 种，我们可以对每一种 dp 出游多少条不同的路径然后矩乘，这样是 O(|S|^4\log(|S|+n)) 的，还是过不去。

继续优化，尝试压缩自动机，我们先拉一条链上有 |S| 个 24 个自环的点，下面拉一条链上有 \lceil\frac{|S|}2\rceil 个 25 个自环的点，上面的链第 i 个点连到下面第 \lceil\frac{|S|}2\rceil-\lceil\frac{|S|-i}2\rceil 个点，边权就是第 i 类路径的数量。

再拉个图方便理解：

这样就只需要一次矩乘就可以求出所有答案了，时间复杂度 O(|S|^3\log(|S|+n))。

然后考虑 n+|S| 是奇数的情况，发现这种时候最后一步是不能走终点的 26 个自环的，直接把不合法的算出来减掉即可（只保留最后一步 i\rightarrow i+1 的边即可）。

最后这题有点卡常，但是发现矩阵是上三角矩阵，所以可以只枚举 i\leq k\leq j 的转移，常数可以除以 6。

4.CF512D Fox And Travelling(7)

选点看成删点，那么你发现这个判定条件就是无向图拓扑的时候的判定。

所以环上的点删不掉，剩下的是若干棵树。

树上必须先删儿子后删父亲，鉴定为树形背包。

众所周知树形背包是 O(n^2) 的，所以你爆标了？

并没有。考虑如果整个连通块是树的情况，这种是无根树，所以你要对每个点都做一遍背包。

最后再来一个背包合并森林，时间复杂度 O(n^3)。

5.CF516D Drazil and Morning Exercise(7)

注意到个形式有点像树的重心，因此我们以 $f_i$ 最小的点作为根儿子的权值是不小于父亲的权值的，证明可以考虑每个点最多只会有一条出边使答案变小。 那么枚举根也就是最小值，变成了统计子树内权值在一个范围内的点的个数，可以启发式合并，复杂度 $O(qn\log^2 n)$ 会在很靠后的点 TLE。 更好的做法是反过来枚举最大值。考虑如果给权值排个序，那么父亲一定在儿子后面。枚举联通块的最大值，那么合法的点是一个区间可以双指针，右端点扩展的时候把他的所有儿子合并起来，最后查询左端点的联通块大小。左端点右移的时候可以直接删掉，因为左端点一定是叶子。 时间复杂度 $O(qn\log n)$。 ## 6.CF516E Drazil and His Happy Friends(14) 一个显然的结论是只有模 $d=\gcd(n,m)$ 同余的男女才有可能一起玩，所以可以分开计算。 如果 $d>b+g$ 那么肯定存在空的组，直接无解。 分类之后可以默认 $\gcd(n,m)=1$。考虑计算每组最后一个变快乐的男/女的时间取 $\max$ 得到答案。考虑如果第 $i$ 天第 $i\ \mathrm{mod}\ n$ 个男孩是快乐的，那么第 $i\ \mathrm{mod}\ m$ 个女孩就会快乐，同理再过 $n$ 天第 $(i+n)\ \mathrm{mod}\ m$ 个女生也会变快乐，这可以等价为如果第 $i$ 个女生快乐，那么 $n$ 天后第 $(i+n)\ \mathrm{mod}\ m$ 个女生也会快乐。这启示我们考虑同余最短路。 - 第 $i$ 个女生向第 $(i+n)\ \mathrm{mod}\ m$ 个女生连长度是 $n$ 的边； - 如果第 $i$ 个女生自己是快乐的，从 $s$ 向 $i$ 连长度是 $i$ 的边表示从第 $i$ 天之后他可以传递快乐； - 如果第 $i$ 个男生是快乐的，那么他向每一个女生连边，边权可以 exgcd 算出来。 点数还是 $10^9$ 的，很没救。 但是注意到第一类边把所有女生连成了一个环，我们可以不显式建图直接计算贡献，具体来说给环排序之后，最大值只会在一个初始快乐的人的前一个取到，直接计算就好了。 时间复杂度 $O((b+g)\log(b+g))$。 ## 7.CF521D Shop(9) 如果只有乘法是非常脑瘫的，但是还有赋值和加法，考虑把这两种操作转化成乘法。 显然的结论是我们肯定是先赋值然后加最后乘，每个数只会赋值一次，每个数加法取到的一定是从大到小排序后的一段前缀。 那么先把赋值转化成加法操作，然后对加法求前缀和，把增量转化成乘法，最后所有操作贪心取最大的 $m$ 个就做完了。 时间复杂度 $O(n\log n)$。 ## 8.CF521E Cycling City(6) *3100? *1300! 三条简单路径等价于两个有交的环。先搞一棵 dfs 树，那么变成了存在两条非树边覆盖的部分有交。 那么问题就简单了。直接差分一下，找到一条边覆盖了超过两次就有解。记两条非树边分别是 $(a,b),(c,d)$，不妨设 $dep_a<dep_b,dep_c<dep_d,dep_a<dep_b$，那么三条路径就是 $\mathrm{lca}(b,d)\rightarrow b\rightarrow a\rightarrow c,\mathrm{lca}(b,d)\rightarrow d\rightarrow c,\mathrm{lca}(b,d)\rightarrow c$。 时间复杂度 $O(n)$。 ## 9.CF526F Pudding Monsters(7) 题意转化成给一个排列，求有多少个区间满足 $\max-\min=r-l+1$。 扫描右端点，单调栈维护每一段 $\max$ 和 $\min$，用线段树维护 $\max-\min-r+l-1$，这样只需要简单的区间加。查询时问的就是区间 $0$ 的数量，因为是排列，所以线段树上的值不可能是负数，可以直接维护最小值的数量。 二维坐标就把值变成一个 pair 就好了。复杂度 $O(n\log n)$。 ## 10.CF526G Spiders Evil Plan(14) 显然路径的端点不是叶子是不优的，于是每次路径可以覆盖两个儿子。 问题变成了选 $2y$ 个儿子到 $x$ 的路径组成的连通块最大权值，如果 $x$ 不是叶子直接贪心取最大的 $2y$ 个，否则取 $2y-1$ 个，可以线段树维护。 但是这样每次询问都要跑一遍，无法接受。 注意到树的直径有一个性质是任意一个点距离最远的点一定是直径的一个端点，所以只要我们选了点就一定会至少选一个端点，所以我们只要把直径端点作为根分别跑一遍上面的做法选 $2y-1$ 个点取 $\max$ 即可。 但是这样选出来的路径并可能是不经过 $x$ 的，这个时候我们需要调整。 调整有两种情况，第一种是去掉最后一次选的叶子，然后把 $x$ 子树内最深的那一条选上，这个可以直接倍增找出来没有被选的路径长度。 另一种情况是直接向上找到第一个被覆盖的点，把子树内最小的路径换成 $x$ 子树内最大的那条。但事实上如果这个点的子树内有超过一条路径那么这种情况要么不优要么已经在上一种里面算过了（因为子树内的两条路径本身就有交），所以还是只需要维护子树内最深的链即可。 复杂度 $O((n+q)\log n)$。 ## 11.CF527E Data Center Drama(3) 不懂就问，这题怎么出现在集训队作业里的？ 首先大胆猜测不考虑自环的情况下只要每个点度数是偶数就一定有解，直接补齐之后考虑构造。 注意到这个度数限制和欧拉回路比较像，欧拉回路是入度等于出度，这个是入度出度都是偶数。 如果有一个方法转化就好了。注意到欧拉回路中一定是先走到一个点再走出去，这样是一条入边一条出边。如果我们把其中一条反向，那么就是两条入边或者出边，这刚好是个偶数。 所以我们跑一遍欧拉回路，把所有在第偶数步走的边反向即可。 最后是自环，一个点有奇数个自环需要补上一个。 时间复杂度 $O(n)$。 ## 12.CF536D Tavas in Kansas(12) 博弈论啥都不会。 首先求出来每个点到 $s,t$ 的最短路，然后每个点可以映射到坐标系上的 $(dis_{s,i},dis_{t,i})$ 位置，问题转化为两人轮流操作，先手可以竖着取走一个前缀矩形，后手可以横着取走一个前缀矩形。 考虑 $dp_{0/1,i,j}$ 表示当前先手还是后手操作，剩下的矩形是 $(i,j)$ 到右上角的部分时先手最多比后手多的权值，转移直接枚举每一行和列，因为既可以换对方取也可以不换，所以直接转移即可。 时间复杂度 $O(n^2)$。 ## 13.CF538G Berserk Robot(13) 首先把坐标系转 $45°$，两维就独立了。 然后这样是 $\{1,-1\}$ 看起来还不够好，我们给每个坐标加上 $t$ 再除以二，这样上下左右分别对应 $(1,0),(0,1),(0,0),(1,1)$。 首先这样操作出来的坐标如果不是整数就无解了，接下来考虑坐标是整数的情况。 记 $s_i=\sum\limits_{j=1}^ia_j,p_i=\lfloor\frac{t_i}l\rfloor,q_i=t_i-lp_i$，那么每个限制形如 $p_is_n+s_{q_i}=x_i$ 的形式。 将限制按照 $q_i$ 排序，相邻两式相减可得 $(p_{i+1}-p_i)s_n+s_{q_{i+1}}-s_{q_i}=x_{i+1}-x_i$。 显然 $s_{q_{i+1}}-s_{q_i}$ 取值在 $[0,q_{i+1}-q_i]$ 之间，所以 $(p_{i+1}-p_i)s_n$ 的取值范围是 $[x_{i+1}-x_i-q_{i+1}+q_i,x_{i+1}-x_i]$。 扫一遍，动态维护合法区间 $[l,r]$，更新时分类讨论 $p_{i+1}-p_i$ 的取值： - $p_{i+1}-p_i=0$：判一下这个区间是否跨过零点，如果没有那么无解，否则恒成立。 - $p_{i+1}-p_i>0$：$[l,r]$ 和 $[\lceil\frac{x_{i+1}-x_i-q_{i+1}+q_i}{p_{i+1}-p_i}\rceil,\lfloor\frac{x_{i+1}-x_i}{p_{i+1}-p_i}\rfloor]$ 求交。 - $p_{i+1}-p_i<0$：$[l,r]$ 和 $[\lceil\frac{x_{i+1}-x_i}{p_{i+1}-p_i}\rceil,\lfloor\frac{x_{i+1}-x_i-q_{i+1}+q_i}{p_{i+1}-p_i}\rfloor]$ 求交。 这样求出来最后的区间如果是空集就无解，否则不妨令 $s_n=l$，那么可以推出每组 $s_{q_{i+1}}-s_{q_i}$ 的取值。 然后直接在区间内选出等量的点赋值为 $1$ 即可，两维都这样跑一遍，时间复杂度 $O(n\log n)$。 ## 14.CF538H Summer Dichotomy(12) 首先老师得是个二分图。 先不考虑 $t$ 和 $T$ 的限制。然后如果有三个老师的区间两两不交直接无解，如果所有老师两两有交那么可以随便分组，否则考虑若 $a=\min r,b=\max l$，显然 $a$ 不能变大，$b$ 不能变小，而 $a$ 变小 $b$ 变大不会使答案更优。 那么不妨初始使用 $a,b$ 作为两组数量，如果 $a+b\notin[t,T]$，那么因为 $a,b$ 都只能单向调整，所以直接调整可以调的那个即可。接下来考虑如果一个老师的区间一个端点都不包含就寄了，都包含可以随便选，否则只能选一边，这样先确定一些老师的分组，然后对剩下的老师跑二分图染色。 时间复杂度 $O(n+m)$。 ## 15.CF547D Mike and Fish(3) 每个点看成行列之间连一条边，对于行入边红出边蓝，列反过来，这样要求每个点入度和出度差小于等于 $1$。 那么直接所有奇度点向一个虚点连边，跑欧拉回路就做完了。 时间复杂度 $O(n)$。 ## 16.CF547E Mike and Friends(7) 先建出来 AC 自动机，然后把询问离线差分一下，那么问题就变成了每次插入一个字符串，路径上单点加 $1$，然后询问某一个节点 fail 树子树内的和，直接 bit 就做完了。 时间复杂度 $O(n|\Sigma|+(q+n)\log n)$。 ## 17.CF549E Sasha Circle(114514) 计算几何，润。 ## 18.CF553E Kyoya and Train(114514) 多项式，润。 ## 19.CF555E Case of Computer Network(4) 点双一定可以使得点双内的点两两可达，先缩起来，剩下的是一个森林。 由于是无向图，点双之间至多一条边连接，所以相当于限制经过这条边的只能有一个方向。 对于每个可达限制直接在树上分两段差分一下就好了。注意图中有重边而且不一定连通。 时间复杂度 $O(n+(m+q)\log n)$。 ## 20.CF559E Gerald and Path(11) 先给线段按照端点位置排序，然后 dp，记 $dp_{i,j,0/1}$ 表示考虑了前 $i$ 条线段，右端点由第 $j$ 条线段达到，第 $j$ 条线段向左/右延伸的最大覆盖长度。 向右转移是简单的，但是发现没法计算向左的转移。考虑如果我们向左，会有一段后缀的线段被包含，他们可以视为没有贡献，那么直接在 $i$ 位置枚举后继 $k$，钦定 $(i,k)$ 中的线段没有贡献然后转移即可。 最后中间包含的线段还有可能有一段的右端点超出了 $k$，这种情况直接强制 $(i,k)$ 每条线段都向右算出来右端点即可，答案显然是不劣的。 时间复杂度 $O(n^3)$。 ## 21.CF566C Logistical Questions(13) 首先考虑一条边的情况，不难发现有函数 $f(x)=w_1x^{\frac32}+w_2(d-x)^{\frac32}$，求个导 $f'(x)=\frac32(w_1\sqrt x-w_2\sqrt{d-x})$。$f(0)=-\frac32w_2\sqrt d<0,f(d)=\frac32w_1\sqrt d>0$，且 $f''(x)=\frac34(\frac{w_1}{\sqrt x}+\frac{w_2}{\sqrt{d-x}})>0$，所以 $f'(x)$ 单调递增且有零点，所以 $f(x)$ 是下凸的。 拓展到树上，发现是同理的。考虑任意一条链都可以列出和上面 $f(x)$ 几乎一致的函数，因此树上每条链都是下凸的，所以整棵树是下凸的，有且仅有一个点使得答案最小。 考虑怎样求答案，假设当前在点 $k$，那么我们将其移动到一个相邻点，只有在靠近极值点时答案会变小，否则答案会变大，也就是说当我们靠近极值点的函数导数是负数。 列出点在一条边上的导数 $f'(x,k)=\frac32(\sum\limits_{i\notin\mathrm{subtree}(k)}w_i\sqrt{d_i+x}+\sum\limits_{i\in\mathrm{subtree}(k)}w_i\sqrt{d_i-x})$，只需要让 $f'(0,k)<0$ 就好了，然后直接往这个子树走。 但这样还是个暴力，点分一下可以做到 $O(n\log n)$。 ## 22.CF566E Restoring Map(14) 特判掉少于三个点的情况。 如果两个点的集合交只有两个元素，那么他们之间一定有边，用这种方法可以找出来所有非叶子节点之间的连边。 如果这样一条边都没连出来，说明是菊花图，直接输出。 如果只连出来一条边，那么非叶子节点的集合一定被分成了两类，分别挂到一个非叶子下面即可。 然后是多于三个非叶子节点的情况。我们记录一下刚才已经练了哪些边，那么叶子的父亲的连边情况和自己的集合中去掉所有叶子节点后是相同的，找到后就可以连边。 问题在于我们好像还不知道叶子的集合是哪个，但是显然他应该是包含自己的集合大小最小的那一个，找出来就好了。 时间复杂度 $O(\frac{n^3}{w})$。 ## 23.CF568C New Language(10) 很有水平的 *2600。 一眼 2-SAT，但是有个字典序最小的限制，普通的 tarjan 好像不太能处理。 注意到 $n,m$ 很小，有一种暴力的方法是直接 dfs 来判断是否满足条件，时间复杂度是 $O(nm)$ 的，在这题是可以接受的。 类似数位 dp 维护一个标记 $flag$ 表示前缀是否顶下界，如果是就先判断这一位能不能取最小的，否则判断能不能取 a。 无解只有两种情况，一种是 2-SAT 本身无解，另一种是后面无法大于给出的串。 如果不能取，就取另一个集合最小能取的，并且把标记修改掉。 时间复杂度 $O(nm)$，实现起来只能说很复杂。 ## 24.CF568E Longest Increasing Subsequence(11) 因为多次填相同的数答案不会更优，所以暂时忽略这个限制。 先跑一遍那个 $O(n\log n)$ 的 LIS 做法，如果遇到 $-1$ 就枚举所有可以填的数。 这样就求出来了 LIS 长度，然后倒着推出序列。 记录一下每个不是 $-1$ 的点的前缀，然后如果当前点不是 $-1$ 直接找前缀，如果前缀是 $-1$ 直接二分出来可以填的最大值填上，如果当前点是 $-1$，那么我们暴力从前缀找第一个 dp 值和他相差 $1$ 而且比自己值小的不是 $-1$ 的位置转移过去。如果没找到，那么说明前驱也是个 $-1$，找到最近的 $-1$ 走过去。 这样跑完之后剩下的 $-1$ 可以随便填，复杂度 $O((n+m)k+n\log n+m\log m)$。 ## 25.CF571D Campus(9) 把询问差分一下，如果我们可以求出每个点上一次被清零的时刻，就可以转化为前缀和作差了。 把询问离线，先建出第二个集合的重构树，每次 ```Z``` 操作是子树覆盖，然后就可以求出上次被清零的时刻，```Q``` 就变成了两次单点求值。这部分可以线段树维护。 然后建出来第一个集合的重构树，每次 ```A``` 操作是子树加，还要支持单点查询。直接 bit 就可以。 时间复杂度 $O((m+n)\log n)$。 ## 26.CF571E Geometric Progressions(15) 思维难度应该是不到 15 的，给 15 的原因是太难写了。 考虑合并两个等比数列。 首先分解质因数，然后考虑合并的时候，如果两边的公比部分次数都是 $0$，直接判断首项的次数是否相等。 如果只有一边是 $0$，那么答案只有可能是 $a_i$，直接判一下。 否则就有一个不定方程，把所有不定方程放在一起去重，如果有超过一个方程那么就有唯一解或者无解，直接判一下。 否则 exgcd 解出来最小正整数解，作为新的等比数列即可。 时间复杂度 $O(能过)$。 ## 27.CF573E Bear and Bowling(10) 考虑贡献延后计算，有一个显然的贪心是每次选价值最大的，然后给前面的数的价值加上选的点的权值，后面的数权值加上自己的权值。 我们需要数据结构支持单点删除，全局 $\max$，前缀加，后缀加 $a_i$。 发现全局 $\max$ 这种没有结合律的东西看起来没法和后缀加 $a_i$ 这种操作一起在数据结构上维护，考虑分块。 维护一次函数 $w_i=k_ia_i+b_i$ 表示这个点前面选了 $k_i$ 个数，后面选的数价值和是 $b_i$，这个东西的查询是类似斜率优化 dp 的，同一个块内应该用单调队列维护一个凸壳。考虑选了一个点之后，整块我们可以直接维护 $k,b$ 的标记，散块暴力重构即可。 注意到所有 $k_i$ 都是单调不降的，所以查询的时候可以直接右移左指针，不用二分。 时间复杂度 $O(n\sqrt n)$。 ## 28.CF575A Fibonotci(6) 大概是上面连着难题，于是有了个放松题。 如果没有取值不同的点就直接周期矩乘，有了特殊点我们就直接把有特殊点的周期拿出来单算就好了，使用线段树维护矩阵，特殊点就是单点修改。 时间复杂度 $O(n+m(\log n+\log k))$。 ## 29.CF575E Spectator Riots(114514) 计算几何，润。 ## 30.CF575I Robots protection(9) 直接做的话条件是 $x\geq x_i,y\geq y_i,x+y\leq x_i+y_i+len_i$，这是个四维数点。 容斥前两个限制，发现所有情况都是三维数点，值域很小，直接就做完了。 时间复杂度 $O(q\log^2 n)$。 ## 31.CF576D Flights for Regular Customers(7) 首先如果 $1$ 的出边没有边权是 $0$ 的或者 $1,n$ 不连通那就寄了，否则一定有解。 设 $dp_{i,j}$ 表示走 $i$ 步能否恰好停留在点 $j$，这个东西就是传递闭包，一次可以在 $O(\frac{n^3}w)$ 的时间内解决。 然后注意到随着时间变化邻接矩阵只有 $O(m)$ 种，我们直接枚举这些关键点，加入新的边之后如果图连通，那么从现在起 $n$ 步以内一定可以到达终点，直接枚举每次传递闭包即可。如果不连通，那么这一段都不会有解，直接跳到下一个关键点，这一段的邻接矩阵都是一样的，可以直接矩阵快速幂。 时间复杂度 $O(\frac{n^3m\log d}w)$。 ## 32.CF576E Painting Edges(6) 颜色数量很少，直接每种颜色开一个并查集维护是否是二分图。 如果只染色就很简单了，但是问题是一条边可能之前已经染色过。 不会删除怎么办？线段树分治，做完了。 时间复杂度 $O(n\log^2n+nk)$。 ## 33.CF578E Walking!(7) 题意等价于将字符串划分为尽可能少的 ```LR``` 交替的子序列，求答案可以直接贪心匹配。 考虑构造，所有匹配出来的段可以按照首尾字母分成四类，发现当且仅当只存在 ```LR``` 和 ```RL``` 时我们无法构造。 这种情况我们直接找一对，把末尾给对面，就有了一个 ```LL``` 和一个 ```RR```。 剩下的情况直接分类讨论即可。 ## 34.CF578F Mirror Box(11) 你看镜子他是一条斜线，是不是很像一条边（暴论 你把他看成在 $(n+1)\times(m+1)$ 的坐标系上连边，黑白染色后两部分是独立的，一张图合法当且仅当黑点或白点的子图是一棵树。 考虑如果有环，那么内部光线照不到，如果不连通，入射光线没法从相邻区域射出。 如果一种颜色的摆放确定了，那么另一种颜色也就确定了，所以先缩点，直接两边做矩阵树答案相加即可。 时间复杂度 $O(nm+k^3)$。 ## 35.CF582D Number of Binominal Coefficients(13) 勒让德定理：$p\in prime$，则 $n!$ 质因数分解中 $p$ 的次数是 $\sum_{i=1}\lfloor\frac{n}{p^i}\rfloor=\frac{n-S(n)}{p-1}$，$S(n)$ 表示 $p$ 进制下 $n$ 的数位和。 推论：$\dbinom {n+m}m$ 中 $p$ 的幂次等于 $n+m$ 在 $p$ 进制下进位次数。 这题就是这个定理的板子了。 直接求不合法的数量，$dp_{i,j,0/1,0/1}$ 表示前 $i$ 位，进位 $j$ 次，是否从下一位进位，是否顶上界的方案数，转移讨论一下有多少种可能，比较复杂。 时间复杂度 $O(\log_pA(\log A+\log_pA))$。 ## 36.CF582E Boolean Function(11) 建出来表达式树，记 $dp_{i,s}$ 表示点 $i$ 子树内每个函数的算出来的值是 $s$ 的方案数，转移直接按照操作符号讨论，分别是与卷积和或卷积，直接 FMT 加速即可。 时间复杂度 $O(|s|n2^n)$。 ## 37.CF585E Present for Vitalik the Philatelist(9) 可以分别算出满足 $\gcd(S)>1$ 的 $(S,x)$ 数量和 $\gcd(x,\gcd(S))>1$ 的 $(S,x)$ 数量相减来得到答案。记 $sum_i$ 表示 $a$ 中有多少 $i$ 的倍数，直接推一波式子。 $$\sum\limits_{x,S,x\notin S}[\gcd(S)>1]=\sum\limits_{i=2}^{10^7}-\mu(i)\sum\limits_{j=1}^{sum_i}(n-j)\dbinom{sum_i}j=\sum\limits_{i=2}^{10^7}-\mu(i)(n(2^{sum_i}-1)-sum_i2^{sum_i-1})$$ $\sum\limits_{x,S,x\notin S}[\gcd(x,\gcd(S))>1]=\sum\limits_{i\mid x,i>1}-\mu(i)(2^{sum_i-1}-1)

先调和级数求出 sum，上面的直接枚举一遍，下面的枚举 x，由于 \max_{i=1}^{10^7}\omega(i)\leq 8 所以可以直接 O(2^{\omega(x)}) 大力计算。

时间复杂度 O(V\ln V+n2^{\omega(n)})。

38.CF585F Digits of Number Pi(7)

3200? 2300!

把 s 的所有后缀建一个 AC 自动机，对每个点求出深度之后，一个串的匹配可以看做在 AC 自动机上走，这个串出现了长度不小于 \lfloor\frac d2\rfloor 的 s 的子串当且仅当行走的路径上经过了深度大于等于 \lfloor\frac d2\rfloor 的点。

接下来是数字范围的限制，套路地差分一下转化为 [1,y] 的答案减掉 [1,x-1] 的答案，然后这种数字上界的限制自然想到数位 dp。

记 dp_{i,0/1,0/1,j} 表示填了前 i 位，当前前缀是否顶上界，是否已经经过了深度大于 \lfloor\frac d2\rfloor 的点，当前位于 AC 自动机上 j 号点的方案数。

转移的时候直接枚举下一位填什么，沿着 AC 自动机上的边走过去即可。

时间复杂度 O(n^2d)，可以滚动数组优化掉第一维状态。

39.CF587D Duff in Mafia(11)

二分答案，钦定大于 mid 的都不能选。

考虑 2-SAT，首先钦定不选的边连边 i\rightarrow i'；然后考虑选的边是个匹配，所以对每个点的所有边排序，两两连 x_i\rightarrow x_j' 的边；最后每种颜色不选的是个匹配，在每个点给每种颜色的边分别排序，两两连边 x_i'\rightarrow x_j。

这样边数是 O(m^2) 的，直接前缀优化建图就做完了。

时间复杂度 O(m\log V)。

40.CF587F Duff is Mad(13)

建 AC 自动机，然后有两种暴力。

第一种是对于询问串经过的所有点加 1，然后对于每个串查询末尾点子树权值前缀和，然后询问时直接差分算答案。

第二种是把询问差分成 [1,l-1] 和 [1,r] 两部分，扫描右端点，每次加入一个串就给末尾点子树权值加 1，然后询问的时候暴力跳，查询每个点的子树权值和。

然后根号分治一下，|s_k|>B 的跑第一种，否则跑第二种， B=\frac n{\sqrt{q\log n}} 时有理论最优复杂度 O(n\sqrt{q\log n})。

但是这都是理论的，真要搞成这个块长是过不去的，块长调成 100 直接飞快地过了（

41.CF590E Birthday(11)

先搞 AC 自动机，子串包含关系之间连边。

暴力不行，直接路径压缩。

然后要求这个图的最大独立集，我超，挑战NPC……这是个可比图，把边钦定从长度大的向长度小的连之后就是个 DAG，转化为求最长反链。根据 Dilworth 转化成最小链覆盖，再传递闭包转化为最小不交链覆盖，最小不交链覆盖又等于总点数减掉拆点二分图的最大匹配，直接流就完了。

时间复杂度 O(\sum|s|+n^3)。

42.CF594E Cutting the Line(16)

我超，大魔王。

这个题被火药桶拉去当联考题了，我被拉去打工写了题解，直接放在下面。

一些约定：

首先，若 k=1 我们无法进行分段，直接判断 s 和 \overline s 的大小输出较小的。

然后考虑一种比较特殊的情况 k=n，我们可以随意分段。

引理1：在 k=n 时一定存在一种最优构造使得每一段都被翻转。

证明：如果存在一段没有翻转，我们直接把这个串分成单个字符并且翻转，串是不变的。

有了这个结论之后，问题等价为将 \overline s 分成若干段倒序拼接，使得最终串字典序最小。

引理2：一个字符串的最小后缀在串中出现位置不交。

证明：如果相交，那么相交的部分是更小的后缀，矛盾。

那么我们找到 \overline s 的最小后缀 t，贪心地放到答案串里面一定是不劣的。

那么我们已经有了一个做法：每次找到 \overline s 的最小后缀 t，把 t 加入答案串的末尾并在 \overline s 中删除后缀 t，重复操作直到 \overline s 被删空。

这个过程就是对 \overline s 做 Lyndon 分解，直接跑一遍就做完了。时间复杂度 O(n)。

接下来考虑 k=2，我们只能分割一次，不妨试试分类讨论。

首先，如果你足够牛逼可以枚举断点，直接建后缀自动机 O(1) 查询任意两个串的 LCP。但是这个做法太暴力了，我们来看看优美一些的做法。

以下的翻转是指在反串的基础上翻转。

  1. 两段都翻转：这不原串吗。
  2. 两段都不翻转：这相当于把 \overline s 旋转了若干位置，那么最小的串就是 \overline s 的最小表示，可以通过求一遍 \overline s+\overline s 的 Lyndon 分解得到。时间复杂度 O(n)。
  3. 第一次翻转，第二次不翻转：从后向前枚举断点，假设当前枚举的断点是 i，目前最优解在 j。那么我们就是要判断 \overline{\overline s[i,j-1]}+s[1,i-1] 和 \overline s 的字典序大小。这个问题等价于询问 \overline{\overline s[i,j-1]} 和 \overline s 的LCP、 \overline s[j-i+1,j-1] 和 \overline s 的 LCP，所有询问串都是 s 或 \overline s 的，直接对 \overline s+s 跑一遍 Z-algorithm 就能快速判断。时间复杂度 O(n)。
  4. 第一次不翻转，第二次翻转：我们把 \overline s 写成 A_1^{\alpha_1}A_2^{\alpha_2}\cdots A_m^{\alpha_m}=B_1B_2\cdots B_m 的形式，其中 A 是 \overline s 的 Lyndon 分解，B_i=A_i^{\alpha_i}。

定理1：划分的第一段一定可以写成 B_iB_{i+1}\cdots B_m 的形式。

证明：如果分界点在两个 A 之间，因为两边都是相同的 A，所以一定有一侧移过去答案会更优；如果分界点在 A 内部，那么根据 Lyndon 串的性质移到边界是更优的。

引理3：若 s_1 是 Lyndon 串并且满足 s_1>s_2\geq s_3，则 s_1>s_2+s_2\geq s_2+s_3。

证明：如果 s_2 不是 s_1 的前缀，直接比出大小，否则 s_1[1\cdots|s_2|]>s_1>s_2\geq s_3，成立。

定理2：B_iB_{i+1}\cdots B_m>B_{i+1}B_{i+2}\cdots B_m。

证明：由 引理3 可得 B_iB_{i+1}\cdots B_m>A_i>B_{i+1}B_{i+2}\cdots B_m。

因此若第一段取 B_iB_{i+1}\cdots B_m 当且仅当 B_{i+1}B_{i+2}\cdots B_m 是 B_iB_{i+1}\cdots B_m 的前缀。

定理3：若 B_{i+1}B_{i+2}\cdots B_m 是 B_iB_{i+1}\cdots B_m 的前缀，那么 2\mathrm{len}(B_{i+1}B_{i+2}\cdots B_m)\leq\mathrm{len}(B_iB_{i+1}\cdots B_m)+1。

证明：如果不成立，那么 B_i 是 B_{i+1}B_{i+2}\cdots B_m 的前缀，与 B 数组的定义矛盾。

因此只有 O(\log k) 个段可能成为答案。

假设 B_iB_{i+1}\cdots B_m 比 B_{i-1}B_i\cdots B_m 优，考虑下图（直线表示平移，曲线表示翻转）：

根据假设可以得到 \overline X<Y，由此又可以直接推出 B_iB_{i+1}\cdots B_m 比 B_{i-2}B_{i-1}\cdots B_m 优。

因此我们只要找到第一个最大的 i 使得 B_iB_{i+1}\cdots B_m 比 B_{i-1}B_i\cdots B_m 优，那么 i 就是最优解。

比较一次是 O(len) 的，所以我们可以直接暴力比较，时间复杂度 O(n)。

最后四种情况取 \min，我们就在 O(n) 的时间复杂度内解决了这个问题。

最后解决原问题，如果你想出了 k=2 和 k=n，那么你距离正解已经非常接近了。

从 k=n 的做法除法，考虑 k\geq 3 时的做法，假设当前 \overline s 的最小后缀是 A，那么我们将所有的 A 提取出来，可以写成 \overline s=s_1+A^{\alpha_1}+s_1+A^{\alpha_2}\cdots+s_m+A^{\alpha_m}。其中 \alpha_i>0,|s_i|>0。

如果我们在这一步取 A^{\alpha_m}，那么在末尾至少可以有 \alpha_m+\max\limits_{i=1}^{m-1}\alpha_i 个 A，否则一定取不到这么多个。

看起来取 A^{\alpha_m} 是最优的，但是还有一些问题。考虑 \overline s=efcdbbaa,k=3，那么有 A^{\alpha_m}=aa，我们第一段直接取出来之后的最优解是 ans=aabbefdc，但实际上的最优解是 ans=aabbcdef。

这里的问题在于 aa 和 bb 都是回文串，如果连续两次取的最小后缀都是回文串，那么我们是可以合并为一次操作的。

这样问题被我们圆满解决，具体流程为： 1. 特判 $k=1$； 2. 求出 $\overline s$ 的 Lyndon分解； 3. 不断取出若干重复的最小后缀加入答案末尾，并判断相邻的两种最小后缀是否回文，直到 $k=2$； 4. 分类讨论四种情况，取最小的加入答案末尾。 时间复杂度 $O(n)$。 ## 43.CF603E Pastoral Oddities(8) 有傻子给可撤销并查集路径压缩了，我不说是谁。 题目的要求转化为所有联通块大小都是偶数，考虑如果是奇数那么显然矛盾，偶数只要找一棵生成树，然后和父亲连边当且仅当自己的度数是偶数就能构造，所以是充要的。 静态的问题容易用并查集解决，动态的问题中可以注意到每条边产生贡献的是一个时间区间。 于是线段树分治，时间倒着跑，每到一个叶子暴力将权值尽量小的边加进来即可，同时在线段树上插入这条边。 时间复杂度 $O(m\log m\log n)$。 ## 44.CF605E Intergalaxy Trips(10) 记 $dis_k$ 表示从 $k$ 到 $n$ 期望走多少步，在策略中我们应该都是贪心地找一个可以转移的最优的状态走过去。 所以我们会走一个转移，当且仅当更优的都取不到，所以有转移 $dis_i=\frac{\sum\limits_{j,dis_j<dis_i}p_{i,j}dis_j\prod\limits_{k,dis_k<dis_i}(1-p_{i,k})+1}{\prod\limits_{j,f_j<f_i}(1-p_{i,j})}$。 这个东西不会从期望大的点往小的点转移，所以可以直接 Dijkstra。 时间复杂度 $O(n^2)$。 ## 45.CF607E Cross Sum(114514) 集训队作业计算几何浓度很高啊。 ## 46.CF611G New Year and Cake(114514) 怎么会是呢。 ## 47.CF611H New Year and Forgotten Tree(12) 先把同种位数的点缩起来，如果一个状态的每个子集点数量都大于边的数量那么就是有解的。 判断是否有解的复杂度很低，可以直接暴力循环每次删掉一条边并判断是否合法。 时间复杂度 $O(n\log_{10}^4n2^{\log_{10}n})$，跑不满。 ## 48.CF613E Puzzle Lover(13) 钦定起点在终点左边，一条合法路径可以分成三部分： - 左边绕一个圈子； - 从左走到右，中间可以上下横跳； - 右边绕一个圈子。 第一步和第三步可以直接字符串哈希算出来，中间的部分考虑 dp，记 $dp1_{i,j,k}$ 表示当前在 $(i,j)$，匹配了 $k$ 位，上一步是在 $(i,j-1)$ 的方案数，$dp2_{i,j,k}$ 表示当前在 $(i,j)$，匹配了 $k$ 位，上一步在 $(i\oplus1,j)$ 的方案数，转移直接枚举下一步怎么走。 起点在终点右边的情况直接把 $w$ 翻转再跑一遍。 注意这样没有只有第一步的走法会算两次，要把多的减掉。 时间复杂度 $O(n|w|)$。 ## 49.CF626G Raffles(8) 分别考虑每个牌堆，每下一注彩票获得的期望收益的导数是恒负的，这意味着收益单调递减。于是静态的情况我们可以直接用堆维护每一个奖池下注增加的收益贪心取最大的。 动态的情况下，由于每次修改的变化量是 $1$，所以最多只会引起一注彩票的下法改变，因此直接用 multiset 维护决策即可，时间复杂度 $O((n+t+q)\log n)$。 ## 50.CF627F Island Puzzle(13) 记 $a,b$ 中 $0$ 的位置分别是 $s,t$，发现这个操作是可逆的，因此如果不加边只有一种走法，直接从 $s$ 走到 $t$ 然后判断一下即可。 如果不合法，考虑基环树，发现我们其中一种可行的策略（不要求最小化步数）是先从 $s$ 走到 $t$，然后从 $t$ 走到换上挂着 $t$ 子树的点 $p$，在上面转转转然后走回 $t$。 于是 $t$ 到 $p$ 的路径上数字不变，环上的数字被整体转了若干个位置。 于是需要调整的数字在树上需要是一条路径（因为加一条边要恰好成环），$p$ 就是环上最浅的点的父亲，而且这些点的 $a,b$ 序列需要是一个轮换。 如果 $p$ 不唯一，这些点不是一条路径，或者不是轮换那么就寄了。 否则说明合法，加边的端点就是路径的两个端点。 最后最小化步数，环上我们既可以正着走也可以倒着走，两种分别求一下需要绕多少圈即可。 时间复杂度 $O(n)$。