2023年7月30日发(作者：)

历年NOIP选题题解汇总　　联赛前上vijos板刷往年联赛题，使⽤在线编辑编写代码，祝我rp++。　　废话不多说，挑⽐较有意思的记⼀下。　　题⽬是按照年份排序的，最早只到了03年。　　有些题⽬因为 我还没写/很早之前写的忘了 所以就没写题解。

　　NOIP2003　　神经⽹络：按照题⽬怎么说怎么做，BFS即可。注意输出层是指出度为0的层，不是指深度最⼤的。　　传染病防治：爆搜题，枚举每⼀层减掉哪个。复杂度不可算，理论在O(2^30*8!)左右，但好像强势不满。想了⼀会貌似卡不掉？

　　NOIP2004　　⾍⾷算：知⼆推三，边搜边判。

　　NOIP2005　　篝⽕晚会：⾸先你得知道两个排列可以看成若⼲个环，⽽且每个点只要转⼀次就可以转出来……⽽这题正好是两个排列的形式，即找到⼀个1-n的环和原环匹配最多就是不要动的⼈。把每个⼈在环中的1的位置记下来取最多的就好了。　　过河：把边权>=100的缩成100，因为长度过长没有意义，⼤于100了前⾯的情况必然可以凑出来，然后在1000下暴⼒DP即可。注意特判S=T的情况，还有不要以为给出的点都在L内。　　等价表达式：随便找⼏个数字(1~20)带进去算在模意义下都相等就可以了(跟解⽅程的思想有点像？)，重点是化为后缀表达式处理的trick。

　　NOIP2006　　2^k进制数：⼤整数组合数。

　　NOIP2007　　先坑着

　　NOIP2008　　传纸条：显然的⽹络流，其实化为四维DP可做。　　双栈排序：若存在iA[j]，即A[j]在A[i]前⾯弹栈。因为A[i]最终也要出栈，所以⽐A[i]还要⼤的、在[i,j]中间的⼀定不能和A[i]在同⼀个栈中，即构成⼆分图。判断有解就是⼆分图染⾊。输出……反正我铁定WA的输出因为数据⽔过去了，不予置评。

　　NOIP2009　　Hankson的趣味题：醉题，复杂度O(nsqrt(B)logB)但是跑得过？反正我是不会什么更好的解法……　　最优贸易：SPFA求出从1出发能买进的最低阶，从n出发沿反向边能卖出的最⾼价，最后枚举边减掉就好了。　　靶形数独：裸搜貌似有90？然后从已知信息最多的那个⾓落搜有100？还有很多剪枝就懒得加了(最优性啊之类)。

　　NOIP2010　　关押罪犯：10年前的NOI题弱化版，⼆分答案+⼆分图染⾊/直接并查集补集都可以过。　　引⽔⼊城：搜索处理覆盖线段，贪⼼/DP回答区间数量问题。　　乌龟棋：强⾏四维存个数的⼀眼DP。

　　NOIP2011　　计算系数：考你会不会杨辉三⾓。　　聪明的质检员：数学直觉+⼆分答案。　　观光公交：不知道为什么是对的贪⼼，然后O(nk)跑得过。题解的话。

　　NOIP2012　　国王游戏：套路贪⼼，强⾏⾼精。　　开车旅⾏：码量较⼤，set寻找下⼀步后倍增，注意最后⼀步的细节。　　借教室：⼆分答案+差分看是否合法(线段树卡常好题)。　　疫情控制：贪⼼神题，到根后尽量⼩的匹配⼩的。

　　NOIP2013　　⽕柴排队：⾸先肯定是rank x对 rank x，然后就是⼀个交换问题。因为⼀次交换可以且仅可以减少⼀个逆序对，⽽最终序列没有逆序对，所以求出逆序对数就可以了。　　积⽊⼤赛：治各种学傻。求出右－左的差值⼤于0的数的和即可(⾃证)。　　花匠：简单DP或者直接找拐点。　　华容道：毒瘤题，把65分的求最短路给预处理出来跑SPFA即可。

　　NOIP2014　　联合权值：乘法分配律逆过来推，记得答案×2。　　飞扬的⼩鸟：向上完全背包，向下0/1背包，细节巨多巨恶⼼。　　寻找道路：先反过来BFS⼀遍，找到符合题⽬要求的点，然后直接BFS找最短路即可。

　　NOIP2015　　⼦串：f[i][j][0/1]表⽰A到了i，B到了j，当前失配否的量，转移就很显然了。　　 　　NOIP2016　　不太想写，⽣⽓。

　　NOIP2017　　不想写，⽣⽓。

　　(坑先留着)