NOIP2017送命记

  又是一年NOIP,又是一次送命记。

  

Day0

  早早的出发去公寓,然后看到了SM大军聚在公寓门外233。

  原本想在考前敲些模板的,然而什么都没有做。

  晚上和Coming,lhx_QAQ,KsCla去吃韩国烤肉,颓颓颓。

  

Day1

  早上起晚了,差点迟到。

  进入考场,发现旁边坐着纪中大佬cty。

  密码是不忘初心,好评。

  

  打开屏幕后,隔壁cty开始调sublime text,敲码速度极快。

  我打开题目,开始看题。

  

  T1什么鬼,感觉不太可做。T2一眼模拟啊。T3跑最短路后DP啊,不过环不是很会处理。

  

  跑去推下T1,直接手动模拟找规律,然而并没有找到。

  推了20多分钟,决定先去码T2。大概9:30的样子过了大样例。(大样例好评,包含了所有情况)

  再回去推T1,这次换个角度,用扩展欧几里得去推,直接得到上界,然后得到公式。。。

  

  大概10:10左右把T1的对拍码完。往左边瞄一眼,发现cty都开始调T3了QAQ。

  开T3,发觉DP很显然,好像也很好转移,然后直接SPFA最短路+SPFA转移,大样例T了。

  感觉有点迷,码个暴力先拍一下吧,拍出各种问题,而且我想的判断无解方法是错的。。。

  

  重新调整思路,并整理出T3正解,然后开始码。这时cty已经码完对拍,afk了QAQ。

  11:30发觉码量惊人,弃疗。跑去肉眼查错T2,感觉很虚。

  觉得T3搞不定,交了暴力,并删减了一些内容。

  再瞎搞搞就结束了。

  

  出来后,发现T3忘记取模了,因为是暴力。

  T1结论题貌似坑了一些人。有几位大佬T3码的是正解,不过都面临着卡常风险。

  

  后来讨论了一下T3,貌似直接spfa转移是可行的,虽然常数玄了点。。。

  看来是我写挂了,菜不成声。

  

  fzh说他过了T2大数据却hack掉了自己程序,我很害怕。

  今天基本是爆炸了,T2很玄,T3爆零。拿的分比大众分还低。

  

  下午一起去玩密室逃脱,最后玩到超时都没通关233。

  回来后吃了顿饭,看了会KsCla玩东方就睡觉了。

  

Day2

  早上起来精神不佳,感觉药丸。

  拖着疲倦的身体走向了广州二中。

  

  今天的密码变成了alphago,差评。

  cty居然不调sublime text了,直接开了题目。

  

  T1第一眼还以为是什么恐怖的最小圆覆盖之类的问题,后来发现是暴力宽搜。T2没什么想法,但是看数据应该是状压DP。T3感觉不太好做。

  

  开场15min不敲码,所以就在那里想T2。

  感觉T2那个层数有点麻烦,干脆一起记下来吧,于是得到一个$O(N4^N)$做法,算了下时间感觉不行。

  

  先跑回去码T1。

  很快就码完了,xjb调了调感觉没问题。试了下大数据,结果WA了。。。

  一脸懵逼,居然被T1给切了。盯着程序看了10min,自信没问题。

  可能我的做法不太对?于是又码了另外一种暴力,结果答案一样= =

  

  看了下时间,9:30。算了,不理T1了,先做T2。

  跑去码$N4^N$做法,码到一半总觉得有点怪,好像状态有点多余。

  换了种角度,又在纸上推了一下,好像是可以记录层数来做DP,然后枚举下子集。$O(N^3 \times 3^N)$

  算下时间,超了一点,那就上预处理。$O(N^2 \times 3^N)$,时间还是略玄学,但是卡到1s内了,再上个lowbit优化下预处理,感觉可行。

  先开始码$O(N^3 \times 3^N)$,因为要对拍。

  很快切掉了,然后在$O(N^3 \times 3^N)$的程序上加上预处理,大样例全过,对拍也拍上了。

  

  这时候大概10:30的样子,回去调T1。

  直接输出调试大样例,发觉读入数据有点迷?

  再看了几眼,发觉win下是不能lld读入的= =

  然后就把T1搬到了cygwin上,大样例直接A了,另外一种暴力也A了。

  居然是因为I64d和lld的原因,我还浪费了30min去调QAQ。

  

  只剩下1h10min,开T3。

  稍微画了一下,好像只有最后一列是稳定受到影响的,那是不是可以求出询问之间的影响啊。不过好难搞啊。。。换种思路吧,每次只是一个L型变化,那是不是可以把换位看成区间操作然后上cdq分治啊,不过答案没有可加性。。。

  

  弃疗了,码$n \leq 10^3$和$x=1$的暴力算了。

  然后码码码,中间Treap花了我一点时间。

  最后没时间把Treap和暴力对拍,于是肉眼差错。

  

  诶诶诶,这里怎么没return啊。

  诶诶诶,这里怎么没update啊。

  我是怎么过样例的啊,win环境有毒。放到cygwin上跑下,还好过了样例。

  

  然后就结束了。

  

  出来后又想了一下T3,发觉$x=1$的做法很容易就推导到正解。

  考场上我居然没想出来QAQ。果然考场debuff还是太大了。

  

After NOIP

  成绩还是未知数。

  但是拿到程序后发现D2T1交的是加了重边的旧程序,我明明改了的QAQ。

  只能祈祷数据水一点了。。。

  

  Upd:

  考场最高得分:100+100+70+100+100+80=550

  官方测试得分:100+100+30+100+100+30=460

  省排名惨不忍睹。。。

  

  感谢CCF,让我A了D2T1并水了D1T3 30pt。

  D2T3 Treap写炸了,只有30pt QAQ。

  感觉之前写的给退役选手的话(其实是写给自己看的)好中二啊,还是删了吧。

  在这里祝福所有OIer WC/省选/高考加油。

 幻梦终醒,本无不散之宴,却不悔付此华年。

  

Summary

  虽然送命了,但还是要总结一下的>_<。

  (1)感觉Day1和Day2的心态都挺棒的(除了最后1h),继续保持这种心态。

  (2)D2T1太惨了,居然交了旧程序。以后对拍程序和提交程序一定要仔细核查,千万不要交旧程序

  (3)D1T3没交SPFA转移DP,好naive啊。以后遇到这种冲突情况,一定考虑清楚,选择最优策略。(这个好像是常识QAQ

  

  然后好像就没了。

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang