Ad-hoc专题

· · 个人记录

Ad-hoc专题

虽然Ad-hoc确实没有什么固定的套路，但是确实值得整理一下，毕竟确实很有意思啊！

[TOC]

AGC057C

我们设 m=2^n。

然后这里给个结论：合法的状态必须要满足 a_i \equiv a_{i+\frac{m}{2}}\pmod {\frac{m}{2}}。

这里解释一下为什么：

首先终点状态一定满足吧，然后我们讨论一下异或和加法的含义。

首先，异或，我们发现异或一个 a \geq \frac{m}{2} 和异或 a-\frac{m}{2} 是等价的，并且这个相当于将 m 个元素两两配对，然后交换，配对 x 和 y 的原则是 x\operatorname{xor}y=a。

然后看 +1 ，首先看异或两个数等价的那个结论，这无疑就是说 x 和 y 能交换，当且仅当 x \geq \frac{m}{2} 并且 y \geq \frac{m}{2} 或者 x < \frac{m}{2} 并且 y < \frac{m}{2}，那就相当于划分了两个等价类嘛其实，然后 +1 只会改变两个元素的所属等价类，即 m-1 和 \frac{m}{2}-1，其他元素的等价类都是没有变化的。

然后我们就发现，这两个操作无论如何都不会影响 a_i \equiv a_{i+\frac{m}{2}}\pmod {\frac{m}{2}} 这一性质。

然后我们贪心一下，即我们要最后满足 \forall i \in [0,\frac{m}{2}-1],a_i< \frac{m}{2}，因为满足这个情况后，剩下的都是两个等价类的内部调整了，只需要异或就可以完成。于是先处理麻烦的部分。

然后我们就从前往后扫，从 0 扫到 \frac{m}{2}-1，然后只要有 a_i\geq \frac{m}{2}-1，我们就让他跟 m-1 交换，这个可以用两次异或实现，借助 \frac{m}{2} 作为跳板，先交换 a_i 和 \frac{m}{2}，再交换 \frac{m}{2} 和 m-1，由于异或有结合律，这两个操作可以合并。然后最后用一个整体 +1 操作来使得这个 m-1 变成 0，然后让 a_i 跟 m-1 交换只需要用到异或，而这个过程中我们发现实际上，只会让两个等价类内部的元素进行两两交换，并不会影响下标在 [0,\frac{m}{2}-1] 之间的两种等价类的元素的数量。然后你可能有个问题，就是如果原来在 [0,\frac{m}{2}-1] 有一个 \frac{m}{2}-1 那 +1 后不就增加了一个 a_i \geq \frac{m}{2} 了？但是实际上并不用担心，因为保证了 a_i \equiv a_{i+\frac{m}{2}}\pmod {\frac{m}{2}} 了，那么 m-1 和 \frac{m}{2}-1 必不可能同时在 [0,\frac{m}{2}-1]。

最后满足了 \forall i \in [0,\frac{m}{2}-1],a_i< \frac{m}{2} 后，我们只需要对两个等价类内部进行一遍重排序就好了，由于有 a_i \equiv a_{i+\frac{m}{2}}\pmod {\frac{m}{2}}，我们只需要考虑一边即可。然后这个时候由于不需要改变等价类的数量了，也就是说这个时候只需要异或就够了！然后由于异或满足结合律，其实只需要异或一个数就可以了，这个数显然是 a_0，因为要让 a_0 变成 0。

CF1725L

真的太抽象了，我应该首先想到NOIP2021的方差的！

反正就是，我们注意到两个性质：

  1. 总和不变
  2. 重复做两次会抵消掉

往NOIP2021的方向去想，发现其实就是在交换两个相邻的前缀和啊，所以我们直接归并排序就做完了！然后无解的条件就是存在一个负数前缀和或者 sum_n 不为最小值，毕竟最后的两项是无法交换的。

809. 【UNR #7】那些你不要的

好好好，不知道为什么当时做这个题一眼看出来结论了。

而且这个题其实也不是很能算ad-hoc。

反正就是我们注意到一次一定是删去一个奇数位置的一个偶数位置的，最后留下来的一定是个奇数位置的，那答案显然就是比较大的中位数。