省选以及全国赛2016省队集训命题思路

LYK是谁命题思路——alpq654321提交答案题在网上看中某个游戏。例如：连连看，对对碰，斗地主，angrybirds。这些一般没有多项式做法。(angrybirds除外)由此来出有数据特点的提交答案题。衍生出来的题目：消消看。提交答案题提交答案题为什么要给你测试点？因为问题本身需要在一定地特殊条件下才有解。测试点特征提交答案题要有什么?LYK说要有DP。LYK说要有爆搜。LYK说要有模拟。LYK说要有贪心。LYK说要有乱搞。LYK说要能拿到分数。LYK说要防AK。衍生出来的题目以消消看为例。通常在第一个测试点是让选(wan)手(jia)适应该提交答案题。因此大部分提交答案题（例如消消看，排序卡排序，NOIP十合一等）的第一个测试点较为简单。选手在10min内手玩即可出解。接下来的测试点接下来的测试点设计见题目而异。就提交答案题来说，大致可以分为三种。1：数据分析类题（例如消消看）。2：在特定条件下的构造题（例如排序卡排序）。3：XJB题（例如NOIP十合一）。根据不同的提交答案题设计不同的测试点。第一类题以消消看为例。显然是不会存在多项式做法的。那么我们要设计测试点，使得它存在多项式做法。我们显然可以在每行/列分开、每个联通块分开、颜色个数以及分数上做文章。分类讨论假设我们要在行列分开上作文章。观察1行n列是否存在多项式算法来消消看。衍生出了测试点9。假如不考虑合并呢？衍生出了测试点7。分类讨论假设我们要在颜色个数上作文章。仍然没有多项式做法。怎么办呢？我是出题人啊！不要分数不就行了！变成一个爆搜问题不是挺好！衍生出了测试点4和5。分类讨论在每个联通块上作文章。我们考虑三种情况。1：消除所有联通块都不会导致其余方块移动。2：消除联通块后使得大联通块变成小联通块由此来获得高分。3：消除小联通块使得联通块合并到某个特定的值。对于第一种情况，衍生出了测试点2与8。对于第三种情况，衍生出了测试点10。事实上对于测试点2仍然可以加入分数。（但并没有什么用处，因为联通块大小是固定的）对于第二种情况，我想过很多构造方法，仍然没有得到一个较好的测试点，有兴趣的同学可以联系我。分类讨论这样我们已经设计了8个测试点了。考虑以消消看的模型来解决其余问题。脑洞1：通过消消看来设计网络流问题。脑洞2：规定一个大小，只有当删掉刚好这个大小的联通块时才能得到分数。脑洞3：用消消看模型来解决某经典OI问题。（事实上测试点7就是经典OI问题）脑洞4：如果该矩阵是黑白矩阵，那么……脑洞5：每次在原矩阵中插入一个联通块，然后还原每次操作。……脑洞x：……第一类题由这些脑洞衍生出了测试点3、6。一道精彩的提交答案题肯定是通过出题人不断地脑洞得到的。第一类题设计连连看问题：在一个n*m的矩阵中每次消两个颜色相同的方格，拐弯次数不得超过k。讨论时间各种脑洞脑洞1：颜色数量较少。脑洞2：每次在当前图上插入两个能连的点。脑洞3：加入分数概念，即每连续两次消除同种颜色的点能获得分数加成。脑洞4：每行/列互相独立。脑洞5：像消消看一样每次消除会导致方块往某个方向移动。脑洞6：设计方案使得最终无法再消除且剩下的个数最多。……脑洞x：……第一类题设计俄罗斯方块。一个n*m的矩阵，每次从高空掉下来一个某个形状的方块，某一行如果全是方块就会被消除。设计方案使得……讨论时间各种脑洞脑洞1：9*9的矩阵，从高空先下来一堆2*2的矩阵，再下来一根非常长的东西，恰好可以消光。脑洞2：随机出现一些形状的方块，尽量撑得久一些。脑洞3：一次性消除行越多分数越高。脑洞4：要求一次性消除x行才能得到分数。脑洞5：越早挂掉越好…………脑洞x：……第二类题以排序卡排序为例。观察所有排序的性质。考虑每个排序对哪些数列是有优势的。两两之间作比较。设计优秀的测试点。构造题对于构造问题，往往是出题人更为出色的脑洞。我们来尝试着出这样的题。构造题问题：给定n个数，接下来有Q组询问，每组求一段区间的最小值。设计解决方案。讨论时间一些方案ST表。(nlgn-1)线段树。(n-lgn)奇怪的树状数组。(nlgn-nlg2n)分块。(n-sqrt(n))莫队。(QlogQ-sqrt(n)log(n))整体分治。(n-lgn)贪心。(n-n)……观察性质接下来就是观察所有方法的特性了。例如在贪心算法中，若数据随机，则可以做到(n-lgn)。构造有趣的测试点。期待大家出这样的题目。第二类题当然对于构造题来说不一定是像这样的某个算法卡另一个算法。在昨天讲的课件中的脑洞是我现在所不能及的。如果那些题目不存在靠谱的多项式做法，那么就可以通过提交答案题，设计一些特点来达到效果。第二类题我曾经出过的构造题。已知合并果子的答案为k。构造n个数，来得到这个答案。n<=10W，ai<=10^9，k<=10^18。然而至今我还不会做这个题目。第三类题NOIP五合一。NOIP十合一。NOIP百合一。NOIP千合一。传统题的命题思路DDD：选择一个经典算法，将其中的某一步打乱，得到一道新的题目。在DDD的集训队胡策题目中，应用这种命题思路，在经典的后缀数组求height中，将sa数组打乱，得到新的height数组。在该height数组中做文章。传统题的命题思路命题优势：命题较为轻松，且题目看上去变得不是那么简单。命题劣势：当选手深入观察后了解其转化后的模型，往往会发现该模型非常简单或者十分经典。通过这种方法要命一道好的题目并不容易。传统题的命题思路那么如果我们在经典题上加以扩展呢？经典的LCS问题。加以扩展。已知一个串s与LCS，求另一串的方案总数。没有多项式做法。那么我们规定LCS=|s|-1呢或者n较小呢。问题变得简单化。传统题的命题思路先在脑海中想好这个题的基本模型。例如是一棵树，一张图还是一个序列。在这上面做一些文章。树上的命题思路：树套小树，深度为一段区间的点，区间LCA等。图上的命题思路：每条边以某个概率生成，每次以一定概率走某条边，缩点等。序列上的命题思路：一段区间，每等差数列位置的区间，a{b{i}}与b{a{i}}构成树套环等。辅助工具：gcd，max，期望，mex，sum等。命题中最重要的事你是出题人！你是出题人！你是出题人！你是出题人！你是出题人！你是出题人！你是出题人！你是出题人！传统题的命题思路当你想到一道好题，却不知从何下手时，不妨将其简化。如果是一段序列，不妨将其随机。如果是一棵树，不妨将其随机。如果是一个矩阵，不妨将其变成黑白矩阵。如果是一张图，不妨将其变成二分图。甚至你可以指定一些特殊条件。（例如树的叶子个数，图的点的度数，每个数的大小等）传统题的命题思路当走上命题的不归路时。千万要注意一点。当你出的题影响他人前途时，仔细斟酌，作一个能回报社会的出题人。论偏题的危害此处会提(hei)到很多著名OIer和已退役OIer，接下来的内容以白色字体展示。论偏题的危害论偏题的危害论偏题的危害详见popoqqq的WC论文。尝试着命一道题一些备选材料：背包问题，LIS问题，LCA问题，LCS问题，RMQ问题，树上问题，图上问题。讨论时间一些例子假如我已知LIS是啥，求方案总数。找不到多项式做法。状压dp！可以做到n<=15。一些例子假如背包的容量非常大。没有什么好的做法。但是物品的价值较小呢？改变dp状态，十分easy。出题的好处由于在CTSC前我出过一道提交答案题，在CTSC中的两道提交答案题中，均看出了所有测试点的特征。一个靠谱的例子：张地主：“由于我比较弱，最后一个测试点肯定是最难的，不知道怎么加强，那我把所有点的编号random_shuffle一下，就加强了很多。”naive！出题的好处设身处地的在出题人身上考虑。一道题目之所以被出出来，一