SD 一轮省队集训笔记

· · 个人记录

太美丽啦，沙东省集！

括号内是期望得分。

Day 1

打了依托史，不会人均 T1，没空写唐氏 T2，技不如人。 T1 交了个打表看出来的部分分有个地方还打错了，根本不是人。 ### A 限制比较强，先简单推一下，将以 $(x,y),(x+1,y),(x,y+1),(x+1,y+1)$ 为左上角的四个矩形进行一些加减操作，可以得到 $a_{x+r,y+c}=a_{x+r,y}+a_{x,y+c}-a_{x,y}$，进一步地继续代换可以得到 $a_{x,y}=a_{x\%r,y}+a_{x,y\%c}-a_{x\%r,y\%c}$，也就是一个同余的形式。 如果确定了矩阵前 $r$ 行和前 $c$ 列的数自然可以填出整个矩阵，但是这个矩阵不一定合法，可能会出现 $2$ 和 $-1$，手玩一下可以发现规避掉这种情况的条件是 $a_{x,y}$ 与 $a_{x\%r,y}$ 和 $a_{x,y\%c}$ 中的至少一个相等。更进一步地，对于 $\forall 1\le i\le r,1\le j\le c$，我们要求 $\forall k\ge 1,a_{i+kr,j}=a_{i,j}$ 与 $\forall k\ge 1,a_{i,j+kc}=a_{i,j}$ 中至少要成立一个。也就是说，我们需要为左上角的 $r\times c$ 的区域中每个格子确定它对应的同余类是【行相等】还是【列相等】，当然可以两者都是。 然后有个直接的做法是枚举 $r\times c$ 个格子的取值和属于哪种相等做到 $O(5^{rc}\text{poly}(r+c))$（对于存在同时满足【行相等】和【列相等】的格子的情况，需要带 $(-1)^{cnt}$ 容斥系数来统计，因为我们只能钦定没法直接算），无法通过。但其实稍微手玩一下就发现枚举取值是没有必要的，填数的方案容易直接确定，所以可以直接做到 $O(3^{rc}\text{poly}(r+c))$。 ### B 傻逼题，为啥不直接闷着头写呢。 容易想到枚举一个合法的点对 $(x,y)$，钦定它是中位数然后统计，此时我们要求第三个点离其中一个点更近，离另一个更远。 然后这里可以直接使用 bitset 做到 $O(\frac{n^3}{w})$ 跑特殊性质，然后可以直接大力四毛子做到 $O(\frac{n^3}{\log n})$，不知道能不能过。 当然，我们转切比雪夫距离之后，限制其实就是查两个正方形异或后范围内的点，可以直接二维数点统计，这样是 $O(n^2\log n)$ 的（当然前缀和滚下空间其实是 $O(n^2)$ 的）。这种方法需要处理距离相同的情况，如果有两对距离相同是好算的，三对都相同因为要求了距离是质数，可以推出距离一定为 $2$，也是容易的。 因为这个奇怪的限制至少带个 $\frac{1}{20}$ 左右的常数，所以是可以通过的。 ### C 对于任意的图 $G$，在 $L(G)$ 上选出来一个最大独立集其实相当于在 $G$ 上选若干条没有公共点的边，也就是说答案其实是 $G$ 的最大匹配。更进一步地，$L^k(G)$ 的最大独立集等于 $L^{k-1}(G)$ 的最大匹配。 线图的经典结构就是由若干个团构成，考虑 $k=2$ 的答案，对于 $L(G)$ 的一个连通块随便取出一棵 dfs 树，很容易自底向上构造达到最大匹配的上界 $\lfloor\frac{|V|}{2}\rfloor$，对应到 $G$ 上也就是 $\lfloor\frac{|E|}{2}\rfloor$，对每个连通块求和就得到答案了。 $k$ 更大的情况也是一样的，我们只需要知道 $L^{k-1}(G)$ 每个连通块的点数即可。然后剩下的部分就没啥营养了，不看了。 ### P9342 [JOISC 2023 Day4] Bitaro’s Travel 注意到从一个点出发只会转向 $O(\log V)$ 次，然后用脚维护即可。 ### P9530 [JOISC2022] 鱼 2 考虑一次询问怎么做，显然每个位置也只会往左右扩展 $O(\log V)$ 次，当然可以笛卡尔树做到线性，但是这个做法不太好扩展。 考虑第 $i$ 条鱼能吃到的最大区间 $[l,r]$，显然有 $\sum_{i=l}^ra_i<\min(a_{l-1},a_{r+1})$，所以所有的区间 $[l_i,r_i]$ 之间要么不交要么包含。同时根据上面的过程，固定住一个端点 $l$ 时，所有的 $r$ 使得 $[l,r]$ 无法扩展的 $r$ 的个数只有 $O(\log V)$ 个，固定住 $r$ 也是同理的。 考虑线段树上直接维护，思考下哪些鱼是没法吃完整个区间的。首先一条鱼可以暂时吃不掉整个区间，但是它能扩展到的区间至少要碰到 $l,r$ 其中一个，所以可以只维护至少碰到了一个端点的区间和这个区间对应的鱼的个数。根据上面的性质线段树上一个点只有 $O(\log V)$ 个区间，合并时需要一些双指针来维护，细节很烦人。 注意到这个合并过程没有均摊，所以修改可以直接做，复杂度 $O(n\log n\log V)$。 ### CF1442D Sum 注意到肯定是取若干个完整的序列，最多只有一个没取完，所以缺一分治配个背包统计答案即可，$O(nk\log n)$。 ### P6109 [Ynoi2009] rprmq1 考虑如果询问的矩形都贴着坐标轴，可以直接扫描线+线段树维护区间加查区间历史 $\max$ 做。 否则尝试转化到上面的情况，考虑对着坐标轴其中一维猫树分治，给询问找到分治树上第一个跨过它的分治区间，从中线开始向左右分别扫描线，即可转化为上面的问题。 ## Day 2 $0(100)+0+0(15)=0(115)$，rk114514。 打的还是奶龙，感觉不应该开 T2，开 T3 会不会多点分来着。 代码怎么交错了，难过。 ### A 考虑 $k=1$ 的情况，我们只需要要求形成的图连通。这是个经典问题，直接设 $f_i$ 表示 $n=i$ 时的答案，只需要枚举 $1$ 号点所在的连通块大小进行简单容斥即可。 对于一般的情况，我们如法炮制，枚举 $1$ 号点能扩展到的点的数量，剩下不能连到的点我们会要求它们不能与 $1$ 连边，与 $1$ 能扩展到的其它点连边数量小于 $k$，预处理下转移系数就做完了，同样是 $O(n^2)$ 的。 其实开始想这题的时候在考虑一个 BFS 扩展的过程，也就是把图分层，但是后来弃掉了，事实上套个 DAG 容斥这个思路也是可行的。 ### B 考虑将一个斜正方形按照勾股定理的弦图拆开，会变成四个直角三角形和一个规整的小正方形。对于小正方形的部分只需要跑普通的二维数点，考虑直角三角形的部分。 直角三角形数点固然不好做，但是本题只需要判断合法性，考虑用贪心的思想维护一些最可能满足限制的点。具体来说，不妨考虑直角边面向第二象限的情况，考虑按照 $x$ 轴的方向扫描线，遇到一个点就把它加入到数据结构的对应纵坐标位置，在直角顶点处处理查询，算出斜边的斜率 $k$，则只需要用一条斜率为 $k$ 的直线截底边上方的点找到截距最低的即可，可以直接线段树维护凸壳查询的时候二分（横坐标单调所以加点的复杂度是对的），或者李超树插入一些线段，复杂度 $O(n\log^2 n)$。 当然还有些 KDT 之类的做法，但我并不会而且数据卡掉了。 ### C 首先 CRT 的解是具有唯一性的，也就是对于同余方程组 $$ \begin{cases} x\equiv a_1\pmod{p_1^{q_1}}\\ x\equiv a_2\pmod{p_2^{q_2}}\\ \ldots\\ x\equiv a_{n'}\pmod{p_{n'}^{q_{n'}}} \end{cases} $$ 所有的 $x\in[0,n-1]$ 都唯一对应一个 $a$ 序列，同理确定了 $a$ 序列也唯一对应一个数 $x$。 对数 $x$ 定义长度为 $m$ 的字符串 $t$，其中 $t_i(i\in[0,m-1])=[\gcd(x+i,n)=1]$，那就是要求有多少个数 $x$ 对应的字符串 $t$ 和题目中给出的串 $s$ 相同。考虑通过确定 $a$ 序列来进一步确定 $t$，具体来说我们发现 $t_{i}=1$ 当且仅当 $\exist j,a_j+i\equiv 0\pmod{p_j}$。 考虑把 $p_i$ 按照和 $m$ 的大小关系分类。当 $p_i>m$ 时，相当于可以任意将 $t$ 的一个位置钦定为 $1$，或者什么都不做。显然具体钦定了哪些位置不重要，只需要关心被钦定的位置数量，所以可以直接 dp，设 $f_{i,j}$ 表示考虑了前 $i$ 个 $>m$ 的质因子，当前 $t$ 有 $j$ 个位置被钦定成了 $1$，转移分钦定一个新位置，钦定一个被选过的位置，什么都不干三种情况，这部分复杂度是 $O(n'm)$ 的。 当 $p_i\le m$ 时，相当于可以初始选择 $a_i\in[0,p_i-1]$ 并使得 $\forall k\ge0,t_{a_i+kp_i}=1$。因为质因子比较小所以考虑直接爆搜，每个质因子将选择的位置和对应的同余类覆盖，查一下上面 $>m$ 时的 dp 数组即可统计答案，这部分复杂度取决于状态数量。 当然这个只有在 $\min p_i=2$ 的时候状态数才是真的不多，交上去可以通过 $70$ 分，剩下的部分看不懂了，难过。 ### QOJ7767/QOJ9648/毛毛虫剖分 好像掉线了啊，难过。 ### P7215 [JOISC2020] 首都 转化一下题意，相当于是要在树上选择一个连通块，使得如果一个颜色要么不在连通块内出现，要么全部出现在连通块内，最小化这个连通块的不同颜色数。 考虑如果选好了一个点，那么找到其它所有和它同颜色的点，这些点以及和开始选好的点路径上的点也都要选，同时新选的点又会带来些新的颜色，不断重复此过程就能找到包含开始选的点的大小最小的连通块。 固定住一个点这种操作可以直接考虑点分治，直接求出包含分治中心的最小合法连通块，答案如果跨过分治中心那我们一定能统计到，否则显然可以递归到子树去。单层递归的复杂度是线性的，所以最后的复杂度是 $O(n\log n)$。 感觉固定一个点/和某个点连通的这种信息好像很多情况下都可以直接用点分治优化啊，见了好多道这种题了，可能有点感觉了？ ### P4183 [USACO18JAN] Cow at Large P 怎么简单题也掉线了，睡觉，有空再回来补。 ## Day 3 完全不会后两题啊。 $100+10+5=115$，rk14。 ### A 首先注意到每个点入度至多为 $1$，所以这是个外向基环森林，而因为有环一定无解所以这是个森林，哥们开始以为这是 DAG 白做了两个小时。 尝试直接 dp，发现不太可行，因为你非常需要知道子树外的信息，没法划分到子问题，所以这应该是个贪心题。正常人都很难不去考虑 exchange argument，那就推一推试试。首先单独一个关卡的期望通关时间容易知道是 $\frac{c}{p}$，考虑两个关卡 $(c_1,p_1)$ 和 $(c_2,p_2)$，那么 $1$ 在前和 $2$ 在前的答案就分别是 $\frac{c_1+p_1c_2}{p_1p_2}$ 和 $\frac{c_2+p_2c_1}{p_1p_2}$，令前者小于后者得到 $\frac{c_1}{1-p_1}<\frac{c_2}{1-p_2}$，形式非常完美，直接套用树上 exchange argument 的做法即可。 ### B 先考虑怎么判是否有解。每次把一个箱子从边界推进去这种操作十分复杂，换个角度看可以认为其实是找这个方向的第一个空格改成箱子，这样就优美很多，然后直接跑二分图匹配即可，建模大概就是边界外每个格子向网格内靠着边界的连续段连边。 然后考虑构造方案。我们要做的事情是给每个箱子安排顺序，限制就是它对应方向上比它更靠前的箱子要先推进来。如果限制关系形成 DAG 可以直接取一个拓扑序，否则可以发现环一定形如一个矩形框，手玩一下发现一个环上的点一定可以通过调整它们的匹配方式来消环，大概就是每条边的方向替换掉对应的顶点。 每次找一个环出来，重复上面的调整过程即可得到解，但是如何分析复杂度？考虑定义势能 $\varphi$ 表示当前每个箱子到它对应方向上边界的距离之和，容易发现一次调整会消耗环长大小的复杂度使 $\varphi$ 减少环长，所以复杂度和初始的 $\varphi$ 量级相同，显然为 $O(n^3)$。 ### C 第一道积分题。 首先令 $sum=\sum_{i=1}^na_i$，显然当 $sum\ge 360$ 时不可能合法，所以实际上本题 $n<360$。 可以观察到一个性质，除了最左右两个灯塔，其它的灯塔照射的范围一定全在 $x$ 轴上方或全在 $x$ 轴下方，否则一定会有交，而两边的灯塔可以朝两边照。 记照射范围全部在 $x$ 轴上方的灯塔数为 $k$，它们的角度和为 $A$，这里可以直接预处理个背包得到选出一对 $n,k$ 的方案数，考虑进行一些分类讨论计算概率（下面的概率全都要除以 $360^n$）。 #### 1. 左右两个灯塔照射范围全部在 $x$ 轴上方/下方 考虑在 $x$ 轴上方的部分，不妨把这 $k$ 个角顶点拼在一起，则它们的边之间不会交叉。可以看成是初始有一个度数为 $180-A$ 的角，然后每次要选一个位置插入一个选过的角，容易得到概率是 $\frac{(180-A)^k}{k!}$。 在 $x$ 轴下方的部分也是同理的，乘起来得到此时的答案是 $$ \frac{(180-A)^k(180-(sum-A))^{n-k}}{k!(n-k)!} $$ 可以直接计算。 #### 2. 左右两个灯塔其中一个跨过了 $x$ 轴 不妨假设是左边的灯塔，右边的情况是类似的。 考虑如果确定了左边的灯塔有 $x$ 的角度在上方，那么上下两部分的概率仍然可以使用刚才的方法计算。求出 $x$ 的合法取值范围 $[L,R]$，则这部分的答案就是 $$ \int_{L}^R\frac{(180-A-x)^k(180-(sum-A-x))^{n-k-1}}{k!(n-k-1)!}dx $$ 显然要积分的东西是个关于 $x$ 的多项式，直接把这个多项式的系数算出来即可。 #### 3. 左右两个灯塔都跨过了 $x$ 轴 设左边的灯塔在 $x$ 轴上方的角度为 $x$，右边的灯塔在 $x$ 轴上方的角度为 $y$，此时的概率为 $$ \frac{(180-A-x-y)^k(180-(sum-A-x-y))^{n-k-2}}{k!(n-k-2)!} $$ 看上去要算一个比较复杂的二重积分，比较倒闭。其实不然，注意到这个式子其实只和 $z=x+y$ 有关，而我们对 $x,y,z$ 的取值范围都有比较强的限制，所以考虑通过对 $z$ 的取值范围分讨解决。 下面设 $L\le z\le R$ 且 $a_1\le a_n$。 1. 当 $L\le z\le a_1$ 时，$x$ 的范围是 $0\le x\le z$，积分长度为 $z$，只需计算 $$ \int_{L}^{a_1}zf(z)dz $$ 2. 当 $a_1\le z\le a_n$ 时，$x$ 的范围是 $0\le x\le a_1$，积分长度为 $a$，只需计算 $$ \int_{a_1}^{a_n}a_1f(z)dz $$ 3. 当 $a_n\le z\le R$ 时，$x$ 的范围是 $z-a_1\le x\le a_n$，积分长度为 $a_1+a_n-z$，只需计算 $$ \int_{a_n}^{R}(a_1+a_n-z)f(z)dz $$ 直接把三个积分加起来即可，其中 $f(z)=\frac{(180-A-z)^k(180-(sum-A-z))^{n-k-2}}{k!(n-k-2)!}$。 考虑复杂度，需要枚举 $k,A$ 的取值并暴力求出多项式的系数，因此复杂度是 $O(n^4)$ 的，但是这里只需要枚举到 $180$ 且常数较小，所以可以通过。 ### P5576 [CmdOI2019] 口头禅 先考虑对串建广义 SAM，称 parent 树上一个点 $u$ 的颜色集合 $C_u$ 为它代表的子串来自的原串编号集合。按照 $len$ 从大到小遍历 parent 树上的点，每个点 $u$ 开一个 set 维护 $C_u$ 内形成的连续段，把儿子的连续段启发式合并上来即可维护出自己的连续段。当一个询问被自己的一个连续段包含时可以对这个询问产生贡献，所以可以在自己的连续段发生扩大时更新询问。 更新询问可以考虑把这个过程离线下来再跑扫描线，但是有个更聪明的办法。考虑开一棵线段树维护所有询问，具体来说将询问 $[l,r]$ 挂在左端点上，权值为 $r$，每次连续段扩大时找到左端点在连续段内的询问中右端点最小的那一个，如果能贡献到就把这个询问删除，复杂度是 $O(N\log^2N)$ 的，其中 $N$ 表示总串长。 ### QOJ5034 >.< 把路径看成字符串，相当于找一条 $1$ 到 $n$ 的不出现给定的若干串的最短路。这种限制容易想到 AC 自动机，相当于自己或者 fail 树上祖先有终止点的点会被 ban 掉，然后在 AC 自动机上跑最短路。 首先字符集比较大，所以需要主席树存转移边。其次 AC 自动机的转移边数量不是线性的，暴力遍历所有转移边复杂度是错的。考虑一个点 $u$ 和 $fail_u$ 的大部分出边是重复的，可以在 $fail_u$ 松弛完之后将自己的转移边删去再继承到 $u$ 去，这样 $u$ 只需要遍历自己新加的转移边，复杂度就是正确的了。根据 dijkstra 的流程早取出的点 $dis$ 更小，所以这么做的正确性也是没有问题的，也就是删去的边用 $u$ 拿来更新肯定不优。 复杂度应该是 $O(n\log n)$ 的。 ### UOJ429 【集训队作业2018】串串划分 没学过 runs，以后再说。 ## Day 4 $0+95+10=105$，rk18。 T2 差点卡常通过了，但是 T1 T3 都是啥抽象。 ### A 场上通过这题的好像大多数都是神秘调整和乱搞。 首先有个结论是一定有解，然后尝试构造。考虑逐个枚举所有颜色填入，限制每行每列不能有重复可以直接二分图匹配解决，这样是对的，但是复杂度太高了。 upd：最大匹配是错的，被卡掉了/xk。 题解说，只需要给每行分配一个循环移位的优先级，然后跑稳定婚姻匹配即可，理解起来好像确实挺有道理，但是真抽象啊。 ### B 考虑分块，给每一个块开一棵 Trie。修改的时候，散块可以暴力把整个块的 Trie 删掉重构，整块直接打个标记处理。查询的时候，整块的部分可以按位确定答案，拉出来它们的 Trie 一起走一遍即可，散块可以考虑在这个过程中暴力扫，赛时为了卡常写的是提前取出来排序然后单指针 + lower_bound 算。 设块长为 $B$，修改的复杂度是 $O(B\log V+\frac{n}{B})$，查询的复杂度是 $O(\frac{n}{B}\log V)$，取 $B=\sqrt n$ 即可做到 $O(n\sqrt n\log V)$，大力卡常一下也许是能过的，赛时应该再多努力一下的。 std 的复杂度其实是 $O(n\sqrt{n\log V})$ 的，简单来说就是考虑压缩 Trie，也就是维护 Trie 的虚树。如果数已经排好序，因为整数求 lcp 可以 $O(1)$ 所以能线性建压缩 Trie，修改散块的时候可以考虑直接 dfs 原来的压缩 Trie 得到排好序的结果，把修改部分和未修改部分归并一下就能再线性建新的压缩 Trie，这样就去掉了修改时 $B$ 后面的 $\log V$，此时取 $B=\sqrt{n\log V}$ 就做到 $O(n\sqrt{n\log V})$ 了。 但是这东西写起来也太傻逼了。 ### C 抽象。 ### QOJ5523 Graph Problem With Small n 简单但是有趣的题。 考虑暴力的状压 dp，直接设 $dp_{S,x,y}$ 表示当前经过了 $S$ 内的点，起点是 $x$ 且终点是 $y$ 是否可行，复杂度 $O(2^nn^3)$，显然过不去。 转移好像没啥可优化，所以从状态入手。本题求的是无向图哈密顿回路，所以你发现一点就是起点是啥并不重要对吧，如果存在两个点 $y,z$ 使得 $x$ 能走两条不相交且并为全集的路径分别到达 $y,z$，且 $y,z$ 之间有边那就形成一条哈密顿回路了，而这个 $x$ 显然可以任取一个点。所以我们不妨固定起点 $x=1$，直接设 $dp_{S,y}$ 表示从 $1$ 出发，经过 $S$ 中的点能不能在 $y$ 停下，这样就得到了一个 $O(2^nn^2)$ 的做法，但还是无法通过。 进一步优化，dp 值存 $01$ 是比较浪费的一件事情，考虑直接把第二维压到 dp 值里，设 $dp_{S}$ 表示从 $1$ 出发经过 $S$ 内的点可能的终点集合，直接做就是 $O(2^nn)$ 的了，可以通过。 ### AGC031E Snuke the Phantom Thief 看上去就很像费用流，但是不太能直接做。 考虑推下限制，以第一类为例，横坐标 $\le x$ 的最多 $y$ 个，可以转化成第 $y+1$ 个横坐标必须 $>x$，其它三类限制同理。如果我们固定了总共偷走的珠宝数量 $k$，那么可以直接得到上下左右第 $i$ 个偷走的珠宝的横纵坐标范围，这个是可以直接费用流的，然后就做完了。 ## Day 5 $35+0(48)+35=70(118)$，rk38(19)。 T2 交的时候不小心删了个大括号，CE 了。 确实根本不会 T1，被组合击杀了，T2 T3 都比较困难。 ### A 考虑 $m$ 为奇数的情况，此时重心显然唯一。枚举一个点钦定是重心，只需要用 $\binom{m+n-1}{n-1}$ 减去钦定一个儿子的子树或者自己的子树补大于 $\frac{m}{2}$ 的情况，则我们需要知道 $$ f_s=\sum_{i=\frac{m}{2}+1}^m\binom{s+i-1}{s-1}\binom{n-s+m-i-1}{n-s-1} $$ 表示一棵大小为 $s$ 的子树和大于 $\frac{m}{2}$ 的方案数，直接计算可以做到 $O(nm)$。 考虑优化 $f_s$ 的计算，我们希望将求和指标改成与 $s$ 相关的东西。直接推好像推不出来啥，尝试使用些组合意义转化掉。比如可以考虑将树拍到 dfs 序上并认为这棵大小为 $s$ 的树占据了前 $s$ 个位置，那么我们要求前缀和第一个 $>\frac{m}{2}$ 的位置在这前 $s$ 个里，枚举具体是哪一个可以得到 $$ f_s=\sum_{i=1}^s\binom{\frac{m}{2}+i-1}{i-1}\binom{m-\frac{m}{2}-1+n-i}{n-i} $$ 然后直接计算即可，可以做到 $O(n)$。 考虑偶数的情况，可以发现能成为重心的点构成了一条链，而且形如链两端挂出去的子树和为 $\frac{m}{2}$ 且链中间都是 $0$。假如要计算链上的一个点 $u$，记 $S$ 为链上编号小于 $u$ 且到 $u$ 中间的点编号都大于 $u$ 的点集，那么 $|S|\le 2$，我们可以通过容斥钦定 $u$ 和 $S$ 中的点可以成为重心来计算 $u$ 在所有 $S$ 相同的链中的贡献。钦定了 $u$ 一个点的方案在上面已经算过了，只需要处理钦定两个和三个点的情况。可以从大到小加点，使用并查集维护钦定连通块挂出来的点的方案，做到 $O(n\alpha(n)+m)$。 ### B 哥们，这也太难了。 首先需要对冒泡排序的过程有点深刻的理解。不妨先考虑全局操作的做法，考虑一轮冒泡排序相当于是取出序列的所有前缀 $\max$ 并移动到下一个前缀 $\max$ 的位置，剩下的数往前移动，手玩一下可以得到一个结论：对序列 $a$ 进行 $t$ 轮冒泡排序后第一个数就是 $\min_{i=1}^{t+1}a_i$。这是因为根据上面的过程，每轮冒泡后每个数至多向前移动一位，所以 $t+1$ 后面的位置移不到 $1$，而 $[1,t+1]$ 的最小值显然会一直移动。 更进一步地，可以得到最后的第 $i$ 个位置的数其实就是 $a_{1\sim i+t}$ 去掉前 $i-1$ 个位置的数后的最小值，可以简单地使用堆模拟这个过程。 > 赛时我使用的是另一种理解解决的这档分：设 $c_i$ 表示 $\sum_{j<i}[a_j>a_i]$，一轮冒泡后 $c$ 序列的变化是将第一个数 shift 到末尾，然后整体 $-1$ 与 $0$ 取 max，最后根据 $c$ 数组还原序列。 > > yyc 告诉我，这个思路也是能扩展到正解的，他写了。 对于原问题，考虑操作分块，将每 $B$ 个询问分为一组，每组内将询问区间端点设为关键点，每个关键点之间为一块，这样每次操作只会在若干个整块内进行，显然只有 $O(B)$ 个块。 对每个操作从左到右处理它涉及到的块，块之间可能产生的变化只会是上一个块的右端点可能和当前块的左端点发生交换，我们需要取出它们进行比较。显然一个块的右端点在进行至少一次操作后一定是所有数的最大值，而左端点根据刚才的结论是前 $t+1$ 个数的最小值。可以给每个块分别开两个堆 $Q_1,Q_2$，维护块内前 $t+1$ 个数和块内的所有数。 当左端点和上一个块的右端点发生交换时，注意到紧接着当前块就需要一轮冒泡，新的左端点要么是新交换来的数，要么是剩下堆里数的最小值，所以并没有什么影响，直接把原来的左端点从 $Q_1,Q_2$ 中删除，新加入的数扔到 $Q_1$ 里即可。 当右端点和下一个块的左端点发生交换时，先在 $Q_1,Q_2$ 中删去原来的右端点，注意新的右端点需要再进行至少 $r-l$ 轮冒泡后才能移到左端点，所以要求 $r-l+1$ 轮开始才能把新的右端点扔进 $Q_1$ 内即可。 实现时需要实时维护每个块的 $t$ 和 $sum$，堆的删除可以惰性删除，查询时只需要遍历涉及的块把 $sum$ 相加即可。这里修改和查询的复杂度都带 $\log n$，所以可以直接取 $B=\sqrt n$ 做到 $O(q\sqrt n\log n)$，可以通过。 ### C 瞪了半天题解看懂了，补点我自己口胡性的证明。 yyc 告诉我，这题应该这么想：观察大样例发现答案是 $O(L)$ 级别的，然后想想这是为什么。 先对所有的串建立 AC 自动机。考虑枚举最长的串 $s_k$，由于子串是前缀的后缀，枚举 $s_k$ 的所有前缀，找到每个前缀最长和次长的后缀使得它在 AC 自动机上是终止结点，那么 $s_i$ 显然只能取在这些串里（取其它的子串显然符合条件的 $j$ 大于 $1$），更进一步 $s_j$ 也来自这些串。 但是这只是一个必要条件，并不充分。对 $s_i$ 还有一个限制就是，必须恰好有一个最长/次长后缀满足 $s_i$ 是它的子串，这个可以倒着枚举所有前缀，以长度为下标开个树状数组判。 当然这还不是充要的，现在唯一的问题是会不会有既不是最长后缀也不是次长后缀的串 $t$ 使得 $s_i\subsetneq t\subsetneq s_k$。其实是有的，如何判呢？事实上这种 $t$ 一定都是所有次长后缀在 fail 树上不包含自己的所有祖先，显然这些串都满足是 $s_k$ 的子串的限制，唯一的问题是有些 $s_i\subsetneq t$ 的情况会不会漏？事实上并不会，这个问题产生的原因是 fail 只会直接跳自己的后缀但子串是前缀的后缀，但是如果我们需要在某个前缀跳 fail，这种情况在考虑 $s_k$ 的以它结束的整个前缀时会考虑到，所以没问题！ 对于最后一种条件，判断起来只需要平凡的链加单点查，转成单点加子树查，复杂度 $O(L\log L)$。 ## Day 6 爆零了。 T1 完全不会做，会了 T2 最难写的做法，冲刺出了 $0$ 分。 ### A 这也太几把难了吧？？？感觉想要深刻理解这道题需要花费巨大的功夫。 考虑如何判定一组 $(x,y)$ 是否合法。先考虑 $x$ 咋取，肯定是取出序列最靠前的 $x$ 个 $1$ 和最靠后的 $x$ 个 $3$，然后让它们按照顺序匹配出一个只相交不包含的结构（显然任何方式都可以不劣地调整成这样），然后同理再取出前 $y$ 个 $3$ 和后 $y$ 个 $1$ 来解决 $y$ 的匹配。 现在唯一的问题是 $2$ 应该怎么选。考虑一个二分图匹配的模型，左部点是是 $x+y$ 对匹配形成的区间，右部点是所有 $2$，每个区间向它包含的 $2$ 连边，则 $(x,y)$ 合法当且仅当二分图有完美匹配。直接考虑上 Hall 定理，由于前面提到的匹配结构，可以分析出来选左部点选一些连续相交的区间的时候限制最紧，也就是设 $F(l,r)$ 表示 $(l,r]$ 包含的匹配区间数量，只需要满足 $\forall 0\le l<r\le n,F(l,r)\le cnt_{r,2}-cnt_{l,2}$，其中 $cnt_{i,x}$ 表示 $[1,i]$ 中 $x$ 的数量。 考虑如何计算一个区间的 $F(l,r)$，需要进行一些讨论，比如 $x$ 个 $1$ 与 $3$ 匹配的区间贡献就是 $\max(0,x-cnt_{l,1}-(cnt_{n,3}-cnt_{r,3}))$。分析一下，考虑取出来 $x$ 个 $1$ 和 $3$ 匹配的区间，如果存在一对匹配跨过了 $(l,r]$ 则由区间不包含得到所有区间都不会被 $(l,r]$ 包含，此时 $F(l,r)=0$，不妨先忽略这种情况。否则，左侧的每个 $1$ 和右侧的每个 $3$ 都会和区间内的一个数匹配，直接减去它们的数量即可。发现对于出现了跨过 $(l,r]$ 的情况，一定会减到小于 $0$，所以和 $0$ 取 $\max$ 即可。对于 $y$ 的贡献同理。 考虑将 $F(l,r)$ 拆开，可以得到若干个限制 $x,y,x+y$ 范围的不等式，直接算出来即可统计答案，复杂度 $O(n)$。 ### B 首先有个很傻逼的做法是观察到任意时刻围住当前射线的边构成了一个凸多边形，然后你可以对纵坐标开数据结构维护凸壳，场上没冲出来，复杂度大概是 $O(n\log^2 n)$ 的。 其实有个人类点的做法，但是需要些观察。对于每条射线，找到它第一个相交的线段作为它的父亲，这样会连出一棵树。对于每条射线，分别找到它上下第一条线 $u,v$，那么 $u$ 和 $v$ 分别到 LCA 路径上的线段恰好就围出来了上面的多边形，分别从 $u$ 和 $v$ 向上倍增找到第一条相交的线段检查即可，复杂度是 $O(n\log n)$ 的，而且十分好写。 ### C 考虑分治，后面忘了。 ## Day 7 $100+12+21(28)=133$，rk18。 要么啥都不会，要么只会签到，难过。 ### A 考虑将选择一个区间看作连边 $l-1\to r$，一条边 $i\to j$ 表示我们知道了 $(i,j]$ 的区间和，那么答案就相当于是求这张 $n+1$ 个点的完全图的最小生成树边权和，其中 $i\to j$ 的边权是区间 $(i,j]$ 内的数的 $\gcd$。 考虑 boruvka，我们会为每个连通块找到伸出去的边权最小的边。那你发现在跑第一轮 boruvka 的时候每个点会选择连向 $0$ 或 $n$ 其中之一，而 $0$ 和 $n$ 之间的边一定会选，所以第一轮连边之后 MST 就已经求出。由此可得结论，答案就是对每个 $i$ 在 $[1,i]$ 和 $(i,n]$ 的 $\gcd$ 中取较小值相加。 考虑前后缀的 $\gcd$ 只会变化 $O(\log V)$ 次，可以直接线段树上维护区间前后缀变化的位置，然后分段统计答案即可，可以势能分析得到复杂度是 $O(n\log n\log V)$。 ### B 不要认为这题可能存在多项式复杂度。 先平凡地将贡献拆开，变成对每个回文串 $T$ 统计它在多少个串中出现过求和。考虑固定了一个串 $T$ 如何算贡献，设 $f_i$ 表示长度为 $i$ 且没有出现过 $T$ 的字符串数量，$g_i$ 表示长度为 $i$ 且 $T$ 恰好在 $[i-|T|+1,i]$ 第一次出现的字符串数量，首先显然有 $f_{i}=f_{i-1}\times k-g_i$，而 $g_{i}$ 首先应当从 $f_{i-|T|}$ 转移过来，但是 $T$ 可能会存在 border 所以这样会多算，假设 $T$ 存在长度为 $k$ 的 border 则 $g_i$ 还要再减去 $g_{i-|T|+k}$。 直接枚举串 $T$ 肯定没救，但是应该能注意到一点是一个串的贡献显然只和 $|T|$ 以及它的 border 集合有关，两者都相等的串贡献一样。因此考虑爆搜，枚举 $|T|$ 然后搜出来所有可能的 border 集合。当然这里有一些剪枝技巧，搜的时候从大到小枚举并用并查集维护相等关系，如果一个 border 的相等关系在并查集里已经全部连好了则直接把它加入集合。同时当 $|T|$ 超过总长一半时长度小于 $n-|T|$ 的 border 不用考虑，因为这时候把 $T$ 移过去会超出边界。 唯一的问题是，如何在确定 $|T|$ 和 border 集合后算出对应的 $T$ 的数量。考虑前面的并查集，直接算 $k^{\text{连通块数量}}$ 会把当前集合的超集也统计进去，但是可以直接再枚举它的超集减去对应的答案即可，也是容易的。 复杂度是爆搜出来的状态数乘上 $\text{poly}(n)$。 ### C 不会。 ## Day 8 $6(28)+45+15=66(88)$，rk22。 两个人均题都没过？？两个人均题都没过？？两个人均题都没过？？两个人均题都没过？？两个人均题都没过？？ ### A 考虑 $m=n-1$ 怎么做，只需要解决边权的匹配问题。显然一个权值肯定会分配给剩下的包含这个点权的区间中右端点最小的那个，这个过程可以简单用堆维护。 考虑一条非树边的限制，路径上的边权最大值要小于它。考虑把边看成点建一个 DAG，路径上每条树边向非树边连边，表示点权大小的限制。对于 DAG 上的问题，我们只需要分别正反跑一次拓扑排序更新下每个点的左右端点（$l_u+1\to l_v$，$r_v-1\to r_u$），然后重新按照 $m=n-1$ 的方法做即可。 实现时不需要显示地建出来 DAG，更新非树边的 $l$ 相当于查询路径最大值，可以倍增求；更新树边的 $r$ 相当于路径 chkmin，可以排序后树上并查集，复杂度是 $O(Tn\log n)$ 的。 赛时没想到最简单的更新左右端点这一步，为啥啊？？ ### B 啥几把。 ### C 逆天。