NOIP2011-2018口胡题解

· · 个人记录

看不懂不能怪我系列

2011：

1.铺地毯:简单模拟，也可以二维梳妆数组||线段树
2.选择客栈:采用聪明的暴力，属于考场上的乱搞型题目呢

3.Mayan游戏:一般这种搜索题要么当场1A要么完蛋保龄注意细节dfs考场上A是有可能的+对自己的启发搜索不要过一层(血的教训啊)

4.计算系数：可以通过找规律配合上高二数学基础推导柿子，知道组合数的基本套路和快速幂就可以A

5.聪明的质检员:这题看出来那个奇葩的柿子表达的含义是一大难关，如果推导出来，二分的难度真的就不大了

6.观光公交:比较困难的贪心,主要模拟贪心过程对这一题恶心

2012：

1.虽然我没写过，但是应该比较脑残

2.国王游戏:这个题需要打表找性质或者手玩数据找规律,再使用高精度,还是要说很难打,高精度除法一次没写过..

3.开车旅行:三个难点1.找到最近次近的点在nlogn复杂度内,2,倍增的思路完全清晰3.代码

4.同余方程:exgcd推柿子后食用，注意求出来的不直接是x最小正整数解

5.借教室:无论是代码还是思路都比国王游戏直接的题，差分+二分求最近满足要求询问的点就能A，线段树可搞90，或许也能A

6.瘟疫控制:二分后倍增，细节死多，十分恶心，建议没有3小时别碰这种玩意,不过现在我应该能1小时解决了

2013:

1.转圈游戏:快速幂基本裸体

2.火柴排队:用正序逆序和之后证明可以用逆序对搞搞

3.货车运输:krustal+倍增，思路有不难打

4.积木大赛:观察性质或者贪心分治都可以搞，分治可以用st表稳定复杂度

5.花匠:设f[x][0/1]表示上升下降最长的就可以转移

6.华容道:不太会,话说小时候华容道我玩的就不好..不过我们还有骗分啊..

2014:

1.生活大爆炸版石头剪刀布:傻子模拟，不过我记得我是在机房打的这一题诶，嘿嘿

2.联合权值:可以用树形dp做，如果学过这个就是傻子题，也可以发现一些贪心性质和数学性质更傻的来做

3.飞扬的小鸟:搜索可以调到很高很高的分,也可以对列与行dp，把列当成背包容量，每列分层dp，注意顶到头边界情况

4.傻子题

5.寻找道路:用一种图论中十分常见而套路的反向连边搞搞

6.解方程:只要你敢，而且不怕数学题的表皮，就可以用读入优化哈希解决,这题真SB

2015: 1.神奇的幻方:傻子模拟

2.信息传递:会tarjan的兄弟上tarjan，会爆搜的同学也可以得到60或者100分，看自己的模拟能力

3.斗地主:100行级别搜索,建议确立搜索框架(dfs参数，return不return等)后再写

4.跳石头:noip第一次的二分答案类型题诶

5.子串:比较难的dp,需要反复想转移,不能陷入思维漩涡，需要滚动数组

6.运输计划:思维难度比子串容易，代码比较难，大概是树上差分+lca+二分答案，常见树上noip级别的东西基本都考了

2016: 1.玩具谜题:傻子模拟X3

2.天天爱跑步:比较难，还没正式打过，不过桶上差分的思路确实比较奇葩

3.换教室:看穿期望的本质就是概率乘价值后就可以序列dp解决

4.组合数问题:二维前缀和与C的递推

5.蚯蚓:只会priorityqueue做法，数组做法调死了,大概是插入弹出中维护一个控制蚯蚓成长的变量

6.愤怒的小鸟:状压或者搜索，不过都需要卡常，其中搜索没有特别好的写法怎么卡都是85(我的经历)

2017: 1.小凯的疑惑:当时我考场上被这个题恶心坏了，我的心里和潜意识都停留在傻B模拟的状态，结果出了这种东西，要是高一noip分不是只有5分的话，可能我已经随便进队了，不说了，该死.这题知道结论上结论，不知道的知道找规律套路的也有很大可能切掉，暴力只有45pts，很恶心

2.时间复杂度:考场上题都没看明白，只觉得自己考试的时候天旋地转，实际上是模拟，不过那时候我也不可能能写绿色的模拟题，大概是80行级别的模拟

3.逛公园:各方面都比较"艰难"的题,部分分只有30,预选省队型题目，首先想一个对每一个点拆k个点的dp，转移比较困难，我觉得可以正向dfs中排序搞一搞，0环的分可以通过tarjan搞一搞

4.奶酪:dfs题,有一定拓展意义，比如我班主任那题

5.宝藏:包括且不限于，dfs+强力剪枝|状压子集dp|模拟退火乱搞|我写的傻子多次贪心取最值

6.列队:30模拟,50离散化也就是聪明一点的模拟,80梳妆数组|splay|segment-tree 100动态开点线段树可以直接上，梳妆数组需要复杂的乱搞算法搞过100000*100000的数据，splay可能也可以搞

2018: 1.同noip2013D2T1

2.货币系统:考虑最少组成在2,3等情况，发现只要组成就可以删掉，所以完全背包直接上，考场上想了好久，没这题一等就没了

3.赛道修建:二分答案后手玩可以发现贪心性质,双指针或set一上就没了

4.旅行:第一次考基环树,拆环再对于树部分贪心做，取字典序最小，不过注意dfs中剪枝，否则只有88

5.填数游戏:这个搜索十分难打,但只要打出来敢于找规律就有65+的好成绩，不行也可以手动找规律，到2个人觉得没问题，这样就有50

6.保卫王国:考场上看成把独立集看成看管问题了,导致爆蛋,也怪自己脑子不清楚吧, 实际上这种WC出的东西放noip确实有点估计恶心人了，标算只有强省最高水平的家伙才能搞吧..这个倍增思路硬想应该是noip历史中最难了，所以88吧，noip一年比一年难也不管我事了,而且一定会是这样，毕竟我是最后一年,呵呵