SD 四轮省队集训

· · 个人记录

Day 1

T1 开场没多久就秒了，稍微写了一会就通过了。T2 狗运做过，回忆了下做法，重新品味了一下通过。T3 是俄罗斯方块，玩得手指头快断了获得 eps 分。 ### A 感觉这种题完全能批量生产一车。 发现 $f(l,r)$ 就是 $[l,r]$ 内的点的虚树大小，考虑把虚树贡献拆一下，用每个点到根的路径并的大小减去每个点的 LCA 深度。前者肯定好求，经典地扫描线右端点，维护每个点最后被覆盖的时刻即可，可以上个树剖做树上颜色段均摊。对于后者，只是询问一次 $f(l,r)$ 可以直接信息合并。 询问区间的子区间自然就是套层历史和，但是区间内 LCA 的深度怎么做历史和？NOIP T4 告诉我们 $\text{dep}_{\text{LCA}(l,l+1,\ldots,r)}=\min_{i=l}^{r-1}\text{dep}_{\text{LCA}(i,i+1)}$，求出相邻的 LCA 作为新的序列，在这个序列上跑扫描线历史和即可。 复杂度 $O(n\log^2n+q\log n)$。 ### B [嘟嘟嘟](https://www.luogu.com.cn/article/2di2vufk)。 考虑一个重排后的排列应该长什么样子，不妨固定住一对 $l,r$ 满足 $l<r$，要求就是不能同时存在 $l<k_1,k_2<r$ 使得 $p_{k_1}<\min(p_l,p_r)$ 和 $p_{k_2}>\max(p_l,p_r)$，换句话说也就是 $p_l,p_r$ 里至少要有一个是区间 $[l,r]$ 的最值。 换个角度看，假设一开始有 $1$ 到 $n$ 这些数，要把它们排成一个合法的排列，就要求每次必须把当前的最大值/最小值插到当前没被插入数的最靠前/最靠后的位置，排列合法当且仅当每一步都满足这个条件，而我们希望最大化插入过程中与原排列重合的位置数量。 然后就有个暴力的区间 dp 做法，可以设 $f_{l,r,x}$ 表示区间 $[l,r]$ 以外的部分已经填完，当前剩下的最大值为 $x$ 时区间内最大的重合位置数量，转移直接枚举在左右端点填最大/最小值四种情况是 $O(1)$ 的，所以得到了一个 $O(n^3)$ 的做法。 继续优化，考虑在二维平面的角度上看这个问题。因为新排列一个区间内的数在值域上肯定是连续的，把 $p_i$ 看成平面上的点 $(i,p_i)$，那么对于 $p$ 的一个区间 $[l,r]$ 能包住区间内的点的最小矩形就是 $x\in[l,r],y\in[d,u]$ 的这么一个矩形，其中 $d,u$ 分别是区间内的最小值和最大值。而因为每次只会填左右端点的一个最值， 那么填完之后剩下的子区间对应的矩形 $u,d$ 的变化量只有 $1$，也就是说每次会删去当前矩形边缘的一个 L 形。而初始时整个排列对应的矩形显然是 $x\in[1,n],y\in[1,n]$ 这么个大正方形，所以每个区间对应的矩形也都应当是个正方形。 对于一个 $p_i$ 来说，它与新的排列重合相当于是 $(i,p_i)$ 作为了某个区间对应正方形的四个顶点之一。考虑到所有以 $(i,p_i)$ 为顶点的正方形其对应的另一个顶点坐标都形如 $(i\pm len,p_i\pm len)$（正负号对应了四个方向），对每个 $(i,p_i)$ 都把这种正方形找出来，发现问题其实可以转化为：平面内有 $O(n^2)$ 个正方形，你需要选择尽可能多的正方形使得它们之间是严格包含的关系。这是因为对于选出来的这些正方形，因为只有包含关系，我们一定能构造出一组方案使得这些正方形同时出现过，每出现过一个就多一个位置不需要交换，所以答案就是 $n$ 减去最多选出的正方形个数。 设 $f_{i,j,dir}$ 表示 $(i,p_i)$ 向 $dir$ 方向延伸出的长度为 $j$ 的正方形（$dir\in\{0,1,2,3\}$），最多包含几个其它的正方形，直接转移还是比较困难，可能可以使用数据结构做到 $O(n^2\text{polylog})$，总之无法通过。 发现题目里还有随机排列的条件没有用，可以感受到随机排列的情况下能够选出的正方形不会太多，改成设 $f_{i,j,dir}$ 表示 $(i,p_i)$ 向 $dir$ 方向的正方形要包含 $j$ 个其它的正方形，最小的边长是多少，转移同样可以分类讨论变成二维偏序。一个结论就是 $j$ 这一维的大小是 $O(\sqrt n)$ 级别的，大概就是与随机排列的 LIS 长度是同阶的，所以这样就能做到 $O(n\sqrt n\log n)$，可以通过。 这里补充下具体怎么把转移写成二维偏序，假设我们现在要对 $f_{i,j,0}$ 进行转移，考虑之前 $j'=j-1$ 时的一个矩形 $x\in[l,r],y\in[d,u]$，那么首先要满足的条件就是 $i<l$ 且 $p_i<d$，转移过来后正方形的长度当 $d-p_i\le l-i$ 也就是 $d-l\le p_i-i$ 的时候是 $r-i$，否则是 $u-p_i$。注意到，如果满足 $i<l$ 那么当 $d-p_i> l-i$ 时就天然满足了 $p_i<d$，同理如果满足 $p_i<d$ 那么当 $d-p_i\le l-i$ 的时候也天然满足了 $i<l$，因此转移的贡献也是可以确定住的，跑两遍二维偏序即可。对于 $dir$ 为其它数的情况可以类似的讨论处理，这样对每层 $j$ 转移是跑八遍二维偏序，比较唐，但是我也不会其它更好的做法。 ### C 六百六十六。 俄罗斯方块很好玩，感谢帮助我消磨模拟赛的时间。 ## Day 2 数据删除。 神了，感觉这场不能接近 AK 就是螳臂。 ### A 手玩一下，用排列复合的语言写出来最后的结果，发现第一个排列会变成 $(ab)^{k_1}a$，第二个排列会变成 $(ba)^{k_2}b$，$k_1,k_2$ 都是好求的。 但是直接求 $k_1,k_2$ 太大了，没法快速幂。注意置换复合的过程中每个置换环是独立的，而置换环环长只有根号种，所以暴力维护对这根号个值取模后的指数即可。 复杂度 $O(q\sqrt n)$。 ### B 首先要观察到，所有合法的排列 $p$ 生成出来的难度序列全都长得一模一样。 从大到小枚举难度 $w$，设 $b_i$ 表示第 $i$ 行难度大于等于 $w$ 的题目数量，把所有行按照 $b_i$ 降序重排，找到最大的位置 $p$ 满足前 $p$ 行都能跨过对角线，则这些行一定对应难度 $\ge w$，其它行 $<w$，进一步地根据这个过程我们可以确定最后难度为 $w$ 的是哪几行。 考虑把每种 $w$ 对应的方案分开计算，当且仅当每种 $w$ 都是奇数种方案最后答案才是奇数。每种 $w$ 的方案把式子写出来后发现相当于算一小块矩形的积和式，模 $2$ 意义下就是行列式。一个重要性质是，每行的 $1$ 对应的是一段区间，其它位置都是 $0$，把每个区间连边 $l-1\to r$ 判断是不是树即可，复杂度 $O(nk)$。 ### C 超级宇宙无敌炫酷傻逼题。 枚举一个红点，找到左右最近的蓝点，和次近且不在同一子树的蓝点，发现只有这 $O(m)$ 个点对是有用的，扫描线一下即可，复杂度 $O(n\log n)$。 ### Day 3 $100+100+55=255$，为啥没 AK 来着？？ 这个 T1 感觉其实是略有难度的，想到最短路树后终于分析了出来。T2 没啥好说的，普普通通一道 dp 题。开到 T3 的时候想了十几分钟发现这是道绝世唐题啊？？先写了份把扩展和数据结构部分都用暴力实现的代码，但是很遗憾没有调过大样例/fn/fn。 ### A 考虑先求出一棵以 $n$ 为根的最短路树，则删边只会考虑删去最短路树上的边，否则没有任何意义。发现策略肯定是走到 $u$ 的时候选择一条 $u$ 的出边删去，所以尝试预处理 $g(u)$ 表示删去 $u$ 在最短路树上的父边之后 $u$ 到 $n$ 的最短路。此时的策略肯定是，$u$ 先走到子树内一个点，然后走一条非树边走到子树外，最后沿着树边爬到 $n$。 枚举一条非树边 $x\to y$，发现相当于对 $x\to\text{LCA}(x,y)$ 路径上的 $g(u)$ 做一个 chkmax 的操作，逆用 ST 表即可做到 $O(n\log n)$ 求出所有的 $g(u)$。此时考虑二分答案 $mid$，check 考虑直接模拟走的过程，从 $1$ 出发 BFS，走到一个 $dis_i+g(i)>mid$ 的点 $i$ 就不合法，判断能不能走到 $n$ 即可，复杂度 $O(n\log n)$。 ### B 把区间按照包含关系建树。分析一下一个点最后的区间会怎么选择，发现只有：放在两边，放在某两个儿子之间的空隙里，扔到子树里这几种选择。而对于一段连续的区间，我们并不关心里面的所有端点，只需要给最靠左区间的左端点记一个负贡献，最靠右区间的右端点记一个正贡献即可，这样拆开贡献方便我们后续 dp。 考虑设 $f_{u,i,0/1,0/1}$ 表示考虑了 $u$ 的子树，当前从祖先传下来了 $i$ 个区间没用，左右两侧是否有没封住的区间的最大贡献，转移顺次合并子树讨论下就好了。注意下 $i$ 这一维的范围，显然一棵子树 $u$ 内最多有 $2siz_u$ 个不同的段，传下来 $2siz_u$ 个区间后肯定能填满，所以这一维的范围限制是对的，最后的复杂度就是树背包的 $O(n^2)$。 ### C 怎么又他妈在 T3 放弱智题，急眼了。 考虑什么情况下答案会变大，发现就是我们操作了一个回文串中心一侧的区间，导致了匹配长度的增大。考虑枚举开始的回文中心然后扩展，这里分为三段： - 开始的回文半径，这里不操作就可以贡献到答案。 - 将一侧字符 shift 之后可能可以再继续扩展，这里会在左右侧各得到一个能给询问贡献的极长区间 $[l_1,r_1]$ 和 $[l_2,r_2]$，当询问区间包含了 $r_1/l_2$ 且没包含 $l_1/r_2$ 的时候会有一个随询问区间端点线性增长的贡献。 - shift 操作扩展完之后，可能再新接一段能继续扩展的长度，这相当于如果询问完全包含了上面的两个极长区间之一时还有一个常数长度的贡献。 由此有用的区间一共就 $O(n)$ 个，对询问的贡献扫描线后都可以简单数据结构处理，容易做到 $O(n\log n)$。 场上留了快两个小时做这题还没写完是不是可以跳了？？ ## Day 4 $100+100+0=200$，完全不会做 T3。 T3 的第一个包看上去是类欧，我咋会这东西啊，遂没写，结果他数据造小了可以暴力计算通过。 ### A 考虑一棵树合法的充要条件，发现就是每个点的儿子至多有一个没有洞。然后就随便做了，场上乱写了个 dp 调了好久，一个稍微聪明一点的做法是考虑一条长度为 $L$ 的白链对答案贡献是 $\frac{L(L+1)}{2}$，我们可以直接拆成求所有链作为白链出现的概率之和。 复杂度 $O(n\log p)$ 或 $O(n)$。 ### B 考虑一条路径 $p_1,p_2,\ldots,p_k$ 能走完的条件，根据题目的定义发现是 $\forall i<k,\sum(w_i-a_{p_i})\le t$，其中 $w_i$ 是路径上第 $i$ 条边的边权。 如果没有 ban 掉一个点的限制，考虑直接点分治，处理跨过分治中心的所有贡献。每层分治用一次 dfs 处理出来每个点向上走到分治中心的 $w-a$ 前缀和的最大值（用来判断能不能走到分治中心），以及分治中心走下来的前缀和最大值。对于一个挂了询问的点，如果这个点能走到分治中心，写出其它点能贡献到询问的条件发现是一维偏序，随便选个方法统计即可。 做到这里发现 ban 掉一个点纯诈骗啊，这相当于是限制只能走 dfs 序上至多两个区间的点，那上面点分治处理的时候加一维变成二维偏序就好了，复杂度 $O(n\log^2 n)$。 ### C 这我哪会。 ## Day 5 $100+20+8=128$，唐。 T1 看完题我就说，哦这不是动态树重心吗！！lxl 放过这种题，我还特意补了！！然后我就真的套了那个求 dfs 序中位数倍增找重心的那个东西/xk/xk/xk。 T2 开的时候感觉是我要先按照边权加边，边权和记入状态里会爆炸，但是看上去可以插值处理掉。结果写连通性的 dp 时转移系数推错了，赛后发现是我钦定了连通块按照 siz 顺序加入，我他妈在干嘛？？？ T3 没开。 ### A 场上直接套了动态带权重心，写了依托！！！ std 的简单做法是，我们根本不关心重心在哪，因为到重心的贡献拆到边上就是两端点权和的 $\min$！！维护这个考虑求出子树内和子树外的一次函数和，求出交点到时候就 swap 哪边大即可。因为修改改的是相邻的点，所以问题不大，可以简单实现到 $O(n\log n)$。 ### B 考虑 Kruskal 求 MST 的过程，我们要干的事情大概就是从小到大枚举边权加入，然后维护出当前的连通性。可以设计出的状态是，$f_{w,i,s}$ 表示当前加入了边权 $\le w$ 的边，$1$ 所在的连通块大小为 $i$，且 MST 的边权和为 $s$ 的概率。 转移时，参考图连通性容斥做个类似 exp 的过程。定义辅助数组 $g_{w,i,s}$，表示考虑当前边权 $w-1\to w$，在不考虑连边是否合法的情况下当前合并了 $i$ 个点，边权和为 $s$ 的概率，枚举 $1$ 所在连通块大小容斥转移即可，连边的系数是边权 $\ge w$ 或者为 $0$ 即可。考虑求 $f_{w,i,s}$，初始令其值为 $g_{w,i,s}$，同样再枚举 $1$ 所在连通块大小减去不合法的连边方案即可。 现在的复杂度大概是 $O(n^4m^3)$ 的，好像场上好多人写这个通过了。正解的方向是，边权和这维导致了状态数非常爆炸，但注意到如果把这一维写成多项式，每次转移就是卷一下然后乘 $x^w$。代入 $x=0,1,\ldots,(n-1)m$ 为点值各跑一遍 dp，拉插还原系数即可。 复杂度大概是 $O(n^3m^2)$。 ### C 不会。 ### Day 6 $100+100+0=200$，还可以。 认真想了一会 T2 通过了，但是 T3 有个纯糖的暴力给了 $48$ 分，不是哥们为啥喜欢这么给部分分啊？？ ### A 先枚举一个数 $t$ 并计算 $\max\le t$ 的方案。我们考虑从下往上判断每棵子树是否合法，发现一件事情就是每棵子树问题是独立的，也就是判断一棵子树的时候可以认为子树内的时间是连续的，合并两个儿子的子树就是一个归并的过程。 对这个归并过程的限制相当于已经插入的点里来自左儿子的数量减去来自右儿子的数量时刻在 $[-t,t]$ 之间，显然这是个反射容斥问题，使用经典的钦定对称做法，可以做到 $O(n^2\log n)$。下一步优化很糖，就是你发现每个点只会对 $O(\min(siz_{ls},siz_{rs}))$ 个 $t$ 产生贡献，所以限定下每个点跑反射容斥的次数就能做到 $O(n\log^2 n)$ 了。 ### B 交换下求和号，枚举每个 $T_i$，问题变为统计有多少对 $(j,k)$ 满足 $S_j$ 和 $S_k$ 能拼出来 $T_i$。枚举下 $T_i$ 的一个分割点，那么能从这个分割点拼起来的 $j,k$ 分别来自对每个 $T_i$ 的正反串建 AC 自动机后 fail 树的一个子树，分别求出 dfs 序后以这两维建系就对应了一个矩形，求出 $T_i$ 的所有矩形跑矩形面积并即可。复杂度 $O(L\log L)$，其中 $L$ 表示总串长。 ### C 看懂题解了，但是这题也太神秘了。 ## Day 7 $100+28+25=153$，打得很一般啊。 T1 脑子比较混乱，不知道为啥三个小时才过。T2 一直在读错题，懒得喷，导致 T3 糖题没啥时间去做了。 ### A 直接分类讨论两条树边的关系。首先如果是祖孙关系，一定会选择一个点的父亲边和连向儿子的一条边，是个显然的调整，可以 dfs 一遍 $O(n)$ 判断。 否则，假设删去的两条树边是 $x,y$ 的父亲边，设 $s_x$ 为 $x$ 子树内的非树边个数，则答案为 $s_x+s_y-2cnt(x,y)$，$cnt(x,y)$ 表示两个端点分别在 $x,y$ 两棵子树内的非树边数量。这种形式很容易想到线段树合并，也就是把树拍到 dfs 序上用线段树维护每个 $y$ 对应的 $s_y-2cnt(x,y)$，把儿子的线段树继承过来然后加入自己连出去的非树边，加一条非树边相当于做链减 $2$。稍微实现一下就是 $O(n\log^2 n)$ 的了。 ### B 困难。 ### C 真是糖完了。 考虑一个固定的最终局面该用什么样的操作去染。首先如果有全黑的列，我们可以直接把这列整体染黑，显然对别的列没有任何影响。否则考虑其它黑色的点，它所在的唯一斜线必须全部被染黑。 那现在能编出来一个简单暴力，枚举一下每列是否全部被染黑，接下来只需要算选斜线的方案。发现对选斜线的限制就是不能有不是全黑的列被斜线染成全黑，而一列相当于是限制一段区间内的斜线不能被全染，所以是容易计算的。你发现这个限制其实很简单啊，我们直接对着全黑的列 DP，记一下上一条选的斜线是哪条，随便优化一下就能做到 $O(n^3)$ 了。 ## Day 8 $70+75+32=177$，但是大家全都 $200+$ 所以掉分了/ll/ll。 感觉前两题都应该直接通过的啊，怎么回事。 ### A 有点邪恶。 $70$ 分的 $O(n\log p)$ 是纯送的，考虑如何计算一个排列的权值，求出 $c_i$ 表示第 $i$ 个位置前面有几个大于它的，答案就是 $\frac{\sum c_i}{\max c_i}$。显然 $c$ 数组和排列是双射，改为对 $c$ 数组计数，对每个 $t\le k$ 求出 $\max c_i\le t$ 的 $c_i$ 和即可统计答案。 但是这题出题人 intended 是线性的，去网上贺一个线性筛求所有 $i^i$ 就好了/qd，赛时没继续看这题。 ### B 怎么和一轮撞题了？？那我怎么还没过？？ 第一步和之前是一样的，非树边的 $l$ 和树上路径的 $l+1$ 做 chkmax，树边的 $r$ 和覆盖它的非树边的 $r-1$ 做 chkmin，这样就能保证满足 MST 的限制。 要求字典序最小肯定是按位确定了，暴力确定每次贪心 check 是 $O(n^3\log n)$ 的，然后接下来有两个优化方向： - 优化按位确定的复杂度，你发现当前这个数的区间越长越容易有解，所以你可以二分一下限定住 $r$ 的范围，然后贪心部分换成并查集优化下，复杂度 $O(n^2\log n\alpha)$，已经能过了。 - 优化 check 的复杂度，现在的问题形如判断完美匹配的存在性，自然考虑 Hall 定理。左部点是区间，右部点是单点，稍微分析下就能得到 $N(S)$ 一定是区间，那合法当且仅当每个 $[L,R]$，都有 $[L,R]$ 包含的区间数量减去 $R-L+1$ 不为正。扫描线一下用线段树维护，简单判一判就能做到 $O(n\log n)$ 求一位填啥了，最后是 $O(n^2\log n)$ 的。 两种做法明明都是弱智啊？？？为啥我没过这题？？ ### C 混乱邪恶的东西。