锐客网

  1. 首页 > it技术 > >

NOIp2015提高组|NOIp2015提高组 解题报告

比赛几个星期前就结束了，玩乐了一会儿，开始学术。

此文非题解。只是我自己的现场解题实录。
Day_0
到宾馆后紧张的要死。晚上写了一堆基础模板：spfa最短路径，prim和kruskal的最小生成树，hungary的二分图匹配，树状数组，kmp字符串匹配，等等。
然后突然发现了一个叫做2-SAT的神奇算法。问了下居然是NOIp可能考的。赶紧看了下做法。然后发现自己tarjan强联通分量不会了，又去补了下。
最后发现自己的身份证没有带来。想了很久，然后还好家里离比赛地近，求家长送过来。
睡前才决定用Pascal以求保险。
Day_1
进考场的时候居然要查身份证！顿时冷汗。
提前一点时间进场了。先敲了Pascal模板，再一看还有时间，又敲了C++的。
看到第一天题目。第一题好简单，用少于5分钟的时间完成了。
第二题看了一会儿，发现是最小环，而且是基环树。
然后就明白有多种做法，当时脑子没反应过来还写了一个比较复杂的。写的是拓扑排序到无入度为0的点。
和大数据拍了一下。结果答案比标准答案大得多。想了想发现我这是把所有环的大小放一起了。
加了几句话，结果变小了却还是比标准答案大。发现竟然记录了最大环，再改动了一下，答案对的上了。
检查了一下复杂度，觉得都没问题就去看了第三题，发现比我预料的麻烦。此时还有三个小时！
仔细看了下第三题并没有什么难点。时间还多，莫非我要AK了？
发现是我想多了。虽然看上去是个暴力搜索或者可以是一个状态压缩DP或者可以写成记忆化搜索。2s时限不足为奇，1G内存！
磨了一阵还有两个半小时，开始码爆搜。
除了加上当没有出完牌且当前步数+1>=当前最优步数的简单剪枝，还想到如果数码连续的一些牌已经无法组成顺子，就强制拆成单张或对子或三张或炸弹来储存。
当这些牌以外的牌出完后，可以根据剩余的单张数、对子数、三张数、炸弹数来无脑计算。
否则枚举一个步骤，先枚举顺子以便在更容易被强制拆开储存，首次出完牌的速度更快且步骤数较好，对简单剪枝的帮助较大。这种情况下累计步数+1。
枚举完顺子，如果又不能强制拆开储存，就尝试把某个部分先拆开储存，这种做法不累计步数，因为拆开储存后还是要到最后对结果有贡献。
码完也大概只有一个小时了，前两个小数据都过了。大数据没有超时！但是用fc了一下发现有两三组数据的答案，我的答案比较大。
然后用一些奇怪的方法把这些组提取了出来，分析错误原因。
然后搞来搞去发现前面步骤好像没问题，于是输出了在这组数据中，出牌到最后的情况：当前步骤和被拆出储存的各种的张数。
当时只有十五分钟了，其实只是在第二类尝试的时候原本不该累计步数而我将步数+1了，但是当时比较慌乱，没有找出来。到最后还是选择检查了一下文件操作。
出考场后却立即想到了我的程序的错误之处，顿时悔恨不已。脑了一下，发现我的程序在n小的时候不可能会出错，然后脑出了最小反例是n=11。
【NOIp2015提高组|NOIp2015提高组 解题报告】n<11的数据共有35分，比暴力分多5分，听到队友们都是短时间打了暴力，我又是悔恨不已。前两题只花了30分钟，虚的要命。
Day_2
估计前一天没查出什么问题，进考场的时候监考人员就不再检查证件了。
还是敲了模板，并且在每个主程序开始的一行加上了//%%% Claris %%% CreationAugust %%% MedalPlus %%% Hillan以求平安。
注：以上膜拜不分先后。
看题发现第一题是NOI题库上的，并且领队赵老师叫我们看过！我清晰的知道那是二分算法。不过好像我的二分姿势不太对，调试了一段时间。
第二题看完有些傻了，好像是带组合数学的高难度数学题？接着发现看错题目，原来组成新串必须按顺序。
然后就很容易想到是DP，也很容易思考出一个50分的暴力DP算法。
发现大概是有一个与kmp匹配算法思想有点相似的优化就是在考虑前i为做成新串前j位的时候，如果原串第i位和第j位相同，可以直接利用i-1,j-1的且要求末位对上的结果。
发现全部数据下这个算法的时间空间复杂度都是4000W，看上去不会被TLE但是显然会MLE。
于是想到滚动数组结果开始的时候滚动姿势也不太对，而且是原地修改，当时连小数据也会答案错误真是慌死了。最后弄了很久弄对了，很高兴，去上个厕所冷静一下。
回来的时候已经只有一个半小时了。对最后一题磨了半个小时的画图和脑洞，我很快脑了一个树剖+枚举+线段树的算法，好像是n带上双重logn。
但是因为树剖和线段树不自信，而且这个算法本来也蛮难写，再加上剩余时间不是很多，想到领队的劝诫，开始暴力。
暴力完二次方算法，发现还可以去做只有一条路的部分分，写了一下，大概差不多了。末了检查。
由于自己机子上第二题我的代码在极端数据就是所有字符都相同的情况下会被略微卡常，所以估计一下250分到260分。
在去食堂的路上遇到了Hillan，聊了一会儿发现Hillan果然就是神。
Day x
在洛谷上和UOJ上拿着源代码玩了一下，再根据学军和余姚两大强校发布的民间成绩，发现结果尚能让人满意。
Day xx
有人找到了官方成绩给我们看，发现自己500分，名列第79，然后听说一等至少是取前80的，很兴奋。
Day xxx
官网公布了一等奖分数线和其获奖名单。




比赛几个星期前就结束了，玩乐了一会儿，开始学术。

    推荐阅读


    上一篇：J2EE系列（Tomcat内存释放不了、Tomcat内存溢出原因、Tomcat内存管理[整理]）

    下一篇：当四号领导遇到八号员工