Question

如何评价NOIP2016提高组复赛试题

Answer 1

作为初赛爆零复赛没参加的老年半退役选手，先占坑。。。
说实话啦，因为我不在国内，没法参加OI生涯最后一场NOIP，于是对题目发表些个人点评减少一点遗憾吧……
——考完啦——
老年选手不知道具体题面只是听了问题概述QwQ
1.模拟不说了，考你会不会编程
2.首先对每条路径从LCA处分成两半，那么两半的路径都是自上而下走或者自下而上走，令di表示第i个几点的深度，那么自上而下走的人能够影响的询问始终满足wi-di=Constant，自下而上走的人影响的都是wi+di=Constant的询问。接下来利用算出的Constant把询问分类，把树上自上而下的链拆成下端+1，上端-1，那么对每一类询问做子树和就能得到每个点的答案了，不能做n遍dfs求子树和，但只要预处理最近同类询问祖先就可以一次dfs解决了。
3.注意到两轮之间的路径只跟两轮有没有申请有关，预处理出四种情况的期望路径长度（两边都不申请，前一轮申请，后一轮申请，都申请），然后直接做背包dp就可以了，f[i][j][k]表示前i轮已经申请了j个其中第i个申请状态为k（k为1表示申请0表示不申请），枚举下一轮申不申请就行了。
——以上胡乱码了个题解，看不懂就对了反正我没写代码全是意识流（雾）——
首先难度较近年有大幅提高，感兴趣的可以看一下去年的第二题：http://uoj.ac/problem/146 感觉去年第二题……怎么说呢，这也能出出来我是比较服的。而今年的第二题说实话已经达到了NOIP第三题的难度，甚至很多集训队员都没有想出做法，而是使用高级数据结构（如启发式合并主席树）强行维护询问来解决，还有被卡常数的风险。
但是上面说的这个算法只需要简单的求出LCA然后进行树上深度优先遍历就能解决，简单的知识点的背后是的较高思维难度。
我很赞成这样的题目，然而放在第一天第二题可能确实难了一些，不知道选手们做的怎么样。
至于第三题，我觉得挺莫名其妙的，第三题只要理解了期望的含义，很容易就能看出非常朴素的背包模型，不需要什么思考就能做出来，属于动态规划的“套路题”。鉴于这是NOIP第一次设计数学期望，对选手来说本题的难点很可能在于理解数学期望，而非对求解方式的思考。当然这也可能是命制高质量的动态规划题比较难，而动态规划又是很重要的思想必须要考的缘故。
总的而言，难度提升，代码量提升，思维考察提升，第二题和第三题换一下可能合理些（雾）？
——Day2考完辣——
先来个意识流题解。。
1.在模k意义下直接求出所有组合数，然后二维前缀和统计0的个数即可。
2.注意到相邻两次切下来的长度，增加量不会超过q，而之前切的蚯蚓没秒钟增加q的长度，所以后切的蚯蚓一定比先切的蚯蚓短，于是开三个队列，分别维护初始的蚯蚓，切得的前一半蚯蚓，切得的后一半蚯蚓，新蚯蚓直接加到队尾就可以了，时间复杂度就线性了。
3.状态压缩DP，f[s]表示集合s的猪已经被消灭了，还需多少次发射，注意到两头猪和远点就能确定一个抛物线，直接枚举两头猪是转移是n^2的，注意到所有猪最后都要被消灭，于是标号最小的未消灭的猪是一定要被消灭的，不妨就在此回合消灭它，那么枚举另一头猪的复杂度是n的，预处理两头猪确定的抛物线能消灭的猪的集合，可以做到O(n)转移，于是复杂度就是O(2^n*n)了。
——奇妙做法——
2A.听说左偏树常数小，不妨来写一个说不定能卡过去。
2B.二叉堆太low了，我们使用32叉堆，在堆上维护时使用位运算，似乎会被卡空间。
3A.对于每个子集，判断能够用一只鸟一次性消灭，能的系数为1，否则为0，得到一个集合幂级数。我们可以二分次数k，那么我们求这个集合幂级数的k次方集合并卷积，并判断全集前的系数是否>0，大于0说明可以消灭。这样复杂度是O(2^n*n*logn)，快速沃尔什变换(FWT)常数很小，感觉跑过去还是比较轻易的。
3B.敦敦敦说：其实fwt用取模，也可以一个n。哦我也不大清楚这是怎么搞的。。
——我也不知道在这个分割线上说什么——
这次NOIP，可以说专治各种高级数据结构学傻，高级算法学傻（雾），比如第一天第二题第二天第二题很容易走进高级数据结构的不归路，我这个FWT学傻了的老年选手看了D2T3直接想出了算法3A。。。算法3是yjq教我的。。
我认为NOIP从命题质量上提升了许多（可对比去年D1T3），即更加注重对思维的考察，代码能力考察也是在有了相应的思维能力之后才会有。注重思维考察一个相应的结果就是难度大幅提升，会提高在NOIP选手中，中等等水平往上的选手之间的区分度。
总体来说给题目点赞~
P.S.对于部分分设置，我根本没看，所以不知道对于刚接触OI的新手是否友好。