加训目录

2025.10

UR 32

改革前的最后一次UR，被彻底干爆了。
solved:0/3

A

首先可以发现钦定位置是什么再做是极为困难的，所以我们尝试发掘性质。不难猜到操作具有可交换性。枚举选择多少个 \(U/D\) 再模拟冒泡排序 \(n\) 轮就能得到一个 \(\Theta(n^2k)\) 的做法。期望得分34。

然后我们就没活了，这个序列是很难快速维护的，不管怎么使用数据结构都无法做到 \(o(n)\) 维护一轮冒泡排序。（寄）

原问题做出了一个转化，（非常莫名其妙），通过枚举一个中间值 \(a\) 使得序列分成由小于和不小于的 \(a\) 表示的 \(01\) 序列。序列排序完毕当且仅当所有划分意义下 \(01\) 序列都有序。

\(U\) 会把一个 \(1\) 挪到序列最后，\(D\) 会把一个 \(0\) 挪到序列开头。

对于每个位置 \(i\) 注意这个 \(i\) 是流动意义下的，不一定一直停留在 \(i\) 的下标上来说，它右边的 \(0\) 元素全部挪到左边需要 \(\lceil \frac{R_0}{cnt_D} \rceil\)，它左边的 \(1\) 元素全部挪到右边需要 \(\lceil \frac{L_1}{cnt_U} \rceil\) 次。 \(\max_{i = 1} ^ {n - 1} \min (\lceil \frac{R_0}{cnt_D} \rceil, \lceil \frac{L_1}{cnt_U} \rceil)\) 就是答案。（UOJ似乎这里还写错了）

当枚举 \(cnt_D\) 和划分 \(01\) 的界限的时候，分界线的变化是均摊 \(\Theta(1)\) 的。维护一下就行了。

这个也太难了吧。

B&C

不会。

2025.11

ARC211

solve:3/5

a

没什么好说的，注意讨论一下5的情况就好了。

b

没看到 \(x \leq y \leq z\) 还写了个假做法，幽默完了。
先判掉0的情况，对于答案是 \(1\) 的情况，

\[\begin{aligned} &(x - 1) * 1 + y - (x - 1) * 0 \\ &(z - 1) * 1 + 1 * 0 \\ &(z - 1) * 1 + y - (x - 1) * 0 \end{aligned} \]

就可以了。

c

比较套路。操作先猜猜性质，不难证出一定删掉的是一段区间，求某个点为中心的答案是经典的区间 DP 问题，但是不能把问题泛化。注意到每一个空隙的最大值一定会被取一次，我们把剩下的被加的机会全丢给全局最大值就好了。

std的实现非常优美。相比之下我写的就很贻笑大方。

d

被猜穿了/fn
其实我明明做出来了啊？？有解的充要条件是缩点之后 \(1\) 和 \(2\) 在唯一的一条链的左右两端的 ECC 中。然后直接输出 DFS 树就是对的。为什么我写了一个如果遇到上次搜过的边就 break 呢？
感觉是不是还在役的话这题5分钟就过了？
这题越想越简单，没救了。

e

暂时还不会。

2025.12

Codeforces Round 1069

solve:1/6 （你在干嘛）

彻底倒闭了！！！！
如此水平，如何THUPC？
如此水平，
如何THUPC？

a

每个位置枚举加入哪个字符，有两种可能：

• 能匹配的字符
• 不能匹配但是加入后不会影响后面能匹配的字符
  这两种情况哪个字符小就匹配哪个，没什么好说的。

b

我是傻逼。
首先这个题最难的一点可能是观察到只有前缀最大值的位置才能放东西（我很快就发现了），原因是不在前缀最大值的位置放超过前缀最大值的东西的话，一定可以交换两堆东西使得答案变大。

然后 DP 的点非常愉快的只有 \(K\) 个了，然后？然后你瞎推什么性质啊？这不是直接做就好了吗？一个二维的 dp 记录 \(i, j\) 表示现在的和、最大值，转移的时候枚举当前位置放多少和放不放。这个是 \(\Theta(K^4)\) 的 能冲过去，正解则是套路发现转移和第二维几乎无关（除了枚举下界），仔细想下是完全无关，因为不合法的不优，就是 \(\Theta(K^3)\) 了。（中间被压掉的段的贡献需要在前缀 \(\max\) 的位置算上）

这题挺牛的，给出题人点赞。你说你把这个放在NOIp多好

c1/c2

不懂啊。
首先观察到这个平方是经典问题，即枚举所有的 \([l, r][L, R]\)，统计这两个串同时是回文串的概率，再把所有的概率加起来。
考虑怎么算这个概率。经过一通尝试之后就会发现对于绝大多数情况，有 \(\lfloor\frac{len_1}{2}\rfloor+\lfloor\frac{len_2}{2}\rfloor\) 个位置是由其他位置完全确定的。那么对于一组 \([l, r][L, R]\)，它的概率就是 \(\frac{1}{m^{\lfloor\frac{len_1}{2}\rfloor+\lfloor\frac{len_2}{2}\rfloor}}\)。

错误的做法：枚举 \(\lfloor\frac{len_1}{2}\rfloor+\lfloor\frac{len_2}{2}\rfloor\)，大力计算方案数量，经过讨论之后方案数是各种奇偶情况的一个二次求和。

正确的做法：注意到两串是完全独立的，计算一边的概率及其选择方案数再平方。

但是其中还有一个问题：两串中心重合的时候，概率是 \(\frac{1}{m^{\lfloor\frac{len_1}{2}\rfloor}}\)。

这个稍微会有些细节，需要枚举 \(len_1\) 对 \(len_2\) 的一些东西求和，减去不合法的情况，再加上合法的情况，总之不会比我写的要困难吧（）

d

我都不知道怎么形容自己的菜了/xk
这个题首先加上最短的 \(n - 1\) 条边，然后有可能是通过加上一条边，再删掉这条边覆盖路径以外最长的边的方法得到的。这个就非常CNOI友好，随便做。我写的是树剖 + ST表。当然这题不可能就这么简单。有一种情况是会删掉原图的两条边，把树断成从左到右 1,2,3 三个部分，再加上两条边连接 1,3 两个部分。这个维护不了。

但是我怎么想到这里倒闭了？这个很难吗？注意到任意选择原树中的两条边换掉，要么是这种情况，要么不是这种情况并且严格不优，所以直接把最长的原图的边换成最短的外面的边就好了。

我怎么感觉 BCD 的难度没有区别啊？

e~f

暂时还不会。