A·F·O NOI2019 退役记
NOI2019 退役记
Day-1
咕咕咕
Day0
cao为啥广州这么热……
cao为啥广州蚊子这么多……
cao为啥广州突然就下雨了……
cao为啥老是找不到网……
……
开幕式出了一堆锅……这主持人居然装的跟啥事都没有也是挺强的…… 余姚->余桃 还行……（怕是以后要叫桃神犇了……）
然后NOI35周年发了一堆奖……
（dzd新名言：我们是正当的正义的竞赛）
广二礼堂日常毒瘤灯光晃眼……
然后下午AK了笔试，打开练习赛发现T1优秀的拆分，T2随机立方体，T3I君的商店
T1大细节题而且还没带草稿纸做个蛋啊……
T2前几天刚看了题解然后空间想象能力严重不足摸了……
T3神仙交互至今不会……（我记得WC考场上这题还爆0了……）
然后想着写写T1……刚打完SA就不想再写那个恶心的分段LCP了……然后写了个95蛤希
然后就想再写点啥，就想着干脆把给高一小孩出题的那个idea写写吧……
感觉这玩意动态离散化写起来跟原题没啥区别，然后还写了个堆的启发式合并……
然后就被坐旁边的开神犇ri了std：“这玩意为啥要用堆合并啊，你直接取最大值不就得了”
哦卧槽我sb了这玩意根本不用写堆……只和最大值有关……可以直接
我说呢，为啥以前没听说过这个东西……
你tm直接写个O(logn)的左偏树不就行了……
（然后就一直在到处蹭网中……）
晚上去自习室翻了翻写过的所有解题报告（然而感觉并没有啥卵用……），然后闲着没事写了个高精（？）就摸了
然后大家都在奶明天出交互……（怕是练习赛放题暗示……）
算了明天rp++反正我都无所谓了……
（然后晚上因为不想挂蚊帐被广东蚊子咬了一晚上……明天怕是要凉……）
Day1
来到赛场之后在8:00之前慌得一批……
（我慌个啥啊反正我都说了不在乎了……）
然后CCF习惯性地鸽了……连一分钟也能鸽……
然后到8:01的时候才开始比赛……然后就翻开了题……
然后就还是慌得不行，就在看题之前在第一页上写了几句话：
“别忘freopen！”（好像我每回考试都要写这个……）
“别忘-Wall！”（主要是ub怕了……）
“别忘开栈！”（然而今天并没用上……）
“不慌，我*****”（此处略去一些字）
然后就先把3个题都看了一遍——
T1
猫？蛤猫老师从小黑屋复出了？
然后看了一下T1的题面发现这不是个小孩都会的斜率优化傻逼题么我就
T2
emm……我记得好像立过flagNOI要考至少两个998的……然而这题是
ri这题好像是神仙数数题，先摸了（反正咱会T1不慌）
T3
咦感觉好像是个很可做的dp的样子？（反正咱会T1不慌）
然后突然发现全场1000多人好像没几个敲键盘的……惊了……
然后就开始写T1
然后写了一会突然下意识的看了一下数据范围——
测试点编号 1~10 特殊条件 xi<yi 11~20 无
测试点编号 1~10 特殊条件 xi<yi 11~20 无
测试点编号 1~10 特殊条件 xi<yi 11~20 无
测试点编号 1~10 特殊条件 xi<yi 11~20 无
测试点编号 1~10 特殊条件 xi<yi 11~20 无
！！！！！！！！
cao我tm怎么又读错题了……
然后就开始尝试修锅，然后发现woc这tm是个有向图啊……这怕是要边跑最短路边跑斜率优化，复杂度怕是要炸……
然后就突然想起来
哦这个在dp上确实还是个
然后我想了想
然后边写边改（？）的对每个点开个单调队列，这回没敢再用
然后到9:00左右的时候差不多写完了，然后大样例居然都过了，爽！
嘿你等着看吧等会回来检查的时候有你爽的时候……
然后就去写T2，发现第一遍看的时候题读错了……这个不是往两边单调不升，而是这个点的前面第一个比他大的与后面第一个不小于他的……
然后就发现第一个的后继不能超过4，然后就去想区间dp，发现确实能转成子问题，但是状态是爆炸的……
诶，我寻思着咱NOI之前好像专门弄过这一块的题来着……
对没错就是LNRT2的暴力，我就是通过这个题总结了一类“考虑最大值的独立考虑dp”
那么我们考虑整个序列的最大值？可能有多个，但是他们的排布显然是，
然后就去想
“感性展开”
诶我们可以把那个
然后就写了个
然后剩下的点就不会了，但是突然发现一条应该和std有关的性质，在区间dp里的时候我们的最大值实际上只会放
然后就去看T3了……
重新看了一遍题发现
cao不是说很可做吗……
我怎么觉得，这个玩意最少只能
我tm第一遍看的都是什么题你说说
到现在比赛刚好还剩一半的时间
不慌咱还有2个半小时能拿多少是多少吧……反正就一个题了
反正这题
第一个想法就是如果没有限制的话肯定是两个序列各取最大的k个，但是公共部分可能小于l，那么是不是贪心调整一下？首先已经两个都取的位置不用考虑，如果有一个位置只取了一个，我们要取另外一个的代价就是替换另一边取过的最小的代价，那么每次取代价最大的就行了……吧？
哎好像听起来很不对的样子啊……
（要是这贪心是真的这题能放NOID1T3？）
然后就试着写了个
然后接着又想了几个贪心都不对，然后就开始想怎么优化
诶我拿
然后就先写了个暴力估了一下哎滚动数组的话常数最小能跑到8e7，好像挺行的啊……
然后接着下意识的看了下数据范围发现那个150是
cao这玩意乘个10这tm能过啊……
这个时候已经过去1个小时了……
然后写乱搞的想法一直在心里动摇着……
cao不管了我可是瞎rand都能rand过的乱搞大师我怕啥？
（这话可是你自己说的……）
然后就先写了个暴力dp，剩下的数据先拿刚才几个不对的贪心跑一遍，再
然后发现大样例一个都没乱搞过去……cao算了拿28分不管了……
然后就开始检查
然后突然下意识的看了看试题的第一页的编译选项……
“对于C++语言 -O2 -lm”
“对于C++语言 -O2 -lm”
“对于C++语言 -O2 -lm”
“对于C++语言 -O2 -lm”
“对于C++语言 -O2 -lm”
“对于C++语言 -O2 -lm”……
So where is “-std=c++11”？？？？？？？？？？？？？？？？？？
我操
我T1好像全都在用unordered_map啊……
这怕不是要CE一大片……
（我上分全靠T1签到题了……）
然后就赶紧去修锅换掉unordered_map……
然后我每次枚举状态的时候都要判
要是直接换成map的话怕是就卡成
然后就赶紧慌得不行的在每个点上开了个队列按顺序存以这个点结束的时间，显然可行的dp只会在这些时间里存，我用个指针维护一下队列看是不是有这个时间不就行了？
然后就写了一个，重新跑了一下样例3
./me <test.in
744蛤？
Ans=749……蛤？
妈的你他妈的在逗我？
艹我tm只剩不到一个小时了啊啊啊啊啊啊啊啊啊居然过不了大样例了？？？？？
咦话说不应该出现这种玄学的情况吧，理论上改成这个是完全等效的啊……
然后就开始慌得一批
然后就换了种都每个时间开
蛤？
然后就突然想哎咱干嘛要用map啊直接用数组好像是能开下的……
然后就下意识的算了一下内存
哎好像真能开下……就把
这tm为啥会出现这么玄学的情况啊……不是按说理论上不会这样啊……
（但是咱过了大样例不慌~）
然后翻来覆去的检查3个题好像都没啥问题了，直到最后5分钟的时候突然瞄了一眼T1的代码发现……
int A=stk[j][hd[j]],B=stk[j][hd[j]]+1;卧槽草草草+1怎么写到了方括号外面……xswlxswlxswlxswlxswlxswlxswlxswl
这tm居然能过大样例？
哦对啊这题是猫出的大样例绝对会把人往死里坑……
（后来才知道怕是大样例的凸包就期望没几个点……）
woc好tm虚啊……怕是T1要fst就凉了……
然后就比赛结束了，就摸了……
估分：
然后LJ让回去休息会然后就照常的心里特别虚特别害怕T1fst然后躺床上一闭眼全是T1挂分现场……然后就睡不着了就绕着广二转了一圈就想woc我总不能回回都挂分吧要不这概率也太低了吧……
（然而心里是这么想还是很害怕……）
然后到了15:00去考场查分……当时紧张的腿都抖了（不是说不在乎考的咋样啊）
然后
我打开机子
输入密码
打开根目录
打开结果.pdf
……
HE-14
T1 100
T2 45
T3 28
总分 173……
我居然没挂分？？？？？
cao这怕是我第一次没有挂分的Day1……
（当然T3那些乱搞也一分没多得……）
然后i207M好像跟我得分与写的部分分都是一样的？
还以为这分还能看呢
然后就听说一堆人上200……
队线似乎有190……
反正我是D队线也跟我没啥关系……
cao然后就听说T2记忆化爆搜能有50，T3
（哦这似乎是因为监考的特意强调了“数据有一定梯度”）
（好像之前的时候一直都没理解过这话是啥意思？）
（不管了反正没挂分就行……）
期待后天也能不挂分……
Day 1.5
社会活动去了广东博物馆，然后就给2个小时……CCF一贯作风……
下午想去自习室摸会，结果路上偶遇撞见了——
immortalCO？？？？？？？？？
蛤woc然后“猫老师好”之后就疯狂的和小伙伴们讨论真猫（D1T1那个是假猫……）会出啥题
然后就得出了结论——
树上链分治交互
（这啥啊……）
然后晚上发现自己已经很久没打SAM了woc突然很慌……
然后就一直在看immortalCO以前讲课的各种数据结构课件……
Day2
一进场发现和ztb挨着，然后发现桌上“倒扣”的纸质题面最后一页居然是完整的T3的数据范围？
然后就发现了最后一行……
“提示：你的程序可以通过判断传入的N的……”
草草草草草草怕是奶中了？？？？？？
真tm出交互？
一看页眉“I君的。。。”
然后就发现了监考的猫老师？
然后就顿时明白了一切……cao怕是真奶中了……
然后和ztb交换了下眼色……
开考后照样在封面上写了几句话然后开始看题
T1一看见跳蚤二字就给跪了……
然后看上去似乎很不可做的样子？蛤？这啥矩形还能跑最短路
然后T2神仙概率……T3根本不是什么树上交互而是图上的……
cao这3个题好像都不太可做啊……
然后去看T1发现好像就是二维优化连边然后跑个最短路就行了……
然后想了半天二维线段树该怎么写然后就想起来了kd-tree……
咦我寻思vfk著名神犇而且还把内存设成128MB应该会卡的吧……
然后懵逼了半天发现不会更好的了……算了kd-tree+线段树+直接最短路应该能过掉88
不管了反正有88，写！
（然后就写到了9:00……中途还因为namespace内的数组名冲突调了半天……）
然后去看T2，发现30分暴力可以直接dp每个i在j位置的概率，然后Ai相等可以矩阵快速幂这样就有40分了……
然后就不知道该怎么写了……
然后就先去看T3发现好像只会
cao为啥我怎么这么菜啊……然后就开始想两两配对该咋做
这个时候就觉得全身都不舒服……cao怕是吹广州的发达空调吹感冒了……
然后就一直恶心……
然后就上了个厕所，然后就突然想到了昨天没事干看集训队论文看到的个词——
整体二分！！！！！
对啊我可以递归处理
这样似乎就有45了呢~（cao我tm当时sb了算成一个点5分……实际上只有36……）
然后就开始写……结果刚要写
咦好像只给了
然后我发现我就是个sb……
我们每次处理
然后正要开始写整体二分的时候又发现不太对劲了……
数据范围里的限制tm是完全严格的
然后这个时候就看着immortalCO就心里在想immortalcovisitworldnmsl……
然后我tm就没辙了……就接着去上了个厕所……
厕所外面人真tm多……然后就突然想到了严格
我们注意到对于
那么我们不妨最终令每一对
（然后就去了女厕所……）
然后就去写了个栈
这个时候就已经还剩一个半小时了……不慌写个T2的40暴力就走人……
然后写完之后发现一直输出0然后就开始心态爆炸的调……
然后突然注意到immortalCO在我后面注视着我？？？？？？？？？？
Wtf？？？？？？？？？？？？？
cao
似乎是因为我太给了然后猫才对我印象深刻……
然后就发现我
然后下意识的看了开头
#define p 99844353你妈的
然后就过了……
然后还剩半个小时就开始疯狂检查心态爆炸
然后下意识的size ./jump发现T1的数组超了128……
就一直改小边的数组直到我心里舒服为止（？）
然后这个时候心里一直在想“我tm已经尽力了”这几个字
然后还剩5分钟的时候干脆关了所有东西cao反正laozi尽力了就这么退役吧
要知道我Day1的时候最后5分钟还查出来一个错……
就一切都结束了
然后就跟猫老师聊了几句他说T3其实是板板出的……
哎不对啊那为啥grader.cpp里有bgg？
然后发现大家都差不多写的这个分？
怕是i207M两天和我得分完全一致然而他有A类加成……
然后就听说T1写kd-tree能过？
哎等会他们是怎么知道能过的？
（算了反正我写的kd-tree）
然后就意识到T3那个暴力是36分而不是45……
估分：
（中午听人瞎bbAg线要420不知所放……）
下午查分然后就抱着cao我啥都不管了的心态去打开了HE-14.pdf……
T1 88（果然过不去……）
T2 40
T3 36
总分 164
嘿我今天又没挂分？？！？
然后我突然意识到
这是我OI生涯最后一场比赛了……
我居然一点失误都没出？？？？？？
之前因为一堆失误
每次都疯狂的翻车
NOIP从估的500多挂到了467……
省选从估的A队挂到了D……
（我tm就因为一句
然后NOI想考几分就考了几分
然后就总分437，后来得知这个分是rk80多……就Ag稳了……
（orzErkkiErkko给给差一点进队）
（那些考600多的是tm人啊……）
然后得知我居然是SJZEZrk1HErk2？？？？？？？
这tm不太科学啊？？？？？（充分打脸十二省联好吧那个确实是我自己写挂了……）
全HE都没进队的……又断了一代……
然后就去找学上
然后因为一些奇怪的原因到晚上9:30（？？？）才去的SJTU……
SJTU：哎这难道是THU不要的？
不得不说那两个教授实在是太可爱了……全程都在哈哈笑……
然后……
就勉强的领了个约……（至于是咋勉强领的……这……你觉得我可爱吗？）
反正起码混了个约……
（upd：后来才知道THU只要429就能进面试，然后有人分比我低都有THU一等约？？？？？what？？？？？？血亏.jpg）
还好两年OI没有一场空……
AFO
从NOI2019到今天高考结束已经过去差不多整整一年了啊……
实在是发生了太多的事啊……
“还好两年OI没有一场空……”
整整一年前长舒一口气说出这话的时候，“强”“基”“计”“划”4个字怕是还没出现在这个世界上……
也许当时已经出现在jyb某个内部文件上……
1月份这玩意刚出来的时候还以为就是把降一本往上提到600分左右而已跟自招怕是没啥太大差别……
然后……等到了5月发现各个学校真的都不招Computer Science……
然后就被打电话告知D类选手不能破格入围
nmd
这tm就是在
被推下了火坑？？？？
然而SJTU的强基还得报，然而一看到报名页面上的专业类别选择
我竟然不知道选啥
不是
我本来应该能是个敲代码的
然后我只能去选个物理之类的
woc
算了，我不报了
然后貌似整个竞赛班就我没报强基？？？？？？
哦值得一提的是——
我们高考前的倒数第三次语文考试的作文是这样的：
给你列出“自主招生”和“强基计划”对于人才选拔的宗旨
让你写作文赞美“强基计划”的变化
……不说了……一堆反语走起……
那一天我们整个竞赛班的同学看到这作文题心情都是非常复杂的