历年NOIP提高组初赛问题求解大总结

虽然说是大总结，但总归没有全部都在上面持续更新中。。。。 ------------ ## 2005 1.将数组{32, 74, 25, 53, 28, 43, 86, 47}中的元素按从小到大的顺序排列，每次可以交换任意两个元素，最少需要交换___次。 2.取火柴游戏的规则如下：一堆火柴有N根，A、B两人轮流取出。每人每次可以取1根或2根，最先没有火柴可取的人为败方，另一方为胜方。如果先取者有必胜策略则记为1，先取者没有必胜策略记为0。当N 分别为100，200，300，400,500 时，先取者有无必 胜策略的标记顺序为（回答应为一个由0和/或1组成的字符串）。 第一题 把不在自己位子上的，暴力换到自己位子上即可，一共是5次 第二题 小学奥数。。。~~膜~~模3不余0就能必胜。 ------------ ## 2008  第一题 不多说，脑内最短路，多做几遍吧。。 第二题 这道题其实可以转化为排列组合的插空。。其实就是不管哪本书把4本书插到另外17本书之间，有几种插法，也就是有几种选法，答案是$C_{18}^4$=3060 ------------ ## 2009  画风突变有没有。。谁让洛谷出了初赛专用题库。。太好用了。 第一题 题目都告诉你是拓扑排序了，直接模拟一下。首先排出1 2 3 4 6，然后把7插进去，有两种情况分别是1 2 3 7 4 6,1 2 3 4 7 6，然后把5插进去，一共$2*6=12$中情况。然后。。。千万别忘了右边还有一个8和9。。。7个数一共8个空，选两个空，或者一个空插进去是$C^2_8+C^1_8=36$,然后一共$12*36=432$种。枚举大佬应该没有吧。。 第二题 这个。。洛谷题目不太对，四种货币是：1,7,49(7^2),343(7^3),震惊，洛谷的上角标被吃掉了。。然后手动算。。付款：$343*29+49+7*3=10017$，还2个一块钱。一共流通35张 ------------ ## 2010  第一题 不多说，直接暴力模拟就行了，答案“yyxy xx yyxy xyx xx xyx” 第二题 不存在由奇数条边构成的简单回路的图，其实就是二分图，于是，把这7个点分成（3,4）就行了，答案是12 第三题 自己有点说不清楚。。  ------------ ## 2013  第一题 这道题很水，首先我们可以从第5个问题轻轻松松的知道a1=0,然后我们代到第一个问题就可以知道a2=1，然后把a2代到3，就知道了a3=1，然后再代到2，我们就又轻松的知道了a4=1。所以答案就是0,1,1,1 第二题 ~~这只青蛙（蛤蟆 没事跳来跳去干什么真是的~~ 这种跳来跳去的题目我们依然用DP解决，我们用f[i]表示有i片荷叶跳到i平均要几次。那么f[1]=0,f[2]=2,f[3]=2.5,f[4]可以从1,2,3转移过来，$f[4]=(f[1]+1)*\frac{1}{4}+(f[2]+1)*\frac{1}{4}+(f[3]+1)*\frac{1}{4}+(f[4]+1)*\frac{1}{4}$,解出来$f[4]=\frac{17}{6}$,那么同理$f[5]=\frac{37}{12}$ ------------ ## 2014  第一题 首先我们可以把两个1和两个8单独拿出来。然后分情况讨论：1.四个数都取1,1,8,8那么显然，这种情况的排列一共有6种，其实枚举一下就可以了。 2.这四个数里面取三个，那么就有1,1,8和1,8,8两种情况，对于1,1,8排列一共有3种，然后插2或4情况有两种，插的位置又有4种情况，然后最后还要在乘个二，因为1,1,8和1,8,8是一样的，所以一共$2*3*2*4=48$种情况。 3.那么最后是四个里面有两个（只有一个显然不行），一共有（1,1）、（1,8）、（8,1）、（8,8）四种情况，然后处理插进2,4这两个数，先让前面定的两个数选位子是$C^2_4=6$，然后讨论2在前面还是4在前面，于是总共$4*6*2=48$ 于是，一共48+48+6=102种 第二题 手动跑spfa，最后跑出来，应该是这样的（数字代表最后的距离）A:0 B:3 C:4 D:12 E:15 F:5 G:4 H:7 I:11 注意，F可以经过A->B->C->F得到！这样跑出来要小，所以最后的答案是15而不是16。 ------------ ## 2015  第一题 这个么。。容斥原理。。。2015-（4的倍数的个数+5的倍数的个数+6的倍数的个数-20的倍数的个数-12的倍数的个数-30的倍数的个数+60的倍数的个数) -> 2015-(403+335+503-100-167-67+33)=1075 第二题 听说是一个叫卡特兰数的东东？那么如果您是暴枚巨佬，我就不多说了orz。然后我们看一下正常做法：用f[n]表示节点数为n的构成的不同形态的二叉树的种树，那么有这么几种情况：左子树节点个数为0，右子树为n-1；左子树节点个数为1，右子树为n-2；……左子树节点个数为n-1，右子树为0。所以说：$$f[n]=\sum_{i=0}^n f[i]*f[n-i-1]$$ OK，最后f[5]=42 ------------ ## 2016   第一题： DP大法好，用f[i][0]存i位为0的方案数，f[i][1]存i位为1的方案数，转移方程就分简单了f[i][0]=f[i-1][0]+f[i-1][1],f[i][1]=f[i-1][0]，最后算出来就是55啦 第二题： 很简单，凑一凑就好了，正确打开方式应该是dancing link，没错，但是随便凑凑也能凑出来啦。分组：1.通用，化学，政治 2.物理，历史 3.生物，地理 ------------ ## 2017  第一题 其实只用试试就行了。首先，最右边那个1肯定通过改变最右边那个0得到，改变自己显然不优。于是有四个1连在一起，我们显然改变最中间的，然后翻过来之后发现，只剩上面两个格子是1了，然后我们只用改变最上面的格子就行了。一共三次 第二题 这就是一道最小割，转化为求最大流即可，这题的最大流真是再好求不过了，显然是4。后一空的话。。搜了一下据说是什么最小割转对偶图？然而我看不懂对偶图是什么，然后于是就只能暴力数。。但事实证明数不对。。不管怎样答案是9。 好的，成功搞懂了这道题的正解。。 我们可以把这个最小割转化为求最短路，为什么是最短路？我把对偶图搞出来你就知道为什么是最短路了。 首先这个图是一个平面图，我们可以把图下面的平面当成s，图上面的部分当成t，就像这样：  然后再把边分割成的每一个平面都当做一个点，像这样：  是不是看出了一点端倪呢。。我们再把相邻的区块上的点连起来：  然后再附上边的权值，每条新的边的权值就是与它交叉的老边的权值，擦掉原图就是：  是不是知道了呢？没错！答案就是这个图的最短路，这个图就是原图的对偶图。选了一条边走，就相当于在原图上切掉与这条边交叉的边。这样第二空也就好求多了，我们只用统计出长度为4的路条数就行了，就好模拟多了。