「UOJ」 UOJ Round 做题记录

我是中国 OI 选手。

开头是两套《省选难度》的 UR，明显做不太动，所以后面放了 UER 的一些题。

UR #25

UOJ805 设计草图

找一下合法的判据，首先保证 $[l,r]$ 长度为偶数，考虑对于替换 ? 之后要能够合法需要的条件。
把所有的 ? 变成 (，令 ( 为 $+1$，) 为 $-1$，必须保证所有前缀和非负。
把所有的 ? 变成 )，令 ) 为 $+1$，( 为 $-1$，必须保证所有后缀和非负。

维护一下单调栈，处理出来每个位置左右最多能够够到的地方，然后需要二维数点。

UOJ806 见贤思齐

首先 $i$ 向 $p_i$ 连边，会形成内向基环树，首先考虑最简单的情况，一棵有根树怎么做。
固定根节点的权值不变或者每天都加一，设第 $i$ 个人在第 $j$ 天结束时能力值为 $f(i,j)$，有

$$\begin{array}{}\text{(1)}& \{\begin{array}{l}f(i,0)=a_i\\ f(i,j)=max\{f(p_i,j-1)+[f(i,j-1)\le f(p_i,j-1)]\}\end{array}\end{array}$$

下面的性质很强，需要手玩才能拿出来，即是如果存在 $j$ 使得 $f(i,j)=f(p_i,j)$ 或 $f(i,j)=f(p_i,j)+1$，那么在之后的每一个时间点来说都会保持这样的关系。
然后定义 $g(i,j)=f(i,j+de{p}_i)-de{p}_i$，可以得到

$$\begin{array}{}\text{(2)}& \begin{array}{r}g(i,j)=g(p_i,j)\to g(i,j+1)=g(p_i,j+1)\end{array}\end{array}$$

证明是

$$\begin{array}{}\text{(3)}& \begin{array}{rl}& f(i,j+de{p}_i)-de{p}_i=f(p_i,j+de{p}_{p_i})-de{p}_{p_i}\\ \to & f(i,j+de{p}_i)-de{p}_i=f(p_i,j+de{p}_i+1)-de{p}_i-1\end{array}\end{array}$$

意思是，父节点权值会在 $j+1$ 时是当前节点的权值加一。
然后可以用线段树维护 $g(i,\ast )$，是在 $g(p_i,\ast )$ 的基础上修改一段前缀得到。
基环树的做法需要一个观察，对于树上最小权值记为 $minl$，在经过一天之后，$minl$ 一定会增加 $1$。于是把环上最小的点拎出来，把边断掉，以它为根按树的做法做即可。

然后学了一下 zky 的做法，感觉吊打 std。

对于 $f(i,j)$ 一开始是 $a_i$ 或者是 $a_i+j$，分别对于 $a_{p_i}$ 还比 $a_i$ 小，$a_{p_i}$ 比 $a_i$ 大的情况，即是说一类会先保持一会不动，一类会让它从开始就增加。
而当过了一段时间之后，$f(i,j)=f(p_i,j-1)+1$，很好理解，即是说 $i$ 和 $p_i$ 中较小的一个追平了权值之后建立的等式。
于是写出来应该是

$$\begin{array}{}\text{(4)}& \begin{array}{r}f(i,j)=max\{min\{f(p_i,j-1)+1,a_i+j\},a_i\}\end{array}\end{array}$$

理解一下，取到 $min\{f(p_i,j-1)+1,a_i+j\}$，表明此时的 $a_{p_i}>a_i$，如果是 $f(p_i,j-1)+1$ 则表明 $i$ 已经追平了这段差距，否则则表明 $i$ 还没有追平。如果取到了 $a_i$ 则说明 $p_i$ 还没有追平 $i$。
或许是技巧，这几天看到了几次了，把里层的变量拎出来，对于这个式子拎出来 $j$，令 $g(i,j)=f(i,j)-j$。

$$\begin{array}{}\text{(5)}& \begin{array}{r}g(i,j)=max\{min\{g(p_i,j-1)+1,a_i\},a_i-j\}\end{array}\end{array}$$

此时维护一个 $l=-\mathrm{\infty },r=+\mathrm{\infty }$，每次 $l=max\{l,a_i-t\},r=min\{r,a_i\}$。两个指针相遇就是答案。
可以倍增优化。

---

UR #24

UOJ792 比特跳舞

首先几个部分分很好求，不想多说，感觉时间复杂度是单 $\log$？
瞄了一眼最短代码长度为 408b，居然不是巨型数据结构，有点震撼，这个速度莫非是 $\mathrm{\Theta }(n)$。😓

从部分分入手想一下。
怎么算从 $u$ 到 $v$ 的简单路径序列的本质不同的子序列个数，考虑每次往长度为 $n$ 的序列后面添加一个数的贡献。

$$\begin{array}{}\text{(6)}& \begin{array}{r}d{p}_{n+1}=d{p}_n+2^n-\sum _{a_{pos}=a_{n+1}}d{p}_{pos-1}\end{array}\end{array}$$

注意一下边界，$d{p}_0=1,d{p}_1=2$。
如果这个式子的结果是奇数，那么二元组 $(u,v)$ 是合法的。
首先去掉 $2^n$，这一块一定是偶数，去掉不影响整个式子的奇偶性，注意观察，假设目前没有重复的元素出现，那么这个式子的结果一直都是偶数。如果出现了重复的元素，若该元素不在第一位，那么减去的 $\sum _{a_{pos}=a_{n+1}}d{p}_{pos-1}$ 仍然是偶数；若该元素在第一位，那么减去的 $\sum _{a_{pos}=a_{n+1}}d{p}_{pos-1}$ 中存在 $d{p}_0$ 使得整个式子改变了奇偶性。
于是得到现在的做法，我们只关心第一位数字是啥，以及这一位数字在后续的序列中重复出现的位置，重复出现了奇数次后会对答案有贡献。
思考如何快速统计答案，固定起点非常不好做，平凡的想法是转成考察对于当前节点为终点，能造成多大的贡献，记录当前序列中最后一个数字出现次数，那么之前不同奇偶性的位置都能产生贡献，发现这个东西能直接 dfs 一遍解决。

好吧，这个 dfs 可能还是需要写一下具体实现。

UOJ793 比特智慧

全场最高分 5pts，有点震撼。

UOJ794 比特之地

写了 50pts 做法，100pts 需要 link

---

UER #10

UOJ706 随机薅羊毛

纯推式子？首先把高斯消元的式子写出来，定义 $d{p}_i$ 表示从 $i$ 开始一直抽直到获奖的期望步数，那么有 $d{p}_i=\frac{(1-p_i)\sum _{j=1,j\ne i}^{n}d{p}_j}{n-1}+1$。
令 $s=\sum _{i=1}^{n}d{p}_i$，那么 $d{p}_i=\frac{(1-p_i)(s-d{p}_i)}{n-1}+1=\frac{(1-p_i)(s-d{p}_i)+n-1}{n-1}$。调整一下 $d{p}_i=\frac{s(1-p_i)+n-1}{n-p_i}$，然后把所有的 $d{p}_i$ 加起来有

$$\begin{array}{}\text{(7)}& \begin{array}{rl}s& =\sum _{i=1}^{n}d{p}_i\\ & =\sum _{i=1}^n\frac{s(1-p_i)+n-1}{n-p_i}& =s\sum _{i=1}^n\frac{1-p_i}{n-p_i}+(n-1)\sum _{i=1}^n\frac{1}{n-p_i}\\ \Rightarrow s& =\frac{(n-1)\sum _{i=1}^n\frac{1}{n-p_i}}{1-\sum _{i=1}^n\frac{1-p_i}{n-p_i}}\end{array}\end{array}$$

答案是 $\frac{s}{n}$。

UOJ707 重构元宇宙

有点困难，靠看 vfleaking 博客了。
我什么时候能学会把距离转内积啊啊啊啊啊啊。
首先确定这个 $k$ 维空间的原点 $0$，然后对于点 $p,q$ 来说，有如下三个式子

$$\begin{array}{}\text{(8)}& \begin{array}{rl}\sum _{i=1}^k(x_{p,i}-x_{q,i}{)}^2& =d^2(p,q)\\ \sum _{i=1}^k{x}_{p,i}^2& =d^2(p,0)\\ \sum _{i=1}^k{x}_{q,i}^2& =d^2(q,0)\end{array}\end{array}$$

然后用第一个式子减去后面两个式子

$$\begin{array}{}\text{(9)}& \begin{array}{rl}& \sum _{i=1}^k((x_{p,i}-x_{q,i}{)}^2-x_{p,i}^2-x_{q,i}^2)\\ =& -2\sum _{i=1}^k{x}_{p,i}\cdot x_{q,i}\\ \Rightarrow & \sum _{i=1}^k{x}_{p,i}\cdot x_{q,i}=\frac{1}{2}(d^2(p,q)-d^2(p,0)-d^2(q,0))\end{array}\end{array}$$

然后原问题重新被描述为

$$\begin{array}{}\text{(F)}& \mathrm{\forall }p,q\in \{1,\dots ,n-1\}:\sum _{j=1}^k{x}_{p,j}\cdot x_{q,j}=A_{p,q}.\end{array}$$

于是首先钦定原点，每次加入一个新的点都有

$$\begin{array}{}\text{(10)}& \begin{array}{r}\sum _{i=0}^{k-1}{x}_{t,i}\cdot x_i^{\prime }=-\frac{d^2(x^{\prime },x_i)-d^2(0,x)-d^2(0,x_t)}{2}\end{array}\end{array}$$

---

Other

UOJ172 论战捆竹竿

有点难，我边看题解边记录一些东西。
首先每次可以在后面添加一个 border，长度增加 $|S|-border$，首先处理出来 border，记 border 集合中每个 border 的长度为 $x_i$，那么需要找在 $[0,w-|S|]$ 中，$\sum _{i=1}^{cnt}{a}_i\cdot x_i$ 能有多少种取值。
看起来是跑同余最短路。具体过程是将 $x$ 从小到大排，用 $x_1$ 作为模数，对于 $[0,x_1)$ 中的点建边，$\mathrm{\forall }i\in [2,cnt],j\in [0,x_1)$，从 $j$ 向 $(x_i+j)\mathrm{mod}{x}_1$ 建权值为 $x_i$ 的边，$di{s}_i$ 的含义是用 $[2,cnt]$ 的 $x_i$ 拼出来的最小的在模 $x_1$ 的意义下等于 $i$ 的数。
然后复杂度是 $\mathrm{\Theta }(n^2\log n)$ 的，考虑用性质优化。

对于任意一个字符串，它的 border 长度一定会构成 $\mathrm{\Theta }(n\log n)$ 个等差数列

可以递归证明，proof。

然后拎出来每一个等差数列，假设首项为 $x$，公差为 $d$，长度为 $len$。
考虑我只有这一个等差数列该怎么去做？观察到会连出来环，一共有 $gcd(d,x)$ 个，并且每个环都是独立的。
那如何在环上更新呢？首先环的起始位置是不会被更新到的，相邻的点之间的边长一定为 $d$，那现在来维护一个单调队列，里面只用放下标距离当前点在 $len$ 以内的点，对于环上 $a$ 来更新 $b$ 之间的代价为 $di{s}_a+d\cdot (po{s}_b-po{s}_a)$，于是用 $di{s}_a-po{s}_a$ 作为关键字比较即可。

剩下的问题是在不同模数之间切换，假设先前的模数为 $las$，现在模数为 $now$，于是再用 $x$ 更新 $(x+las)\mathrm{mod}now$ 即可。

复杂度降为 $\mathrm{\Theta }(n\log n)$。