一些好题

- [P3034](https://www.luogu.com.cn/problem/P3034) 不是很常规的题目。 考虑奶牛之间的相对位置。因为一头奶牛最多跳出来一次，所以两头奶牛的相对位置最多改变两次。这样就可以求出任意两头奶牛的相对位置。 这样的话直接自定义一个比较奶牛的函数然后 `sort` 一遍就好了。 --- - [P7446](https://www.luogu.com.cn/problem/P7446) 相当妙的一道题。 因为这是 Ynoi，所以考虑分块。将 $1-n$ 的序列进行分块，设块长为 $\sqrt n$。由于一个点的所有祖先的编号都小于这个点，所以维护一下每个点的第一个 **不和自己在同一个块内** 的祖先 $f$。这样查询 LCA 可以通过类似树链剖分的方式做到 $O(\sqrt n)$。 再考虑修改。一个块被修改 $\sqrt n$ 次后，块内每个点的父亲都必定不在当前块内。因此每个点的 $f$ 值就是父亲。于是每个块经过 $\sqrt n$ 次修改就可以直接打懒标记了。那么对于这 $\sqrt n$ 次修改，考虑 $O(\sqrt n)$ 暴力重构 $f$ 值。这样 $\sqrt n$ 个块，每个块至多被 $O(\sqrt n)$ 地重构 $\sqrt n$ 次，这部分的复杂度就做到了 $O(n\sqrt n)$。 总的时间复杂度为 $O(n\sqrt n)$。 lxl 难得良心一次，本题完全不卡常，代码也很短。 --- - [P5046](https://www.luogu.com.cn/problem/P5046) 因为这是 Ynoi，所以考虑分块。预处理出 $ansl_{i,j}$ 表示第 $i$ 块的左端点到 $j$ 这个区间的逆序对数，$ansr_{i,j}$ 表示第 $i$ 块的右端点到 $j$ 这个区间的逆序对数。预处理的时候用树状数组维护一下，即可做到 $O(1)$ 地移动端点。 查询时把区间分成左散块、右散块和中间完整块。用 左散块和中间完整块组成的区间 的逆序对，加上 右散块和中间完整块组成的区间 的逆序对，减去中间完整块的逆序对，再加上左散块对右散块的贡献即可。 显然前三个东西都是可以直接利用 $ans$ 求的。而最后一个东西，只需要在预处理的时候保存块内排序的结果，然后归并扫一遍即可。 时空复杂度均为 $O(n\sqrt n)$。 本题卡常，考虑 IO 优化，再瞎调块长，卡卡过掉了。 ~~但不保证任何时刻都能通过此题。~~ --- - [P4375](https://www.luogu.com.cn/problem/P4375) 感觉 USACO 思路奇葩的题目相当多啊。 考虑把数组从 $a_x$ 和 $a_{x+1}$ 中间劈开，划分成 $AB$ 两个部分。易知每次冒泡之后，$A$ 中都**有且仅有**一个数跑到了 $B$ 里面去，$B$ 也**有且仅有**一个数跑到了 $A$ 去。因此将最小的 $x$ 个数全部放到 $A$ 里面所需的冒泡次数，就是**原本在 $A$ 但需要去 $B$** 的元素的数量。显然这个东西可以树状数组搞。 那么枚举 $x$ 的位置然后取个 `max` 就好了。 --- - [P4139](https://www.luogu.com.cn/problem/P4139) 设 $2^{2^{2\cdots}}=x$，显然 $2^x\equiv x\pmod p$，因此只需求 $2^x\bmod p$ 即可。根据欧拉定理， $2^x\bmod p=2^{x\bmod \varphi(p)+\varphi(p)}\bmod p$，所以求出指数，再快速幂就解决了。问题转化为求 $x\bmod \varphi(p)$。 可以发现，从求 $x\bmod p$ 转化为求 $x\bmod \varphi(p)$，这是转化为了一个 **规模更小，但形式相同** 的问题。因此可以考虑不断递归下去。 递归边界为 $x\bmod 1=0$。 来分析一波时间复杂度。每次将 $p$ 取 $\varphi$ 后，奇数会变成偶数，而偶数至少会减半，因此递归层数的上界为 $2\log p$，再加上快速幂，单次询问的复杂度即为 $O(\log^2 n)$。 --- - [P2827](https://www.luogu.com.cn/problem/P2827) 我真是个 SB，，这么 naive 的结论没有想到。退役了退役了。 一个显然的想法是维护一个堆，但是会 T。 考虑如果蚯蚓 $a$ 比蚯蚓 $b$ 先被切掉，那么 $a$ 分成的两条蚯蚓也一定分别比 $b$ 分成的两条蚯蚓长。这相当于自带单调性。因此可以把堆扔掉了。维护三个队列，第一个放还没被切过的，第二个放被切过的蚯蚓左段，第三个放被切过的蚯蚓右段。然后取最大值的时候只要比较三个队头了。蚯蚓的生长打个标记就好。 --- - [[Violet 4]迷路的兔子](https://hydro.ac/d/bzoj/p/2717) 显然答案为 $C_n^2$。接下来考虑构造。 对于每一对 $(i,j)$，都让兔子 $(j,j+i,j+2i)$ 出去站岗一次。手模一下发现这样可以使每一对兔子都恰好一起出去 $3$ 次。 --- - [CF1746F Kazaee](https://codeforces.com/contest/1746/problem/F "CF1746F Kazaee") 发现平凡的数据结构没有办法做，于是考虑随机化。 考虑哈希，给每一个数随机映射为另一个数，对每一个询问，判断这个区间的所有数的映射值之和是否为 $k$ 的倍数。 在这个策略下，`YES` 不可能被错判成 `NO`，而 `NO` 被错判成 `YES` 的概率大致为 $\frac{1}{k}$。于是做 $x$ 遍这个判断，单次询问出现错误的概率可以做到 $\dfrac{1}{k^x}$。这里设 $x$ 为 $40$ 是可以过的。 --- - [CF1848F Vika and Wiki](https://www.luogu.com.cn/problem/CF1848F) 简单题，但是牛逼题！ 设 $f_{i,j}$ 表示 $a_i$ 在第 $j$ 次操作后的结果，那么手模一下可以发现： $$f_{i,j}=\oplus_{k=0}^j(\binom{j}{k}\bmod2)a_k$$ 接下来涉及到一个很牛逼的结论，$\binom{n}{m}$ 为奇数当且仅当 $m$ 在二进制表示下是 $n$ 的子集。证明考虑 lucas 定理即可。 所以当 $j$ 是 $2$ 的次幂时，有 $f_{i,j}=a_i\oplus a_{i+j}$。 那么直接倍增就做完了。 时间复杂度 $O(n\log n)$。 --- - [CF329C Graph Reconstruction](https://www.luogu.com.cn/problem/CF329C) 首先显然有非常傻逼的分类讨论做法，但极难写。 考虑在新图中不能出现的边很少，所以一张随机图有很大概率是合法的。那么我们直接多 shuffle 几次整个序列然后 check 即可。 --- - [CF1909E Multiple Lamps](https://www.luogu.com.cn/problem/CF1909E) 非常幽默的诈骗题！ 考虑当 $n\ge 20$ 时，把所有开关都按一遍，最后亮着的灯数量为 $\sqrt n\ge \lfloor\dfrac{n}{5}\rfloor$，符合题意。 当 $n<20$ 时，爆搜即可！ --- - [[AGC040C] Neither AB nor BA](https://www.luogu.com.cn/problem/AT_agc040_c) 要简洁地刻画原题中的这个事情非常困难，考虑转化！ 容易发现在消除的过程中任意元素的位置奇偶性不变，所以考虑把所有奇数位置的 `A` 都变成 `B`，这样的话条件就变成了不能选 `AA` 和 `BB`！ 这个等价于整个序列的绝对众数不能是 `A` 或者 `B`！ 然后枚举绝对众数的出现次数就做完了！