25.05-二轮省集模拟赛题解

· · 题解

由于水平有限，只补了一部分题，因此只有这部分题解。

D0T1 A

题意

给定无向连通图，求有多少种加边方案使得最终的图无重边、自环，且边双连通。取模。n\le 5000,m\le 10^6。

题解

边双连通即为不存在割边，因此先 Tarjan 跑出原图的边双连通分量并缩点，得到一棵由割边连接的树。此时边双内部的边可以任意添加，最后给答案乘上 2^{cnt} 即可。问题转化为给新树加边，要求每条树边均被某条新边 (u,v) 所对应的树上路径 u\to v 覆盖，求方案数。注意此时每个新点内部有 w_i 个点可向外连边，w_i 为该边双的点数。

考虑容斥，枚举没被覆盖的边数 i，设方案数为 g_i，答案即为 \sum (-1)^i f_i。注意到钦定若干条边不覆盖后，整棵树被分成了若干连通块，每个连通块内可以任意连边，因此树形 DP 计数。最朴素的 DP 状态为 f_{u,j,k} 表示 u 子树内断了 j 条边，u 所在连通块大小为 k 的方案数，转移类似树形背包。时空复杂度 O(n^3)。

但是注意到多断一条边时，容斥系数只会取反，而具体有多少条边并不重要。所以可以去掉边数一维，并将容斥系数加入 DP 值转移。具体地，设 f_{u,i} 表示 u 子树内 u 所在连通块大小为 i 时，子树内带容斥系数的方案数总和。初值为 f_{u,w_u}=1，转移时将子树 f_v 合并到 f_u，若断边则 f_{u,i}\leftarrow -\sum f_{v,j}，容斥系数取反，点数不变；不断边则 f_{u,i}\leftarrow f_{u,i-j}\times f_{v,j}\times 2^{j(i-j)-1}，即 u,v 两点间除树边外的所有边状态任意。树形背包转移即可，注意上下界优化，时空复杂度 O(n^2+m)。

D0T2 B

题意

给定一张 DAG，每条边是黑色或白色，q 次询问当黑白边权分别为 a,b 时，1\to x 的最短路长度。n,q\le 5\times 10^4,m\le 10^5。

题解

考虑处理出 1 到每个点的所有可能的 (x,y)，其中 x,y 分别表示经过的黑白边数，询问时在每个点上枚举。若对每个 x 保留最小的 y，复杂度为 O((n+m+q)n)。

然而注意到若把所有 (x,y) 放到坐标系内，则可能成为最优解的 (x,y) 一定在下凸包上。又有据说经典的 Trick，两维值域均为 [1,n] 内整数的凸包点数至多为 n^{\frac 23}，因此在每个点上维护凸包，转移时暴力合并。如果建凸包时使用快排的话，复杂度为 O(n^{\frac 53}\log n+(q+m)n^\frac23)，然而远卡不满，容易通过。

D0T3 C

题意

定义序列的权值为通过邻项交换使其变为单峰序列的最少操作次数。给定排列 a，求 a 每个前缀的权值。n\le5\times 10^5。

题解

先考虑单个序列的权值求法。首先关注最小值，其一定会被放在序列开头或结尾，同时归位后其余元素相对顺序不变。因此放在两处都会得到长度减少 1 的子问题，对每个值依次求贡献即可。最终答案为 \sum_{i=1}^n\min(\sum_{j<i}[a_j>a_i],\sum_{j>i}[a_j>a_i])。

对每个前缀求解时，仍然考虑计算每个数的贡献。对于 a_i，前面的 \sum_{j<i}[a_j>a_i]=c_i 始终不变，后一个数单调不降，讨论二者大小关系即可。具体地，在 \sum_{j>i}[a_j>a_i]\in[0,c_i) 时若在末尾加入一个大于 a_i 的数，则贡献加 1；不小于 c_i 时贡献一直为 c_i，不再改变。因此找到 a_i 之后第 c_i 个大于 a_i 的数 a_{p_i}，则 (i,p_i] 内每次加入一个大于 a_i 的数都会使答案加 1。

具体实现上先使用 BIT 求出 c_i，然后按 a 的值从大到小排序，用权值线段树上二分求出对应的 p_i。最后增量维护答案，用 BIT 维护目前贡献还在增加的所有 a_i，长度增大时查询小于加入值的个数并加入答案，在对应的 a_{p_i} 加入后从 BIT 中删除即可。时间复杂度 O(n\log n)。

D1T1 花卉港湾

题意

给定一棵树，建一张新图，给所有原树上距离不低于 k 的点对间连边，q 次询问新图上 u,v 两点间的最短路。n,q\le 10^5,1\le k<n。

题解

首先若 d(u,v)\ge k，答案为 1。再分别找到距离 u,v 最远的点 p,q，根据直径的性质可知 p,q 均为直径端点。因此直接找出一条直径 L\to R 用于判断。此时若 u,v 中有一点无法到达直径端点，或直径长度不足 k，答案为 -1。否则一定能通过直径在 3 步之内抵达，答案至多为 3。

之后只要解决答案为 2 的判断就做完了。首先若有一个直径端点到 u,v 距离均不低于 k，则可以其为中转点两步抵达。之后设 p_i 表示直径上距离 i 最近的点，d_i 表示该距离，w_x 表示 \max_{p_i=x}d_x，也即直径上的 x 点子树内的最远距离。令 p_u\le p_v，则只有 p_u<p_i<p_v 的点 i 作为中转点时可能比两个直径端点优，根据直径的性质容易证明。此时要求 x=p_i 满足 x-p_u+w_x+d_u\ge k,p_v-x+w_x+d_v\ge k，整理得 w_x+x\ge k+p_u-d_u,w_x-x\ge k-p_v-d_v，再加上 p_u<x<p_v，是三维偏序问题。

这样已经可以随便上点东西维护了，但是分讨一下可注意到若 x 不满足 p_u<x<p_v，却满足另外两个限制，则某个直径端点一定能作为中转点，因此这个限制可以忽略。同时由于每个点都能贡献到每个询问，且只关心是否存在，而不关心具体个数，可在所有查询前用下标为 w_x+x 的数组记录下对应的 \max(w_x-x)，并预处理出后缀最大值，查询可以做到 O(1)。时间复杂度为 O(n\log n)，来自求两点距离时的 LCA，因此用科技可以做到线性。

D2T1 MEX 求和

题意

给定非负序列 b，求 \sum_{\forall i\in[1,n],a_i\in [0,b_i]}w(a)，其中 w(a) 表示 a 数组的 MEX 值。n\le 5000,b_i\le {10}^9。

题解

考虑将 MEX 值拆成 \sum_{i=0}^{n-1} f(x)，其中 f(x) 为 1 表示 a 中存在 [0,x] 中的所有数，问题变为每个 f(x) 能贡献的方案数。考虑先将 b 从小到大排序，之后设 f_{i,j} 表示填了前 i 个数，此时不大于 b_i 的数中还有 j 个需要存在却还没有的方案数。那么从 f_{i-1} 转移到 f_{i} 时，又会多出 m_i=\max(0,\min(a_i,x)-a_{i-1}) 个数需要填，转移为 f_{i,j+m_i}\leftarrow f_{i-1,j}\times (b_i-(j+m_i)) 和 f_{i,j+m_i-1}\leftarrow f_{i-1,j}\times (j+m_i)，分别表示是否新填了一个需要填的数，总时间复杂度 O(n^3)。

这个状态的 j 维含义比较抽象，因为这是赛时更换状态以图优化的结果。此时注意到可以分讨 a_i 和 x 的大小关系来确定 m 的取值，即若 a_i<x，则 m_i=a_i-a_{i-1}；否则 m_i=\max(0,x-a_{i-1})，再分讨若 a_{i-1}>x，则 m_i=0，否则 m_i=x-a_{i-1}。注意到 a_{i-1}<x<a_i 的位置只有一个，而其他情况下 m_i 均与 k 无关，因此用前后缀的 DP 数组预处理转移系数，每枚举一个 x 暴力进行中间一个位置的转移即可，时空复杂度 O(n^2)。

D3T1 重建：地下铁道

题意

给定 n 个点的环，每条边有长度，可任意定向。m 个任务要求沿着边的方向从 s_i 走到 t_i，代价为 w_iL，L 为路径长度。求最小总代价。n,m\le 5\times 10^5。

题解

考虑先钦定 (1,n) 之间边的方向，这里令其为 n\to 1，则 s_i<t_i 的任务方向固定。对于 s_i>t_i 的任务，先令其经过 n\to 1 的边，考虑选择其中一些反向以最小化代价。首先若与 s_i<t_i 的任务有相交的边，则一定不能反向。又注意到若有 s_x>t_x 的任务不反向，则只有 s_x\le s_i<t_i\le t_x 的任务 (s_i,t_i) 才能反向。因此若有长为 L 的任务未反向，则长度不低于 L 的任务一定无法反向。这也说明将可反向的任务按长度排序，最终选择反向的一定是一段前缀中的任务。

因此排序后维护前缀所有任务 [t_i,s_i] 的并，要求对应后缀所有任务的交包含该区间，对每个合法前缀求最小值即为答案。至于再钦定 1\to n 时计算方式相同，可以将所有边和任务反过来，即将 w 的 [1,n-1] 翻转，每个任务变为 (n-s_i+1,n-t_i+1)，重做一遍即为 1\to n 的答案。时间复杂度为 O(m\log m)，来自对区间进行排序，用桶排可以做到线性。

D4T1 崩坏世界的歌姬

题意

给定整数 n,m，计算有多少长为 n 的排列满足任意相邻位置之和均不为 m 或 m+1。n\le 10^9,m\le 10^7，其中 80\% 满足 m\le 3000。

题解（80 分）

注意到将所有不能相邻的数之间连边后，[1,m] 的数连成了一条链。因此想到先将 m 个数排好，再向其中插入剩余的 (n-m) 个数。注意到排完 m 个数后，只关心中间的 (m-1) 个空是否合法，从而确定每个空中是否可空，从而用插板法计算出方案数。因此只需要对所有 j\in[0,m) 求填完后有 j 个非法相邻的方案数。

考虑用 DP 解决该问题，设 f_{i,j,0/1} 表示填了前 i 个数，有 j 个非法相邻，其中是否包含 i 和 i-1 的方案数。转移时分讨插入了 i 和 i-1 之间/合法空/非法空，乘上对应的个数转移即可，此处略去。算出 g_{j}=f_{m,j,0}+f_{m,j,1} 后，即需要向 (m+1) 个空中插入 (n-m) 个数，其中 j 个不可空，得到方案数为 {n-x}\choose m，还要乘上 (n-m)!，得到答案为 \sum_{x=0}^{\min(m-1,n-m)}g_x\times \frac{(n-x)!(n-m)!}{m!(n-x-m)!}。

另外需要求 (n-i)!，其中 n\le 10^9,i\le 6000，只能使用分块打表预处理出这些阶乘的值。总时间复杂度 O(P+m^2)，P 是分的块长。另外本题还有 20 分分别为 m\le 10^5 和 m\le 10^7，分别是多项式优化和数学推递推式，不是很懂，不管了。

D4T3 每个人的结局

题意

给定平面内 n 个矩形，可在平面内随意放三个点，w_i 可以取 x 当且仅当第 x 个点在第 i 个矩形内，求合法的 w 序列数量。1\le lx_i,rx_i,ly_i,ry_i\le n\le 2\times 10^5，其中 15\% 满足 \max \{lx_i\}\le \min\{rx_i\} 或 \max \{ly_i\}\le\max \{ry_i\}。

题解（15 分）

注意到 15\% 的特殊性质中有一维没用，因为只要将点放在 [\max \{l\},\min\{r\}] 内，就能满足所有矩形这一维的限制。 所以变成了一维问题，即只有 [l_i,r_i] 内包含第 x 个点，w_i 才能取 x。考虑找到右端点最小的区间和左端点最大的区间，设最小右端点为 p，最大左端点为 q。若这两个区间有交，即 p\ge q，则存在点被所有区间包含，答案为 3^n；否则两个区间的值一定不同，我们令其分别为 1,2，最终答案乘上 6 即可。

注意到 1,2 分别放在 p,q 能在合法前提下覆盖到最多的区间，然后将 3 放到 (p,q) 开区间内 pos 处。考虑每个区间的取值。设其能覆盖 p,q 中 k 个点，则若 l_i\le pos\le r_i，该区间有 (k+1) 种取值，否则有 k 种取值。 此时计算每个点作为 pos 时的方案数：若 k=0，将区间外赋成 0；若 k=1，给区间内乘上 2；若 k=2，给区间内乘上 3，此时由于区间外一定在 (p,q) 外，可以不用管。

再考虑统计最终答案，考虑使用类似点边容斥的 Trick，即对于某种方案有一段区间的点合法，则用这段区间的点数减去边数得到 1 的系数。因此把点和边作为线段树下标，维护区间乘操作，最后求所有数带系数的和即为答案。时间复杂度 O(n\log n)。

至于满分做法需要在二维上钦定 1,2 在两个角上后分讨 3 的位置，再进行点边块容斥，扫描线维护。有点太复杂了，摆了，但感觉思路很有参考价值，故记录。

D5T1 互质序列

题意

给定 n，长为 m 的合法序列要求 a_i\mid n，且相邻两数均不互质。q 次询问长为 m 的合法序列数量。 n\le 10^{16},m\le 10^{18},q\le 150。

题解

先将 n 分解质因数，并求出其所有因数，若暴力则可以设 f_{i,j} 表示填了 i 个数，最后一个数为 j 的方案数。若 j 有 V 种取值，则暴力转移复杂度为 O(mV)，矩阵快速幂优化复杂度为 O(q\log m V^3)，直接把所有因数放到 j 上则有 V_1=d(n)。考虑优化 V 的大小以降低复杂度，首先注意到每个质因子的个数不重要，只关心是否存在，因此可以压成 01 串，做到 V_2=2^{w(n)}，其中 w(n) 表示 n 的质因子数量。

再注意到若把 01 串所有质因子在 n 的分解中最高次项取出来构成可重集，则若两个 01 串 x,y 对应的可重集相同，则 \forall i,f_{i,x}=f_{i,y}，因为这两个状态本质上是等价的。由此可以进一步压缩状态，用 V_2 个状态预处理一下转移系数，最终得到 V_3\le 250，具体多少不清楚。

好像复杂度有点大，但是多次询问矩阵快速幂有经典优化，即先预处理出转移矩阵所有的 2^k 次方矩阵，每次询问进行 O(\log m) 次向量乘矩阵即可。最终复杂度为 O(V_3^3\log m+qV_3^2\log m)，可以通过。

D5T2 树的搜索

题意

设 f(x,y) 表示从树上 x 点开始，只向儿子方向随机 DFS（即每次在未访问过的儿子中等概率随机一个访问），访问到 y 时经过的点权最小值的期望值，要求 x 是 y 的祖先。给定一棵树，求所有合法 (x,y) 的 f(x,y) 之和。n\le 5\times 10^5,a_i\le 10^9。

题解

原题是 P8334，这是题解。

D6T1 构造题

题意

设 f_{i,j} 表示从 (1,1) 走到 (i,j) 的路径数，要求在网格中选择一些位置标记为可通过，再选择若干可通过的格，使得它们的 f 值之和为给定的 k。q 次询问，要求所有询问使用相同的标记网格，标记的格数不超过 X，每次选择的格数不超过 Y。q\le 10^4,X\ge 960,Y\ge 240,k\le 10^{100}。

题解

先考虑使用二进制来刻画每一位，发现精细实现也需要构造到 2^{330}，即需要 993 个格才能满足题意。尝试 3,5 进制后发现均不如二进制优，但需要选择的格数变少了，可以通过一些部分分。

注意到使用其他进制时，960 格的总和都难以达到 10^{100}。因此考虑先将总和达到上界，发现斐波那契数列增长较快，并且可以用两格的代价变为下一项。计算一下发现 f_{480} 恰好能达到 9\times 10^{99}，总和已经可以达到上界。另外又有定理为每个自然数均能唯一地被互不相邻的若干项斐波那契数之和表示，赛时感性理解也想到了这一点，因此标记格数为 \log_{\phi}k，所选格数不超过 \frac{\log_{\phi}k}2，均满足要求。时间复杂度在高精度加法，需要使用压位高精。

D6T2 匹配题

题意

给定长为 n 的字符串 S，要求从中删掉 k 个位置，并将剩下的位置两两匹配，i,j 匹配要求 S_i\ne S_j，代价为 100\times\left|i-j\right|+w_i+w_j。求匹配总代价最小值，若无合法匹配则输出 -1。多测，T\le5,n\le 2000,k\le 6,w_i\le 10^5,S_i\in\{a,b,c,d,e,f\},n\equiv k\pmod 2。

题解

考虑枚举分界点 p，将整个串分为 [1,p],[p+1,n] 两部分，注意到两部分可以内部匹配，直到其中至少有一部分剩余字符全部相同。证明可以考虑调整，即若目前两边均剩余了超过一种字符，则找到在单侧数量最多的一种字符，令该侧最多和次多匹配一个，一定不会影响匹配的合法性。同时考虑到这样减少了跨过分界点的匹配数量，一定比不匹配优。

因此对于每个前缀，匹配后剩余的字符要么是同一种，要么会与之后的同一种字符匹配。据此设计 DP 状态 f_{i,j,k,c,0/1} 表示考虑了长为 i 的前缀，剩余 j 个字符，删了 k 个字符，剩余字符均为 c 或均与后面的 c 匹配的最小代价，需要将匹配代价拆到两个字符处以方便转移，即 i<j 时 i 处有 w_i-100i 的代价，j 处有 w_j+100j 的代价。

转移讨论向前或向后匹配，根据 S_i 是否为 c 转移即可。需要格外注意的是 0 状态可以在任意情况下直接转到 d\ne c 的 f_{i,j,k,d,1}，而变为 0 状态则需要 j=0。转移式此处略去，时间复杂度 O(Tn^2kV^2)，优化一下也可以做到 O(Tn^2kV)，其中 V 为字符集大小。使用滚动数组优化后空间复杂度为 O(nkV)。

D7T1 宿雾若水遥

题意

给定一棵 n 个点的树和 m 条树上的链，q 次询问给出 L,R，求 \sum_{L\le l\le r\le R} w(l,r)，其中 w(l,r) 表示第 l 条链到第 r 条链的并集大小。n,m\le 2\times 10^5,q\le 5\times 10^5。

题解

考虑把贡献拆到每个点上，枚举点 x，找到其在链中出现的所有位置，则所有相邻两次出现 p,q 之间的区间 [p+1,q-1] 的子区间中均没有 x。若以 l,r 为两维建立坐标系，则做矩形加即可处理此类贡献，最终答案用总点数 n 乘上区间个数，再减去 [L,R] 所对应的矩形和即为答案。

赛时不会矩形求和，因此想出了分讨修改和询问区间关系的做法。具体地，若贡献区间为 [s,t]，询问区间为 [L,R]，分讨一下四个端点的大小关系可以得到修改对询问的总贡献量。这里有两个式子分别是和 L,R 有关的二次函数，因此需要开多个树状数组分别记录系数，还需要记录另外两种的贡献和和贡献次数，使用六棵树状数组维护扫描线即可，具体推导过程此处略去。

该做法复杂度高的原因是每个点会在多个链中出现，导致矩形加的次数太多。考虑减少矩形加的个数，先从链的情况入手，这时发现若从链头到链尾枚举点 x，则某条链中出现点 x 的 x 是一段区间，也即每条链只会出现一次，消失一次。因此总变化量为 O(m)，所以本质不同的 [p+1,q-1] 只有 O(m) 个，使用 set 动态维护目前空位的连续段，区间加带上消失和出现的时间戳之差，即贡献的次数作为系数即可。

考虑把上面的做法拓展到树上，直接将整棵树重链剖分，并把每条链拆成若干条重链，这样每条链在 DFS 序上就是连续的了。此时按照 DFS 序枚举点算贡献，再将所得的 (s,t,x) 中的端点 s,t 转化回原链序列的左右端点，同样扫描线计算答案即可。

时间复杂度 O(m\log n\log (m\log n)+m\log n\log m+q\log q+q\log m)，其中所有的 m\log n 均为转化后的重链条数，分别是 set 维护连续段、修改、对查询排序和查询的复杂度。这里 set 常数大，修改查询有六棵树状数组，常数也大，但是树剖常数小，可以通过。空间复杂度 O(m\log n\log m)，记录扫描线时的修改，实际测试时空间甚至比时间更紧一些。

D7T2 缠忆君影梦相见

题意

给定一张无重边自环的有向图，求有多少种删掉三条边的方案使得新图不强连通。多测，T\le 10,n\le 50,m\le n(n-1)。

题解

考虑把强连通转化为 1 和其他每个点均互相可达，这个条件是充要的。因此可以通过原图和反图分别 BFS 一遍来判断是否强连通，用压位可以做到 O(\frac{n^2}w)，由于本题 n\le 50，可以用 long long 做到等价于 O(n) 的复杂度。

通过上面的判断方式，我们注意到若原图和反图的 BFS 树没有改变，则连通性也不会改变。因此考虑直接跑出 BFS 树，只枚举这些边被删，枚举量就降到了 O(n)。具体实现时设 f_{E,k} 表示在 E 边集中删掉 k 条边的方案数，若不连通则为 {\left|E\right|}\choose k，否则枚举跑出的 BFS 树边删去，递归到 f_{E-e,k-1}，写代码时打标记和统计方案数有一些细节，时间复杂度 O(\frac {n^5}w)，本题中即为 O(n^4)。