思维与构造题 做题总结
0. 前言
前几天听了你谷网课提高组的课，身心俱疲收获颇多。其中本蒟蒻作业完成度最好的就是Day3的构造题。由于做的这几题都算是比较有难度和代表性，于是my决定写一篇总结！
1. 什么样的题叫做思维题
实际上需要思考的都叫思维题。
思维题，顾名思义，即更注重思维的考察，一般码量不会太大，前提是您能想出正解。
这种描述您是不是马上想到了DP？没错，DP即为思维题的一类，但是由于DP的种类极为庞大，特性极为特别，于是可以单独作为一类题型。
2. 什么样的题叫做构造题
构造题也是思维题的一种，但因为其非常好玩有特点，可以单独拿出来讲。
构造题的特点非常鲜明，字眼有以下几个：
- “请你构造一种方案”
- “若有多种方案，输出任意一种”
- “是否有这样一种可行的方案”
等等诸如此类的玩意。
但也有些题不是这样明显。
由于构造题的特殊性，出现以上字眼的原因想必不用我多说。因此构造题一般都会带SPJ。（至少我做过的题都是这样）
但是不排除没有SPJ的可能性，有以下几种
- 对于方案的构造，输出是否可行或最终答案即可，并不要求输出如何构造（不需要SPJ）
- 毒瘤出题人认为正解只有一种，而且抠出了所有拿部分分的可能性并且给了暴力应得的分数（不想写SPJ）
其他的可能性由于作者并没有做过太多这类题，外加想象力的限制，无法列举出来。做过这样的题的童鞋欢迎推给作者，我会在更新这种可能后将您的uid作为鸣谢名单放在文章顶部。
3. 来看看题吧
注：以下列举题目的难度均为标题的颜色，且标题均为指向题目的链接。建议读者仔细阅读思考后做题，没有思路再看作者提供的题解，具体见下。
下面来看一道非常相似的题。
这题与上一题是非常类似的。棋盘由一维到二维，棋子由两个变为一个。
感觉完全不一样了好吧。
但是思路非常一致。
首先这两个人都绝顶聪明，他们一定会想办法把对方逼死或者让自己活的时间最久。
所以您可以感性理解为他们一定会把棋盘整个都走一遍。
于是谁是走最后一步的？那个人就是赢家。
那么显然如果是奇数轮次，先手方胜，反之后手方胜。
于是问题转化为游戏会进行几轮，显然有n个格子，就会进行 n-1轮，因为有一个格子已经被占。
那么n的奇偶性是一致的。于是如果n为偶数，输出先手的Alice，否则输出后手的Bob。
是不是感觉很容易呢？接下来可就没那么容易了。
\color{green}\text{CF1385E Directing Edges} 题解\color{blue}\text{CF161B Discounts} 题解\color{purple}\text{AT2043 [AGC004C] AND Grid} 题解\color{blue}\text{P4665 [BalticOI 2015]Network} 题解\color{grey}\text{CF717E Paint it really, really dark gray} 题解\color{purple}\text{CF45G Prime Problem} 题解（xgf神推荐）\color{blue}\text{AT2665 [AGC017B] Moderate Differences} 题解\color{black}\text{CF618F Double Knapsack} 题解
4.总结
- 构造题基本不需要看输出样例，自己手动看一下是否符合要求即可。毒瘤的出题人一般不会给您正解的输出的。
- 正难则反，考虑有解/无解的情况往往对无解/有解情况的求解有启发。
- 对于某些不知道有没有可能无解的题，大胆猜测一定有解。不要上来就骗分输出无解。
- 注意多组数据的细节处理和边界情况带来的启发。
- 尝试证明答案的上/下界然后对着构造。
- 留心题目中不起眼的一些话，可能会提示做法。
- 尽量对题意进行转化和构造比较可做的方案，使题目变得友好。
希望这篇文章对您学习OI有帮助，能够给您一些启发。
谢谢阅读！
都看到这里了，还不点个赞吗/kel？
球球了