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

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

点击量：1686

~~假装上一篇文章咕了~~

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（怎么又始发站咕咕咕啊，