NOI 二轮复习 II：构造与创造性思维

本文是 NOI 二轮复习的第二篇，介绍了有关于非传统题目的思考方式。

广义来说，所有问题都属于构造类问题——它们都需要构造解。

此类题目中也有较多 ad-hoc 题，需要我们从多个角度思考，发挥自己的想象力。

我们不能对于每道题都枚举所有套路逐一试错，而需要具体情况具体分析。不应当完全依靠猜或试找出来，而是主要通过线索推断出来。它们包括但不限于：

注意在做此类题目时，要避免自己陷入思维死局。

常见模型

一些问题常在特定结构上出现。

无向图的 DFS 树是没有横叉边的，可以根据此来完成一些题目。

「PMOI-4」可怜的团主。直接跑 DFS 树，如果叶子足够就直接构造（因为没横叉边），否则依次连边即可。代码。

图论相关的内容非常多，可以参见以下表格。

CF1444C。我们知道 $\sum \operatorname{deg}=O(m)$ ，因此内部判断完之后，直接枚举就是对的。

SNOI2024 拉丁方。考虑 B 性质怎么做。每个颜色向其没有出现的列连边，然后二分图边染色（染成答案），就是方案。一般情况，跑两遍即可。代码。

即之字形构造。

P9837 汪了个汪。所有的无序数对都要恰好出现一次，那么按照顺序填，按照无序数对的差分类即可。

Coprime Matrices。构造时直接将每两列按照之字形左右来回走即可，依赖 $\gcd(x,x+1)=1$ ，因此对于 $w$ 的处理偏移一下即可。代码。

可以去看《邓明扬，一类调整算法在信息学竞赛中的应用 2021》。简单来说，就是先任取一个合法解，然后对合法解进行微调使得权值变大，一直操作直到无法进行。

CF1168E Xor Permutations。转化为构造一个排列 $p$ ，使得 $p_i\oplus a_i$ 两两不同。直接使用调整法，随机一个还没有出现过的 $p_i$ ，如果有合法的 $p_i\oplus a_i$ 就直接填，否则随机一个拆掉。代码。

一些杂题。

一些题。

考虑对于正反面都分别连 $a\to -a$ ，那么如果一张牌入度为一出度为一则可以缩点，否则一定入度为二或者出度为二，出度为二必须出到相同的地方，否则无解。根据此直接构造即可，能证明这是有解的充要条件，可以参考官方题解。代码。

一些题。

直接扫一遍过去可以得到颜色数，然后可以二分答案，二分的时候每次可以排除掉一半以上的区间不再考虑，那么询问次数是对的。代码。