徘徊在 AFO 的边缘 – NOIP 2018 半退役记

作者: wjyyy 分类: NOIp2018,记录篇 发布时间: 2018-11-08 11:31

点击量:846

    假装上一篇文章咕了

Day -1

    Dijkstra板子手写堆怎么都过不了标准版,但是弱化版就能过;然后标准版换成pq立马就过,不知道什么原因……

    MST的板子也没有1A,感觉图论药丸💊……

    不过貌似有点期待大模拟了(毒奶),因为前一天晚上写出来一道,几天前也有一道模拟+搜索……立了个今年A掉猪国杀的flag。

    上午弄了道树剖题,感觉良好(顺便练了线段树)。中午颓+刷了一下洛谷日报。下午拿std::map存边T掉了预示着什么……晚上打算睡个好觉。

Day 0

    早上卡点去火车站,找了个人少的取票机取了票,但是票是红色的,dalao们都问我为什么又取到红色票了……但是那边人真的少啊!

    发现这趟火车刚从武汉回来就要从襄阳过去,来的那趟晚点了导致始发站晚点莫名感觉TLE。路上体验良好,该用网的时候不是很差,路上打了遍fhqtreap,和五中高一的在一个车厢。

    经过长江拍的照片

    中午吃传统老店KFC,希望能rmb--,rp++;。挤地铁到了光谷,去年这时候就在修路,今年修路幅度更大了,不知道在搞什么鬼,走路还得绕步行街。14:30到宾馆一楼发现宜昌某学校的在办入住,考虑先放东西直接去试机。

    还是南一楼八楼,木质凳子,hp键盘,4G内存(没有打广告!)。试机打了个treap,试了试快读,Code::Blocks比自己电脑还好用(雾。又打了a+b,然后想写写斗地主(Noip2015)……写了7个kb交上去只有25分,发现细节处理有点问题遂改之,拿了45试机就结束了。不知不觉写了7k,感觉键盘手感不错,不知道明天怎么样。

    回宾馆的路上看到了特别好看的天空,我天天在学校连审美能力都丧失了。

    晚上在光谷吃完饭夹娃娃什么都没夹到但是感觉rp++。貌似下午有段时间没穿外套鼻子塞了,但是不影响我们娱乐狼人杀。

    已经很晚了,所以晚安。

Day 1

    早上4点左右醒了一下,腿比较疼,继续睡……

    按照惯例在楼下沙县吃早餐,比去年早一点,毕竟去年是8:25进的考场时间比较巧,排上了队走的也比较快,HB-0263抽到了804-63号

    状态还不错,键盘按着非常舒服。Code::Blocks都比较正常,突然发现机子是8G的,特别特别流畅,编译很顺利(待会就说不定了。

    8:26公布密码,Fei2Xue@Lian&Tian!看上去比较文艺,一次打对了,不知道谁说的密码不一次打对会慌。倒是觉得监考会打错密码。看了看文件,3个题都有大样例,比较稳;打开pdf,测试点10/20/20,比较正常,没有spj,空间全部512M,顿时感觉CCF豪气,直到看到了下面的一段:

    我们多交的报名费都用来干这个了吗,但是看不懂配置不知道CCF少爷机一秒多少,万一1e9我是不是可以暴力出奇迹啊《

    T1感觉比较熟悉,分了个治,发现是\(O(n^2)\)的,需要求rmq,怕ST表写错,就写了sgt,感觉稳一些,貌似寒假在北京的时候Hestel说过他当年把\(O(n)\)套了个线段树,但是\(n\le 100000\)过掉了,于是我也不是很担心这个题,大样例能跑过。

    T2第一眼ex小凯的疑惑???于是当了数学题,在草稿纸上写下\(\tt T2\)期望\(80\)。先打了背包暴力,感觉用std::bitset优化暴力非常可靠,大概是\(O(2^n\times a_i/\omega)\)的,只能过掉\(65\)分,不过也是很多了。打了一下水过大样例中\(n\le 13\)的部分就去看T3了。

    T3貌似是个树形DP,但是不知道怎么做决策,给了个图,联想到去年宝藏、今年省选的林克卡特树和今年NOI的多边形……突然感觉很难,但是想想这是NOIp,头铁推了一下贪心,感觉没啥问题,实在不行再用树形DP推。

    写了半天最后贪心的时候要匹配,先排序,然后二分,但是不会链表上二分,也不会在数组上删除,于是拿无旋Treap开始写,也方便二分。写着写着开始纠结是分裂的时候删点还是先查询后删点,有一段时间干脆打算拿std::vector做了,后来发现复杂度不对。搞来搞去终于过了样例,测大样例发现\(\tt Segment fault\),查了半天发现Treap的Delete写挂了为什么又犯这样的错误啊啊啊啊。过了大样例感觉比较稳了,回去推T2无果。

    最后20min发现T2\(n\le 5\)的时候\(a_i\le 1000\),突然发现挂了,因为根据小凯的疑惑,dp数组需要开到\(O(a_i^2)\),但是\(n=2\)可以特判,\(n=13\)的时候\(a_i\)挺小,草草打了\(30\)分过了样例滚粗。

    T3题面明显提示二分答案

    被Dew奶中了

    然后出来发现全省都会T2就我不会;全省280+就我230还不稳;担心省一还保不保得住。不小心听到T2是个背包 呵呵 说不定要被一个背包送退役了,去年d1T1很多人用背包推,推不出来,今年又搞真背包,被CCF玩弄于股掌。

    估分\(100+15(30)+100=215(230)\)。

    中午在华科吃的,雨下挺大,鞋子湿了,下午联机MC无果,联机CS体验极差。鞋子还没干就又去光谷吃晚饭了。

    晚上散完心之后打了场Virtual CF,半个小时AB(-1)C,比较正常,E是个类似容斥的东西,感觉有点虚Day2,但是没推出来也就算了。

Day 2

    早上起早了些,排队还等了一会,抽到808-64号,63++了。

    808环境感觉差一些,机房比较窄,一排只有8台机子,不过配置一样,还是8G内存。监考员提示使用Code::Blocks后果自负???无所谓了 能有什么后果,吐槽键盘不好用。密码果真是%xiao#SHU9shen!xia,算是致敬金庸先生吧

    发现机器时间和实际时间不符,找监考员问,他说开考会提示,我才不信,--rp;

    开了题发现T1T3有25个点,怎么又被Dew这个AK佬奶中了,T3 2s,都512M。T1比较可做,可以贪心,但是环不好处理,稍微考虑了一下开始打了,过了一会发现有的情况没考虑到,大样例各种挂。不知不觉推到了9:50,打了60分暴力和12分特判去推T2了。考完后得知是基环树枚举短边……我貌似每次基环树都看不出来诶,明明看到后40分是\(n=m\)却根本没有想到基环树。

    T2\(n\le 8,m\le 10^6\),中国象棋既视感,推了一下状压DP,感觉复杂度是\(4^n\)左右的,套不上\(m\)了,考虑把DP推出来然后矩阵加速一下,矩阵打完发现DP有状态不合法,有点紧张就去看了看T3。

    T3不傻子树形DP吗……噢多组询问不会了orz。打了\(O(nm)\)的44分过了小样例我为什么没有测大样例现在慌的一批回去就推T2了。

    怀疑DP方程写错了,但是看不出来,11:30了我好方啊。于是开始用std::string比较字符串+爆搜,发现搜出来没啥问题,能稳过(毒奶\(n\le 3,m\le 3\)的数据,也是对的。接着就不知道自己答案怎么大了,喝了很多水冷静,又上了好几次厕所却根本没有用,想不到思路。最后还是把这个能拿15分的程序交了上去。

    估分\(72+15+44=131\),两天\(215(230)+131=346(361)\),woc万一挂分了就不及格了呜呜呜,别人都是要上500的了我还在及格线边缘徘徊,要AFO了好慌啊……

    听说T2是个规律,但是没看到靠谱的结果,状压白推了(就说怎么可能3年连考状压;T3是动态DP那是什么,感觉很难的样子。

    今年WC估计是去不了了,还不知道文化课能怎么样。退役可能失败了,但是半退役也不是什么好兆头。希望能在全省占rk20-吧。

    中午吃火锅,又夹到一个娃娃,不知道夹娃娃是不是掉了rp,但就是感觉非常快乐。今年没什么遗憾,就是莫名被一个背包和一个基环树还有一个找规律给送走了,心态还不错(脸皮变厚了)。

    下午走晚了差点赶不上火车,然后火车晚点+1(怎么又始发站咕咕咕啊,

现在在火车上。

    经过长江的时候又拍了张照片

    文化课加油吧,徘徊在AFO的边缘。希望有一等奖拿。

Upd @ 22:29

    代码发下来了,luogu上测的\(100+45+70\ +\ 76+20+44=355\)。d1T3莫名RE,d1T2可能数据水了点,d2T1多水了4分,感觉72分稳了;d2t2的20估计是梯度数据。

 

后记

    文化课凉得很彻底……真正的后记会再开一篇文章的。从零开始的文化课生活 – NOIP 2018 后记

5
说点什么

avatar
3 Comment threads
2 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
4 Comment authors
huyufeifeiHailJediwjyyyWepdekr Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Wepdekr
游客

您这个分稳了啊QwQ

HailJedi
游客
HailJedi

%%%

huyufeifei
游客
huyufeifei

我要AFO了,您徘徊在AK的边缘orz……

/* */