30.3.18 考试小记

发布于 2018-03-30  2.95k 次阅读


T1

本来题目描述的是水题,结果等写完以后才改题意。。。30分hash暴力交上去都T,气!

题目要求线性复杂度,不是hash就是KMP,那我们肯定要用hash啊。

考虑这种奇怪的匹配需要维护哪些信息才能实现。我们需要知道的其实就是相等元素的相对位置关系,那么可以记录每个元素上一次出现的位置,然后动态维护一段区间的hash就可以完成任务。每次的动态维护其实就是抠掉最前面的元素,然后还要处理抠掉元素对于后面元素的影响,显然只会影响至多一个元素的hash值,因此可以O(1)完成修改操作,处理一下细节,然后这道题就做完了。

注意,hash如果不用双模数的话一定不能出0。

 

T2

考场上部分分少乘了一个r,我都不知道自己是怎么想的。

题解是很神的玩意,但是这道题还可以用随机化的方法搞过去。

模拟退火,就是不断由一个可行的解生成出新的解,如果新解更优那么一定替换过去,否则按照一定的概率接受不优的解。因此,这个算法可以减少跳进局部最优解的概率,从而获得更多分数。

应用到这道题上,就是随机每个圆上点的极角,并通过控制极角变化的程度来控制新解的范围。求出一组可行解之后,再求凸包算面积即可。

但是,直接写完然后调整参数的方法在平均情况下只能拿到70~90分,实测很难AC,有两个方法能大大提高正确率:一是对于初始解的构造,我们可以在较大范围内多次重新生成解取最优,之后再进行模拟退火。二是多次重复进行整个算法,这点依据时间限制而定,对于这道题,实测每次运行20次左右,平均只要200ms,但是AC率就已经很高了,本地跑了十几次只有1次WA了一个点。

这是我写的第一道模拟退火,也算是因为这道题又学了一些新知识吧。

 

T3

恶心的数据结构,还没改完。

 


反思

又翻车了。考试的时候没有想到T1的正解,也没有压力测试一下,然后成功爆零,感觉现在做这种题的时候还是想的不够广,经常会把自己套进自己的圈套里。T2少乘一个半径,然后又因为手造数据太水没看出来。T3打了60分的暴力,却因为精度之类的奇怪的原因挂了20。从前几天的稳定前三到现在的连环翻车,感觉有很大的原因还是最近又浮躁了,想暴力、写程序的时候有点自以为是,感觉自己写的暴力很稳就不去调试,感觉自己想的思路没错就不去查错,感觉式子推的没错就不去验证,感觉程序又快又稳就不去对拍,在该想着保住当前分数的时候早早去想如何得到更多分数,这些问题都是近两天的考试中涌现的。一定要在省选之前戒掉这些毛病,找回之前的状态!


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974