作为初赛爆零复赛没参加的老年半退役选手,先占坑。。。
说实话啦,因为我不在国内,没法参加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的新手是否友好。