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