CF 构造，交互，博弈题总结
CF 构造，交互，博弈题总结
以后 CF 上的构造，交互，博弈题就放在这里了。题目总结 更倾向于一些阳间传统一点的题。
板刷 CF 计划（。因为蒟蒻太蒻，只能做 *2000 到 *2500 之间的题。
CF521D Shop
设 (opt,x,y) 为一次操作 ，首先考虑只有 3 操作的情况。因为要求的是 ∏i=1nai，那么不难发现乘在哪里都是一样的，所以把所有的值从大到小排序就可以了。
然后我们不难发现一个性质：所有操作必然是先 1，再 2，再 3 的。
这启示我们把 1 操作和 2 操作也转换成 3 操作（即乘上一个数）。
先考虑 2 操作。对于同一个下标 x，对他进行的操作必然是要从大到小操作的。那么不妨先从大到小排序。每次操作 (2,x,y)，那么就算出这次操作前下标为 x 的值 sum，那么这次就相当于乘了一个数 sum+ysum，这样就转换成操作 2 了。
那么操作 1 呢？首先，对于每个数，我们只需要找到最大的操作 1，设为 (1,x,y)，然后就可以把这个操作转换成 (2,x,y−ax)就可以了。
然后把所有乘起来的东西从大到小排序。找到前 m 个就可以了。
但是，这样子就可能做不到 1→2→3 的顺序了，怎么办呢？实际上，因为乘法满足交换律，对于前 m 个操作，我们再对于 opt从小到大排序就可以满足了。
code。
CF1217D Coloring Edges 构造题。
不得不说我构造题真的啥都不会/kk。
不难注意到如果没有环，那么全部设置为 1 就可以了。
那么如果有环呢？答案至少为 2。同时我们可以大胆猜测答案就是 2。
然后怎么构造呢？不难发现，把每个点当成高度，那么一个环必然由上升的连线和下降的连线组成，其中一个设置成 1，另一个设置成 2 就可以了。
但是好难想啊qwq，大概是我太菜了吧>_<。
代码太太太简单了，就不放了。
CF1470D Strange Housing 构造。
vp 的时候被这题打爆了，绿题都不会做了。（虽然 CF 上评分是 *2200，我觉得应该蓝的）。
考虑一种很野蛮的构造方法：首先如果图不连通输出 NO，否则对图进行染色，1 表示选 2 表示不选。遍历到点 u 的时候，如果点 u 没有被染色过，那么把 u 染色成 1，并且把所有与其相邻的点染成 2。然后再遍历与其相邻的点。
看起来非常不正确是不是？然而这是合法的。为什么呢？首先，显然这张图不会有两个 1 相邻的情况。并且，题目要求在所有连接两个不被染色的点的边都被删除的情况下，这个图满足任意两个点互相可达。此外，每次染色一个新的点的时候，必然可以与之前的一个已经染色的点联通，用归纳法就可以证明整张图是联通的。
此题虽然是 div2 F 题，但是实际难度并没有那么高。我 vp 的时候一直在想所谓 “高明的贪心”，于是就没有想出来。这也启示我们要勇于暴力瞎构造，说不定就对了呢？