HNOI2015总结

// 此博文为迁移而来,写于2015年4月21日,不代表本人现在的观点与看法。原始地址:http://blog.sina.com.cn/s/blog_6022c4720102vy9t.html

 

这次省队选拔其实是抱着玩玩的心态去参加的,尽管分数在我的意料之中,但是感觉还是有莫大的遗憾。总分75分,第一天35分,第二天40分,可以说是比较标准的暴力分(第一天其实还有10分没有去争取)

Day1:第一次参加比赛是用NOI-Linux。去年的时候,我就在魏龙的帮助下在电脑上装了Ubuntu,当时感觉不太习惯。在其他人的一些帮助以及自己的摸索下,还是用的比较习惯了。但是在第一天考试的时候,还是碰到了一些非能力的问题,也不知道是紧张还是手速太慢,我的配置文件没有打好老师就说要收了,这更是让我感到不舒服。考试的时候因为Emacs的一些版本问题,导致一些快捷键如同Ctrl+Z或是Ctrl+W出现了一些奇奇怪怪的变化——我的程序莫名其妙的少了一截,我却不知道怎么撤退。总的而言,第一天亏就亏在了状态这个问题,整个上午都在打着第二题,直到把50分的情况都打完之后才发现第三题还没动笔。我在之前看题的时候对于第三题,就有过一种想法,用拓扑排序+堆优化,但是我个人认为这只是一种比较好的暴力方法罢了,所以我还是规规矩矩的一题一题写的。当时我根本没有想到,这就是第三题的正解,而且周子栋打出来了,AC了。第一天下来,问题有很多:对于一些奇怪问题的到来,没有什么应急措施,而由此导致了时间的分配问题(我想如果我先打第三题或是有时间打第三题就不会是这种情况了吧)

Day2:第二天在状态方面还是很明显好了许多,前一天的晚上就把配置啊,撤退啊什么的都准备好了,但是由于本身的知识能力,第二天也就打了第一题,第二题的共40分,还好没有出现暴力打错的问题。第二题的话,我还是在考场上临时想出来的一个优化。由于我之前从来没有单独去写过LCA(想想也是惭愧),所以LCA是我考试时突然写出来的……一般的标准20分是求出所有点之间的距离,最后询问的时候直接求和即可。我想可以实现找出一个非叶子节点作为根节点,求出所有点到根节点的距离,最后跑LCA求出两点之间的距离,这样空间复杂度小了许多,但是由于第三个以后的测试点都非常大,所以这也只有20分,但对于我突发奇想想出一个平常没写过的东西还是比较值得庆幸的。

总而言之,现在呢还是高一,今年进省队是从没想过的,这次考试本来最大的作用就是提前有个准备,同时尽自己所能得到更多的分,75分中规中矩,但是对于Day1的第三题完全能够到手却流失于指缝,让人十分惋惜。现在要做的,就是继续努力学到更多知识,在NOIP拿一等奖的基础上,冲刺明年的省队。

随便写的算法:
 
1、亚瑟王(arthur)
 
       算法一:DFS(10分)
 
2、接水果(fruit)
 
       算法一:跑DFS/BFS求出主链,在链上求出存在的所有存在的子链,求和(20分)
       算法二:在算法一的基础上:考虑到30%数据是一条链,可以写树套树(30分)
       算法三:动态树+树分治(100分)
 
3、菜肴制作(dishes)
 
       算法一:输出impossible(15分)
       算法二:拓扑排序(40分)【有待考证】
       算法三:逆向拓扑排序(70分)
       算法四:逆向拓扑排序+堆(100分)
 
4、 落忆枫音(maple)
 
       算法一:枚举所有边,跑DFS判断是否全部到达(20分)
 
5、幻想乡开店(shop)
 
       算法一:事先求出所有点之间的距离,询问时直接求和(20分)
       算法二:任取一个非叶子的节点作为根节点,求出所有点到根节点的距离,询问时求出LCA
                    (空间复杂度明显小些,但是依旧20分)
       算法三:在算法一或算法二的基础上:考虑到有20%的数据是A=20,可以考虑树形DP(40分)
 
6、比较实验(pairwise)
 
       算法一:树形DP(100分)【有待考证】
 
       红色标记是我弱在这次考试时写的。。。好像全都是暴力(shop除外吧,感觉还是动了脑筋的呢 = =。)更多总结等发了题解再说。
原文地址:https://www.cnblogs.com/jinkun113/p/4681274.html