10.28 写题

P5901 regions

按颜色数量进行根号分治。离线下来,对于出现次数 $\le \sqrt n$ 的点作为下方点的情况,我们处理出这个点到根路径上每种颜色数量,那么对于一次询问,我们只会在这个询问的下方点进行一次询问,这里下方点数量是 $O(\sqrt n)$ 的。然后考虑出现次数 $> \sqrt n$ 的点作为下方点。对于每个点处理出子树内的出现次数 $> \sqrt n$ 的点的数量,然后从每个上方点查询即可。每个点最多只会进行 $O(\sqrt n)$ 次这种询问。复杂度就是 $O(n\sqrt n)$。

但是还需要考虑空间复杂度。每个点都算一下当前子树中大点的出现次数空间会是 $O(n\sqrt n)$ 在这题会被卡死,所以我们可以先减去当前这些点的出现次数,再加上遍历结束后的出现次数。

空间 $O(n)$ 时间 $O(n\sqrt n)$。

10.28 提高组模拟赛 T4

四元环计数,裸题。

四元环计数和三元环做法基本一样,钦定一个点作为最小点,枚举这个点一个出边,再枚举出去后的这个点的出边,两次必须保证编号大于开始点,然后打 tag 即可。

lower_bound 实现的,复杂度是 $O(n\log n + n\sqrt n)$ (默认边和点同阶)。

可以开始把图建好,小的点连向大的点,其实是一样的。

10.28 T3 牛牛的凑数游戏

水题。结论大概是前面一段的和 $+1$ 如果小于下一个位置的值,那么这个和加一就是最小的不可被表示的数。可以方便地归纳证明。

正解用了一个迭代然后主席树或者 BIT ,其实可以按位维护,对每个位维护出最小的两个数以及这个位为最高位的所有数的和。不难发现答案只会再这些情况中产生,因为同一个位中的两个数加起来必然会爆到下一位。

10.28 T4 牛牛的RPG游戏

套路题。先 cdq 一下,每次割长的那个边,然后相当于把一条加入凸包再查询一条的答案。这个东西斜率和截距貌似都没啥规律,直接上李超树即可。复杂度两个 $\log$ 。

也可以用 BIT 套李超树整过去,复杂度一样,实际上还快一点。

然后这题每次加入一层来做也可以。。因为对 $n,m$ 大小交换后就只有 $O(\sqrt n)$ 级别了。。数据范围太小暴力没卡掉。

CF480E

有修改,考虑分治。每次选择较长边切开,然后考虑维护跨过中线的最大正方形。

这个东西可以双指针 + 单调队列维护。每次修改复杂度是 $T(n) = T(\frac n 2) + O(n)$ 也就是 $O(n)$ 级别的。所以总的复杂度是 $O(n^2)$。

Hunger Game

8__ZYW~MZI6_X9_93PO@PRB.png

最开始的时候,开着的箱子异或为 $0$ 。

如果不存在一个子集异或为 $0$ ,那么先手操作一次后后手通过 nim 游戏的操作一定可以使得开着的箱子的异或为 $0$ 。然后就回到了最初的状态。

否则,如果存在这样的子集,假设先手拿了一个子集异或为 $0$ 后,后手仍然可以拿一个子集使得异或为 $0$ 那么先手其实可以直接拿这两个集合的并。于是拿了一个极大的集合,后手就没异或为 $0$ 的可以拿了,回到了上一种情况。

所以,一旦开始存在一个子集异或为 $0$ ,先手必胜,否则后手必胜。

文章作者: yijan
文章链接: https://yijan.co/2020/11/08/1028-xie-ti/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog