ZROI 20连题解 - 洛谷保存站

# 落忆枫音

反正感觉没啥题做，要不要补一下 ZROI 呢？

希望一两天内改完。

## Day3 C

先随机赋权，然后：

- $k = 1$，简单的，对应着一种 hash
- $k = 2$，考虑二进制分组，一定有一位不一样。
- $k = 3$，只需要找出来一个位置即可，一定存在一个位置满足这三个数不在一个位置，注意判定即可。

std 采用了大神哈希优化。

## Day5 D

注意按照 $y$ 排序检查实际上就是对的。

考虑按照 $y$ 扫描线，然后我们将可以的设为 $1$， 不可以的设为 $-1$，然后我们就并不关心具体大小了，只要后缀最小值大于等于 $0$ 即可。这个相当于一个 Hall 定理。

## Day6 C

## Day7 B

具体来说就是决策森林是因为子区间是优美的，所以可以建出来，

然后相当于如果不删这个子区间就会往下递归，求最大平均数是凸包合并，此处可以使用 Minkowoski 来解决，复杂度 $O(n \log n)$。

代码暂时写不动。

## Day8 D

实际上是你考虑合法的位置那些填了数，描述出了形态后可以尝试用组合数学进行计算多项式的点值。

描述形态的过程应该需要二项式反演之类的东西。

## Day9 D

## Day12 C

仔细想了一会感觉应该是个简单题，但是我为什么没有过呢？

注意转移顺序就是链底向上一个链底连边，然后链头向链底连边。

然后你就要求一颗树的排列方案数满足 $P_x < P_{fa_x}$ 即可。

这个你可以尝试树形 DP / 组合数嗯做，最后可以得出 $\frac{n!}{\prod siz_x}$，最后使用 LCT 即可。

## Day13 A

## Day13 C

疑似 Dirty Work，不想写怎么办（

实际上只需要将邻域摊开来到序列上然后大力分块即可，每次贡献只需要拟合系数。

注意分块的一个细节是跨过整块一定要两边都跨过去，这样算才是对的。

复杂度 $O(q \sqrt m)$。

## Day14 D

答案合并是一个半群，选手自己精心构造即可，这是不难的。

把只算前 32 次的贡献变成一个阈值状物即可做到 1log。

## Day14 C

但是为啥是有单调性的呢？？貌似感性理解，感觉会这里就做完了！

往一边倒可行是有单调性的，不妨求出其阈值 $a_i, b_i$。

这个东西是方便求出的，

然后对于区间 $[l, r]$ 的询问无非就是 $l \leq a_i \and i \leq r + l \leq i \and b_i \leq r - (l \leq a_i \and b_i \leq r)$，对其扫描线即可，复杂度 $O(n \log n)$。

## Day17 C

## Day19 C

正在渲染内容...