专题题解 - PKU&THUSC 2023
PKUSC D1
T1：
题目大意：
给定 $S,T$，对于每个 $i$ 求 $S_i$ 换为 $T_i$ 后 $S$ 的最长 Border。
$|S|,|T|\leq 10^6$
题解：
枚举后缀 $Suf=S[|S|-i+1:]$，对应的前缀 $Pre=S[:i]$，如果 $Suf$ 和 $Pre$ 有三位不同那么显然不可能通过替换一位变得相等，如果有两位不同那么一定是替换重叠的那一位才有可能相等，如果是一位不同就是替换不同的那一位。当然要特判一下 $S_i=T_i$。
$O(|S|)$
T2：
题目大意：
有 $n$ 个人，第 $m$ 个人是狼人，其余随机一个人是预言家，预言家每天随机一个区间 $[l,r]$ 并知道其中有没有狼，求期望几天确定狼的位置。
$n\leq 150$
题解：
枚举一个包含 $m$ 但不包含预言家的子集 $S$，算钦定 $S$ 里的人都不能确定是不是狼人的期望天数。称 $S$ 的元素是黑的，此时发现预言家可以问的区间只有全白的区间，或包含所有黑点的区间，设一次询问问到这些区间的概率是 $p(S)$，将 $(-1)^{|S|+1}\times \dfrac{1}{1-p(S)}$ 求和即可。
设白色连续段的长度依次为 $w_1,\ldots,w_t$，则发现 $p(S)\times f(n)=\left(\sum f(w_i)\right)+(w_1+1)(w_t+1)$，其中 $f(x)=\dfrac{x(x+1)}{2}$。
我们发现 $f(w_1)+f(w_t)+(w_1+1)(w_t+1)=f(w_1+w_t+1)$，于是这等价于将 $n$ 个人排成一个环，但是第一个人和第 $n$ 个人之间额外加一个明好人，然后求对于每种染黑的方案，白色段长度的 $f$ 和。从 $m$ 开始做个 DP，设 $f(i,j)$ 表示当前考虑到了 $i$，$f$ 和为 $j$ 的概率即可。可以额外记录一个 0/1 表示预言家有没有选出来了。
$O(n^4)$
T3：
题目大意：
给定一个 $n$ 个结点，非叶结点都有偶数个儿子的树，每个点的权值有 $p_i$ 的概率为 $1$，还有 $1-p_i$ 概率为 $0$，选完权值之后从下到上每个点的权值修改为自己和儿子权值的众数。支持 $q$ 次操作：单点 $p_i$ 修改，求根最后是 $1$ 的概率。
$n\leq 2\times 10^5$，$q$ 更小一点
题解：
没有修改时，我们要在每个点做个分治 NTT，具体来说每个儿子是个一次多项式，要算全乘起来后次数小于等于 $d/2$ 和大于 $d/2$ 的系数和。
考虑某一个点的修改（即可以看成一个菊花图的子问题），考虑线段树分治，后面是转置原理先鸽了。
然后一般树上就套个动态 DP 就行了。
$O(n\log^2 n+q\log^3 n)$
PKUSC D2
T1：
题目大意：
给定一个长度为 $n$ 的序列，有 $q$ 次操作：在序列中某个数 $x$ 之后插入一个数 $y$；将之前某次操作的 $x$ 修改为另一个数；求某个数 $x$ 现在排在序列里第几个位置。
常识范围。
题解：
对于插入操作，将 $y$ 的父亲设为 $x$，这将构成一个树结构。我们要支持子树移植和查询排名，套用 ETT 即可。
注意儿子有顺序，可以用 set 按插入时间维护每个点的儿子集合，子树移植时在 set 里二分到要插入的位置。
$O((n+q)\log (n+q))$
T2：
题目大意：
有 $n$ 个点集 $S_1,\ldots,S_n$，所有点在第一象限内且横纵坐标不超过 $V$，有 $q$ 次询问（$q$ 很小），每次给定 $A,B$，你要从每个 $S_i$ 里选一个点，设所有选出的点的横纵坐标和分别为 $X,Y$，求 $(A+X)(B+Y)$ 的最大值，允许答案 $\dfrac{V^2}{4}$ 的误差。
$n\leq 50000, q\leq 10, |S_i|\leq 10$
题解：
求出所有 $(X,Y)$ 的凸包，每次询问只从凸包上的 $(X,Y)$ 中选出一个最优的即可。求凸包使用 Minkowski 和即可。
证明考虑下图：
设 $(x,y+a)$ 和 $(x+b,y)$ 是凸包上相邻两个点，则 $a,b\leq V$，只要证明其连线上任意一点的横纵坐标积不超过 $\max(x(y+a),(x+b)y)+\dfrac{V^2}{4}$ 即可。
不妨设其连线上一个点为 $(x+c,y+d)$，则 $c+d\leq V$。并且根据一次函数的单调性有 $cy+xd\leq \max(xa,by)$，所以 $(x+c)(y+d)=xy+(dx+cy)+cd\leq xy+\max(ax,by)+\dfrac{V^2}{4}=\max(x(y+a),(x+b)y)+\dfrac{V^2}{4}$。
$O(\sum |S_i|(q+\log |S_i|))$
T3：
题目大意：
有一个未知数 $x$，给定五个方程，第 $i$ 个方程形如：
其中 $P$ 是固定的大素数。每个方程的 $a_i,b_i$ 分别在对应范围内随机。
请解方程，保证在 $[1,p-1]$ 中有唯一整数解。
$a_i\in [1,p-1], b_i\in [1,100], P\in [9\times 10^{17},10^{18}]$
题解：
注意到：
所以：
因此满足条件的 $x$ 只有不超过 $100\sqrt x<100\sqrt P$ 个，由于 $a_i,b_i$ 随机，有一定的理由假定满足上述条件的 $x$ 几乎是随机分布的，我们找两个方程，同时位于它们所确定的这两个区域里的 $x$ 的期望数量大约为：
于是只要把每个拿出来检验一下是不是解就行了。现在问题是怎么找到这两个区域的交，将问题重新描述如下，找 $x$ 使得：
枚举 $X=(A_1-B_1x)\bmod P$，则 $x=(A_1-X)\times B_1^{-1}$，将其带入第二个不等式：
化简：
其中 $A’=A_2-B_2A_1B_1^{-1}, B’=B_2B_1^{-1}, C’=C_2$。最后这个问题可以用类欧解决。具体地，我们每次二分下一个满足条件的 $X$，问题转化为判定一个区间里是否存在一个满足条件的 $X$，然后稍微推一下式子：
就变成了一个比较标准的类欧问题。
稍微口胡一下，比如用万欧的话，记左边的值为 $S$，遇到一根竖线就是 $S\leftarrow S+B$，横线就是 $S\leftarrow S-P$，要求 $S$ 的历史最小值，这个显然是一个可合并信息。
$O(B^2\log^2 P)$
THUSC
T1：
题目大意：
给定一个长 $n$ 的序列，$q$ 次操作：区间加 / 询问一个区间至少要用几次区间 +1 或区间 -1 操作变成全为 $x$。
$n,q\leq 3\times 10^5$
题解：
显然一个区间询问的答案等于在区间前后各加一个 $x$ 后，相邻数差的绝对值之和除以 $2$，线段树维护差分序列，支持单点修改即可。
$O(n+q\log n)$
T2：
题目大意：
给定 $n+m+1$ 个点的无向带权图，边权 $w_i$ 表示经过这条边需要消耗 $w_i$ 的时间以及燃料。$0$ 是基地，$[1,n]$ 是游乐园，$[n+1,n+m]$ 是补给站。你需要以 $1,\ldots,n$ 的顺序依次在每个游乐园表演一次，在游乐园 $i$ 表演消耗 $v_i$ 能量。
你的最大燃料量和最大能量分别为 $L,V$，当你到达补给站 $i$ 时可以花 $c_i$ 时间补满燃料，当你到达基地时可以花 $c_0$ 时间补满燃料和能量。
求从基地出发完成所有表演回到基地需要的最小时间。
$n\leq 200, m\leq 50$
题解：
相当于要将 $[1,n]$ 分成若干段 $[l_i,r_i]$，每一段都满足 $v_{l_i}+\ldots+v_{r_i}\leq V$，然后路线设计为 $0\to l_1\to r_1\to 0\to l_2\to r_2\to 0\to \ldots$，假设已经算出 $0\to l\to r\to 0$ 的最小时间为 $c(l,r)$，则后面只是个简单的 1D/1D 动态规划。下面考虑怎么算 $c(l,r)$。
固定 $l$，从 $l$ 往后 DP。设 $f(i,j)$ 表示表演完了 $l,\ldots,i$，现在出现在补给站 $j$ 的最小时间。$f(i,j)$ 可以转移到 $f(k,l)$ 当且仅当 $dis(j,i+1)+dis(i+1,i+2)+\ldots+dis(k-1,k)+dis(k,l)\leq L$。
直接枚举 $k,l$ 是 $O(n^3m^2)$，但可以记辅助变量 $g(i,j)$ 表示现在表演完了 $i$，下面必须去补给站，并且只能去到 $i$ 距离不超过 $j$ 的补给站，这种情况的最小时间。那么在转移时可以只枚举 $k$，然后 $f(i,j)\to g(k,L-dis(j,i+1)+dis(i+1,i+2)+\ldots+dis(k-1,k))$，然后再 $g(k,x)\to f(k,l) (dis(k,l)\leq x)$。注意 $g$ 本质不同的状态只有 $O(m)$ 种。这样复杂度是 $\tilde O(n^3m)$ 的。
其实还可以再优化，设 $S(i,j,k,l)=dis(j,i+1)+dis(i+1,i+2)+\ldots+dis(k-1,k)+dis(k,l)$，根据三角形不等式可知 $S$ 关于 $k$ 是单调的。同时注意到 $S$ 可以拆贡献 $S(i,j,k,l)=S_1(k,l)+S_2(i,j)$，其中 $S_1(k,l)=dis(1,2)+\ldots+dis(k-1,k)+dis(k,l)$，$S_2(i,j)=-dis(1,2)-\ldots-dis(i,i+1)+dis(j,i+1)$。
所以转移时我们只枚举 $l$，然后算出一个最大的 $k$，在此之前的 $(k’,l)$ 都可以从 $(i,j)$ 转移，对于每个 $l$ 都用一个什么数据结构维护一下决策就行了。
$\tilde O(n^2m^2)$
T3：
题目大意：
有 $n$ 个人 $m$ 张纸条，第 $i$ 个纸条初始在第 $p_i$ 个人手上，写有数字 $q_i$。每一轮，第 $i$ 个人会看他手里每一张纸条的数字 $x$，将它修改为 $b_{i,x\bmod d_i}$ 然后交给第 $a_{i,x\bmod d_i}$ 个人。求 $T$ 轮内有多少时刻所有纸条都在第 $1$ 个人手上。
$n\leq 80, m\leq 800, d_i\leq 54, T\leq 10^{100}$
题解：
将每个人看成 $d_i$ 个点，可以写成一个 $\sum d_i$ 个点的基环树森林，其中有 $d_1$ 个关键点，要问有多少时刻每个纸条都在关键点上。
有一张纸条不在环上的情况可以暴力做掉，剩下的就是都在环上，一个环上多个纸条显然是可以合并的，所以现在问题就是：有若干个集合 $S_1,\ldots,S_k$ 和一个序列 $a_1,\ldots,a_k$，求有多少个 $X\in [1,T]$ 满足 $X\bmod a_i\in S_i (\forall i)$，并且 $\sum |S_i|\leq 54$。
注意 $\sum |S_i|\leq 54$ 说明 $\prod |S_i|$ 大概就不超过 $3^{18}$。尽管如此，直接枚举肯定还是会 T 的，所以可以考虑折半搜索。
分成两半，两边暴力 exCRT（注意 CRT 过程中所有模数都很小，所以做 exgcd 的时候有一个数很小，复杂度是一个 $\log$），然后整理得到两个方程：
其中 $A_1\in T_1, A_2\in T_2$，其中 $|T_1|,|T_2|$ 不是很大（大概 $3^9$）。
设 $D=\gcd(M_1,M_2)$，先把所有 $T_1,T_2$ 中元素模 $d$ 分组，每组分别做，然后就可以将 $M_1,M_2$ 都除以 $D$，变成普通 CRT 了，带入 CRT 的式子，设（这里的 $M_1,M_2$ 是除之后互素的）$M=M_1M_2$，$B=(M_2^{-1}\bmod M_1)\times M_2, C=(M_1^{-1}\bmod M_2)\times M_1$，问题转化为：
不同的 $(A_1,A_2)$ 答案至多差一，枚举 $A_1$ 后使得答案不同的两段 $A_2$ 很容易通过预处理后快速算出来。
$O(3^{D/6}\times \log T+\log^2 T)$
T4:
题目大意：
交互题。
有一个 $n\times m$ 的网格，它被划分为 $k$ 个（矩形的）子网格。按照所属子网格左上角的横纵坐标和自己的横纵坐标为一二三四关键字对所有格子排序。你可以询问某个格子的排名，请在 $45k$ 次操作内得到排名为 $x$ 的格子位置。注意 $k$ 是不给你的。
$n,m\leq 10^6$
题解：
将格子的排名称为标号。
考虑按照子网格左上角的编号顺序依次确定每个子网格的形状。注意如果有两个子网格是可以直接合并（而不影响编号）的，那么我们求出的一定是合并后的结果（虽然这不重要）。
设当前要确定形状的子网格左上角为 $(x,y)$，标号为 $A$。设 $z$ 是满足 $(x,z)$ 已经被另一个子网格占据的最小的数（如果没有就是 $m+1$），我们有下面三种情况（红色是当前正在确定的子网格）：
我们先问 $(x,z-1)$，如果它不是 $A+z-y-1$，那么就只能是情况一，可以二分右下边界。
如果 $(x,z-1)$ 的标号就是 $A+z-y-1$，我们再问 $(x+1,y)$ 的标号，如果不是 $A+z-y$，说明一定是情况二（当然也可能退化为情况一），我们在 $(x+1,y)$ 到 $(x+1,z-1)$ 中二分找到标号 $A+z-y$ 的位置，就确定了蓝色子网格的左边界，也就确定了当前子网格的右边界。
如果 $(x+1,y)$ 的标号是 $A+z-y$，那么有可能是情况三或情况一，我们找到使得 $(u,y)$ 标号为 $A+(u-x)(z-y)$ 的最大的 $u$，则它要么是当前子网格的下边界，要么是蓝色子网格的上边界，我们再二分一下 $(u,y)$ 往右最多是不是能延伸到 $(u,z-1)$，就知道是哪种情况了。
询问次数不超过 $(\log n+\log m+C)k$，$C$ 感觉不超过 $2$。