我是中国 OI 选手。
开头是两套《省选难度》的 UR，明显做不太动，所以后面放了 UER 的一些题。
UR #25
UOJ805 设计草图
找一下合法的判据，首先保证 $[l, r]$ 长度为偶数，考虑对于替换 ? 之后要能够合法需要的条件。
把所有的 ? 变成 (，令 ( 为 $+1$，) 为 $-1$，必须保证所有前缀和非负。
把所有的 ? 变成 )，令 ) 为 $+1$，( 为 $-1$，必须保证所有后缀和非负。
维护一下单调栈，处理出来每个位置左右最多能够够到的地方，然后需要二维数点。
UOJ806 见贤思齐
首先 $i$ 向 $p_i$ 连边，会形成内向基环树，首先考虑最简单的情况，一棵有根树怎么做。
固定根节点的权值不变或者每天都加一，设第 $i$ 个人在第 $j$ 天结束时能力值为 $f(i, j)$，有
下面的性质很强，需要手玩才能拿出来，即是如果存在 $j$ 使得 $f(i, j) = f(p_i, j)$ 或 $f(i, j) = f(p_i, j) + 1$，那么在之后的每一个时间点来说都会保持这样的关系。
然后定义 $g(i, j) = f(i, j + dep_i) - dep_i$，可以得到
证明是
$$ \begin{aligned} &f(i, j + dep_i) - dep_i = f(p_i, j + dep_{p_i}) - dep_{p_i} \\ \rightarrow& f(i, j + dep_i) - dep_i = f(p_i, j + dep_i + 1) - dep_i - 1 \end{aligned} $$意思是，父节点权值会在 $j + 1$ 时是当前节点的权值加一。
然后可以用线段树维护 $g(i, *)$，是在 $g(p_i, *)$ 的基础上修改一段前缀得到。
基环树的做法需要一个观察，对于树上最小权值记为 $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$ 中较小的一个追平了权值之后建立的等式。
于是写出来应该是
理解一下，取到 $\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$。
此时维护一个 $l = -\infty,r = +\infty$，每次 $l = \max\{ l, a_i - t \}, r = \min\{ r, a_i \}$。两个指针相遇就是答案。
可以倍增优化。
UR #24
UOJ792 比特跳舞
首先几个部分分很好求，不想多说，感觉时间复杂度是单 $\log$？
瞄了一眼最短代码长度为 408b，居然不是巨型数据结构，有点震撼，这个速度莫非是 $\Theta(n)$。😓
从部分分入手想一下。
怎么算从 $u$ 到 $v$ 的简单路径序列的本质不同的子序列个数，考虑每次往长度为 $n$ 的序列后面添加一个数的贡献。
注意一下边界，$dp_{0} = 1, dp_{1} = 2$。
如果这个式子的结果是奇数，那么二元组 $(u, v)$ 是合法的。
首先去掉 $2^n$，这一块一定是偶数，去掉不影响整个式子的奇偶性，注意观察，假设目前没有重复的元素出现，那么这个式子的结果一直都是偶数。如果出现了重复的元素，若该元素不在第一位，那么减去的 $\sum_{a_{pos} = a_{n + 1}} dp_{pos - 1}$ 仍然是偶数；若该元素在第一位，那么减去的 $\sum_{a_{pos} = a_{n + 1}} dp_{pos - 1}$ 中存在 $dp_{0}$ 使得整个式子改变了奇偶性。
于是得到现在的做法，我们只关心第一位数字是啥，以及这一位数字在后续的序列中重复出现的位置，重复出现了奇数次后会对答案有贡献。
思考如何快速统计答案，固定起点非常不好做，平凡的想法是转成考察对于当前节点为终点，能造成多大的贡献，记录当前序列中最后一个数字出现次数，那么之前不同奇偶性的位置都能产生贡献，发现这个东西能直接 dfs 一遍解决。
好吧，这个 dfs 可能还是需要写一下具体实现。
UOJ793 比特智慧
全场最高分 5pts，有点震撼。
UOJ794 比特之地
写了 50pts 做法，100pts 需要 link
UER #10
UOJ706 随机薅羊毛
纯推式子？首先把高斯消元的式子写出来，定义 $dp_{i}$ 表示从 $i$ 开始一直抽直到获奖的期望步数，那么有 $dp_{i} = \frac{(1 - p_i)\sum_{j = 1, j \not= i}^{n}dp_j}{n - 1} + 1$。
令 $s = \sum_{i = 1}^{n} dp_i$，那么 $dp_i = \frac{(1 - p_i)(s - dp_i)}{n - 1} + 1 = \frac{(1 - p_i)(s - dp_i) + n - 1}{n - 1}$。调整一下 $dp_i = \frac{s(1 - p_i) + n - 1}{n - p_i}$，然后把所有的 $dp_i$ 加起来有
答案是 $\frac{s}{n}$。
UOJ707 重构元宇宙
有点困难，靠看 vfleaking 博客了。
我什么时候能学会把距离转内积啊啊啊啊啊啊。
首先确定这个 $k$ 维空间的原点 $0$，然后对于点 $p, q$ 来说，有如下三个式子
然后用第一个式子减去后面两个式子
$$ \begin{aligned} &\sum_{i = 1}^{k} \left( (x_{p, i} - x_{q, i})^2 - x_{p, i} ^2 - x_{q, i}^2 \right) \\ =&-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} \left(d^2(p, q) - d^2(p, 0) - d^2(q, 0)\right) \end{aligned} $$然后原问题重新被描述为
$$ \begin{align} \forall p, q \in \{1, \dots, n -1\}: \qquad \sum_{j=1}^{k} x_{p,j} \cdot x_{q,j} = A_{p,q}. \tag{F} \end{align} $$于是首先钦定原点，每次加入一个新的点都有
$$ \begin{aligned} \sum_{i=0}^{k-1} x_{t,i} \cdot x'_i=-\frac{d^2(x',x_i)-d^2(0,x)-d^2(0,x_t)}{2} \end{aligned} $$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)$ 中的点建边，$\forall i \in [2, cnt], j \in [0, x_1)$，从 $j$ 向 $(x_i + j) \mod x_1$ 建权值为 $x_i$ 的边，$dis_i$ 的含义是用 $[2, cnt]$ 的 $x_i$ 拼出来的最小的在模 $x_1$ 的意义下等于 $i$ 的数。
然后复杂度是 $\Theta(n^2 \log n)$ 的，考虑用性质优化。
对于任意一个字符串，它的 border 长度一定会构成 $\Theta(n \log n)$ 个等差数列
可以递归证明，proof。
然后拎出来每一个等差数列，假设首项为 $x$，公差为 $d$，长度为 $len$。
考虑我只有这一个等差数列该怎么去做？观察到会连出来环，一共有 $\gcd(d, x)$ 个，并且每个环都是独立的。
那如何在环上更新呢？首先环的起始位置是不会被更新到的，相邻的点之间的边长一定为 $d$，那现在来维护一个单调队列，里面只用放下标距离当前点在 $len$ 以内的点，对于环上 $a$ 来更新 $b$ 之间的代价为 $dis_a + d \cdot (pos_b - pos_a)$，于是用 $dis_a - pos_a$ 作为关键字比较即可。
剩下的问题是在不同模数之间切换，假设先前的模数为 $las$，现在模数为 $now$，于是再用 $x$ 更新 $(x + las) \mod now$ 即可。
复杂度降为 $\Theta(n \log n)$。