【NOI 9】交互、构造与通信

# 构造、交互与通信题 构造交互通信这三类题型作为非传统题的代表，越来越多地出现在了国内的正式比赛中。如 NOIP2022 T3（构造），WC2022 T3（交互）。通信题虽然因为考点原因，只能出现在 CTT 与 CTS 的比赛中，但其很多的方法与构造交互是相通的，因此我们将其放在一个专题中学习。 在进行此类题目训练的时候，首先要掌握好各种常见模型的实践。此外，此类题目中有较多 ad hoc 的题目，需要我们从多个角度思考，发挥自己的想象力。 ### 三类题目的关系 1. 某些交互题的解决方法就是构造方案。 2. 某些交互题需要我们从信息的角度出发来考虑问题。 ### 抽屉原理 1. 在构造题中，若我们遇到了 $n/k$ 这样的操作次数的时候，可以考虑将所有数划分为 $k$ 个集合。这样，最小的那个集合的大小就一定小于等于 $n/k$ 了。 2. 例题：CF1198C，CF1534D，CF1450C2，[gym102900B](https://codeforces.com/gym/102900/problem/B)。 ### 归纳法 1. 考虑找到有解的充要条件，然后试图将原问题转为规模减一的一定有解的子问题。 2. 例题：CF1470D，CF1515F，ARC122E，P6775，P8553，[gym101221A](https://codeforces.com/gym/101221/problem/A)。 ### DFS 树 1. 例题：CF1364D，P5811，CF1391E。 ### 转化到图 1. 将我们要找的东西转为图上的一个环，欧拉回路；或者转为 2-sat 或二分图染色问题。 2. 例题：CF1270G，CF1404D，AGC018F，[uoj669](https://uoj.ac/problem/669)，[uoj670](https://uoj.ac/problem/670)。 ### 最优化与交互 1. 如果我们想要通过询问确定是哪一种情况，就可以用下面的方法。一般，这样的题中，交互库都是自适应的，并且甚至可能还要求你先求出最小操作次数。 一般的考虑方法是：考虑维护当前可能是答案的情况构成的集合。我们对于每一种集合，求出它的最小询问次数。转移便是对于每一个集合的每一种询问，根据答案可以得到该集合的一个子集。我们要找到这样的询问：它对应的每一种答案得到的新集合的询问次数的最大值最小。 为了找到这样的集合，我们可以直接使用 dp。事实上有时候最小询问次数只和集合大小有关，那么我们 dp 的时候就可以只记集合大小。此时注意可以结合 dp 的各种优化方法来解决问题。 除了 dp 以外，我们还可以用二分等方法近似地得到一个询问的方法。 2. 例题：P7998，CF1746E2，CF1534H，[uoj52](https://uoj.ac/problem/52)。 ### 二进制分组 1. 这一类问题一般询问次数较少，每次问 $n$ 个数的一个子集，需要你确认 $n$ 个数分别是多少。方法是，为 $n$ 个数分配不同的长为询问次数的 $01$ 串，第 $i$ 个为 $0$ 代表这个数在第 $i$ 次询问不被问，反之被问。 有时候，你的算法需要保证每个数被问到的次数一定。设最大询问次数为 $q$，那么你最多就可以确认 $\binom q{\lfloor q/2\rfloor}$ 个数是多少。可以据此分析数据范围，确认是否是这个做法。 2. 例题：CF1365G，[uoj751](https://uoj.ac/contest/78/problem/751)。 ### 随机化 1. 随机化有两种，一种是操作次数一定，正确性与进行的轮数有关，检验其正确性的方法是：检查正确与否是否之和自己的随机过程有关。另一种是操作次数是带有期望的，这一点需要数据不能是自适应的。 2. 例题：CF1562F，CF1765G，CF1364E，P7597，[uoj454](https://uoj.ac/problem/454)。