A·F·O NOI2019 退役记
ywy_c_asm
2019-07-16 18:17:48
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了这玩意根本不用写堆……只和最大值有关……可以直接$O(1)$合并
另外就算要用堆也不能写**堆的启发式合并**这种蠢的东西吧……
我说呢，为啥以前没听说过这个东西……
>
>你tm直接写个O(logn)的左偏树不就行了……
>
（然后就一直在到处蹭网中……）
晚上去自习室翻了翻写过的所有解题报告（然而感觉并没有啥卵用……），然后闲着没事写了个高精（？）就摸了
然后大家都在奶明天出交互……（怕是练习赛放题暗示……）
算了明天rp++反正我都无所谓了……
（然后晚上因为不想挂蚊帐被广东蚊子咬了一晚上……明天怕是要凉……）
## **Day1**
来到赛场之后在8:00之前慌得一批……
（我慌个啥啊反正我都说了不在乎了……）
然后CCF习惯性地鸽了……连一分钟也能鸽……
然后到8:01的时候才开始比赛……然后就翻开了题……
然后就还是慌得不行，就在看题之前在第一页上写了几句话：
“别忘freopen！”（好像我每回考试都要写这个……）
“别忘-Wall！”（主要是ub怕了……）
“别忘开栈！”（然而今天并没用上……）
“不慌，我*****”（此处略去一些字）
然后就先把3个题都看了一遍——
----
T1
猫？蛤猫老师从小黑屋复出了？
然后看了一下T1的题面发现这不是个小孩都会的斜率优化傻逼题么我就$dp[i][j]$时刻j在i的答案然后按顺序从左到右考虑每个点用做过不知道多少遍的单调队列处理一下下凸壳不就行了么？$O(nt)$，不愧是猫老师复杂度开这么满……
----
T2
emm……我记得好像立过flagNOI要考至少两个998的……然而这题是$1e9+7$……
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怎么又读错题了……$x_i$甚至可能$>y_i$……
然后就开始尝试修锅，然后发现woc这tm是个有向图啊……这怕是要边跑最短路边跑斜率优化，复杂度怕是要炸……
然后就突然想起来$p_i<q_i$这个条件了……
哦这个在dp上确实还是个$DAG$，咱们在外层枚举时间不就行了……
然后我想了想$1e5×1e3$的数组开起来有点虚，就写了个$unordered_map$存dp，这样dp转移和状态反正也是均摊$O(m)$的，只不过要$O(nt)$枚举罢了……
然后边写边改（？）的对每个点开个单调队列，这回没敢再用$deque$，就用不能$pop\_front()$的$vector$然后再额外维护一个$head$指针代替了一下……（话说我以前为啥不这么写啊……）枚举时间的时候对所有有状态的地方把这个时间插到凸包上，然后处理以这个时间为起点的转移。
然后到9:00左右的时候差不多写完了，然后大样例居然都过了，爽！
>嘿你等着看吧等会回来检查的时候有你爽的时候……
然后就去写T2，发现第一遍看的时候题读错了……这个不是往两边单调不升，而是这个点的前面第一个比他大的与后面第一个不小于他的……
然后就发现第一个的后继不能超过4，然后就去想区间dp，发现确实能转成子问题，但是状态是爆炸的……
诶，我寻思着咱NOI之前好像专门弄过这一块的题来着……
对没错就是LNRT2的暴力，我就是通过这个题总结了一类“**考虑最大值**的独立考虑dp”
那么我们考虑整个序列的最大值？可能有多个，但是他们的排布显然是，$|i-1-(nxti-i)|<=2$，那么，我们可以在区间dp上套一个序列dp决策这些最大值放到哪，$dp[i][j][k]$区间最大值为k，我们对dp做个前缀和，然后套一个$f[i]$最后一个最大值放在i，f就暴力枚举上一个放的是啥就行了，必须使得上一个位置是合法的，f的转移空出来的地方就用区间dp的前缀和填补，使得这些位置都比k小就行了。这样是$O(n^4w)$的，卡卡大概就35分了。
然后就去想$n<=50,l_i=1,r_i=1e9$咋做，这样的话状态就不用区间dp了只需要记长度就行了，但是值域有点大。然后我就想方程的时候突然发现了区间dp里好像并不用再套一个dp，我们枚举最后一个最大值放到哪，前面的都是小于等于最大值的，后面都是小于最大值的，即$dp[l][r][i]=dp[l][r][i-1]+∑dp[l][k-1][i]dp[k+1][r][i-1]$，这样的话就$O(n^3w)$了。然后不用区间dp就是$dp[i][j]=dp[i][j-1]+∑dp[k-1][j]dp[i-k][j-1]$，这玩意咋做？然后盯了这个式子半天突然想到个以前自创的词——
## **“感性展开”**
诶我们可以把那个$dp[k-1][j]$暴力展开，好像并没有啥卵用，但是我就突然想到了这怕是多项式然后让我们拉格朗日插值的woc怕是可以归纳我们假设$dp[k<i][j]$是一个关于j的k次多项式，然后这个转移发现是一些k-1次与i-k次多项式相乘然后求和的形式，再加上一个关于j-1的i次多项式（当然可以化为关于j的），好像是对的哎~
然后就写了个$O(n^3)$插值一拍发现是对的，这样就有45分了~
然后剩下的点就不会了，但是突然发现一条应该和std有关的性质，在区间dp里的时候我们的最大值实际上只会放$O(\log n)$个因为前一个与后一个的距离差不多就是二倍的关系，然而并不知道该怎么用……（后来考完之后听老放说才知道这玩意暴力记搜就能多拿几分……）
然后就去看T3了……
重新看了一遍题发现
cao不是说**很可做**吗……
我怎么觉得，这个玩意最少只能$O(n^4)$啊……
>我tm第一遍看的都是什么题你说说
到现在比赛刚好还剩一半的时间
不慌咱还有2个半小时能拿多少是多少吧……反正就一个题了
反正这题$O(n^4)$有28，而且感觉乱搞能拿很多分……
第一个想法就是如果没有限制的话肯定是两个序列各取最大的k个，但是公共部分可能小于l，那么是不是贪心调整一下？首先已经两个都取的位置不用考虑，如果有一个位置只取了一个，我们要取另外一个的代价就是替换另一边取过的最小的代价，那么每次取代价最大的就行了……吧？
哎好像听起来很不对的样子啊……
（要是这贪心是真的这题能放NOID1T3？）
然后就试着写了个$O(n^2)$的贪心，发现样例1过了，样例2WA了，果然不对……
然后接着又想了几个贪心都不对，然后就开始想怎么优化$O(n^4)$的暴力dp，发现这个dp已经无法优化状态了……
诶我拿$O(n^4)$过150是不是可以？
然后就先写了个暴力估了一下哎滚动数组的话常数最小能跑到8e7，好像挺行的啊……
然后接着下意识的看了下数据范围发现那个150是$n<=150$不是$∑n<=150$……
cao这玩意乘个10这tm能过啊……
这个时候已经过去1个小时了……
然后写乱搞的想法一直在心里动摇着……
cao不管了我可是瞎rand都能rand过的**乱搞大师**我怕啥？
（这话可是你自己说的……）
然后就先写了个暴力dp，剩下的数据先拿刚才几个不对的贪心跑一遍，再$random\_shuffle$搞出一定公共的部分，剩下的部分直接取前$k-l$大的……
然后发现大样例一个都没乱搞过去……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……
然后我每次枚举状态的时候都要判$if(!dp[j].count(i))continue;$
要是直接换成map的话怕是就卡成$O(nt\log n)$的……
然后就赶紧慌得不行的在每个点上开了个队列按顺序存以这个点结束的时间，显然可行的dp只会在这些时间里存，我用个指针维护一下队列看是不是有这个时间不就行了？
然后就写了一个，重新跑了一下样例3
```cpp
./me <test.in
744
```
蛤？
```cpp
Ans=749……
```
蛤？
**妈的你他妈的在逗我？**
艹我tm只剩不到一个小时了啊啊啊啊啊啊啊啊啊居然**过不了大样例了**？？？？？
咦话说不应该出现这种玄学的情况吧，理论上改成这个是完全等效的啊……
然后就开始慌得一批
然后就换了种都每个时间开$vector$存结束点的写法，结果还是输出744……
蛤？
然后就突然想哎咱干嘛要用map啊直接用数组好像是能开下的……
然后就下意识的算了一下内存
$100000×1000×4/1024/1024=381MB$
哎好像真能开下……就把$map$换成数组然后发现输出居然就对了……
这tm为啥会出现这么玄学的情况啊……不是按说理论上不会这样啊……
（但是咱过了大样例不慌~）
然后翻来覆去的检查3个题好像都没啥问题了，直到最后5分钟的时候突然瞄了一眼T1的代码发现……
```cpp
int A=stk[j][hd[j]],B=stk[j][hd[j]]+1;
```
卧槽草草草+1怎么写到了方括号外面……xswlxswlxswlxswlxswlxswlxswlxswl
这tm居然能过大样例？
哦对啊这题是猫出的大样例绝对会把人往死里坑……
（后来才知道怕是大样例的凸包就期望没几个点……）
woc好tm虚啊……怕是T1要fst就凉了……
然后就比赛结束了，就摸了……
估分：$100+45+28=173$
然后LJ让回去休息会然后就照常的心里特别虚特别害怕T1fst然后躺床上一闭眼全是T1挂分现场……然后就睡不着了就绕着广二转了一圈就想woc我总不能回回都挂分吧要不这概率也太低了吧……
（然而心里是这么想还是很害怕……）
然后到了15:00去考场查分……当时紧张的腿都抖了（不是说不在乎考的咋样啊）
然后
我打开机子
输入密码
打开根目录
打开结果.pdf
……
```cpp
HE-14
T1 100
T2 45
T3 28
总分 173
```
……
我居然没挂分？？？？？
cao这怕是我第一次没有挂分的Day1……
（当然T3那些乱搞也一分没多得……）
然后i207M好像跟我得分与写的部分分都是一样的？
还以为这分还能看呢
然后就听说一堆人上200……
队线似乎有190……
~~反正我是D队线也跟我没啥关系……~~
cao然后就听说T2记忆化爆搜能有50，T3$O(n^4)$能有40……
（哦这似乎是因为监考的特意强调了“数据有一定梯度”）
（好像之前的时候一直都没理解过这话是啥意思？）
（不管了反正没挂分就行……）
期待后天也能不挂分……
## **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发现好像只会$O(n^2)$的20分……
cao为啥我怎么这么菜啊……然后就开始想两两配对该咋做
这个时候就觉得全身都不舒服……cao怕是吹广州的发达空调吹感冒了……
然后就一直恶心……
然后就上了个厕所，然后就突然想到了昨天没事干看集训队论文看到的个词——
# 整体二分！！！！！
对啊我可以递归处理$[l,r]$与备选集合$S$，这样的话我每次把$[l,mid]$的都开一遍灯，不就能够找出$S$的哪些点在左区间了吗？到叶子的时候$S$中必定有2个点一个是自己另一个是配对就能找出来了。
这样似乎就有**45**了呢~（cao我tm当时sb了算成一个点5分……实际上只有**36**……）
然后就开始写……结果刚要写$O(n^2)$的时候就发现似乎有点不太对劲……
咦好像只给了$\frac{n^2}2$？那我每次都要保存一遍每个点的状态，但是我只处理$<i$的边，我并没有办法修改$>i$的状态啊……
然后我发现我就是个sb……
我们每次处理$>i$的边不就行了……$<i$的状态你去查一下如果有连边那就改了呗……
然后正要开始写整体二分的时候又发现不太对劲了……
数据范围里的限制tm是完全严格的$O(n\log n)$的啊……然而我每次要扫不止一遍……
>然后这个时候就看着immortalCO就心里在想immortalcovisitworldnmsl……
然后我tm就没辙了……就接着去上了个厕所……
厕所外面人真tm多……然后就突然想到了严格$O(n\log n)$做法……？
我们注意到对于$[l,mid]$这段左区间必然会选$[l,mid]$，所以$S$中存在$[l,r]$内的是没有用的。
那么我们不妨最终令每一对$i<j$都在$i$处确定$j$，我们对$[l,mid]$开灯的时候，去$[mid+1,r]$与$S$中找与$[l,mid]$内配对的，$S$中剩下的就是右区间能够配对的，$[mid+1,r]$中未被挖走的就充当新的右区间，实际上我们每次传入的是两个集合A与B，不难发现每一层的$|A|$与$|B|$总和就是n。而且你发现A集合每次缩减的甚至是至少一半所以严格$n\log n$甚至是个上界……
（然后就去了**女厕所**……）
然后就去写了个栈$vector$的整体二分……发现过了自造大样例哈哈哈哈
这个时候就已经还剩一个半小时了……不慌写个T2的40暴力就走人……
然后写完之后发现一直输出0然后就开始心态爆炸的调……
**然后突然注意到immortalCO在我后面注视着我？？？？？？？？？？**
Wtf？？？？？？？？？？？？？
cao
~~似乎是因为我太给了然后猫才对我印象深刻……~~
然后就发现我$3×inv[3]$怎么居然是0？？？？？wtf？？？？？
然后下意识的看了开头
```cpp
#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……
估分：$88+40+36=164$
（中午听人瞎bbAg线要420不知所放……）
下午查分然后就抱着cao我啥都不管了的心态去打开了HE-14.pdf……
```cpp
T1 88（果然过不去……）
T2 40
T3 36
总分 164
```
嘿我今天又没挂分？？！？
然后我突然意识到
这是我OI生涯最后一场比赛了……
我居然一点失误都没出？？？？？？
之前因为一堆失误
每次都疯狂的翻车
NOIP从估的500多挂到了467……
省选从估的A队挂到了D……
（我tm就因为一句$j+(1<<i)-1<=n$毁一生啊啊啊啊啊啊……）
然后NOI想考几分就考了几分
然后就总分437，后来得知这个分是rk80多……就Ag稳了……
（orzErkkiErkko给给差一点进队）
（那些考600多的是tm人啊……）
然后得知我居然是SJZEZrk1HErk2？？？？？？？
这tm不太科学啊？？？？？（充分打脸十二省联~~好吧那个确实是我自己写挂了……~~）
全HE都没进队的……又断了一代……
然后就去找学上
然后**因为一些奇怪的原因**到晚上9:30（？？？）才去的SJTU……
~~SJTU：哎这难道是THU不要的？~~
不得不说那两个教授实在是太可爱了……全程都在哈哈笑……
然后……
就勉强的领了个约……（至于是咋勉强领的……这……你觉得我可爱吗？）
反正起码混了个约……
~~（upd：后来才知道THU只要429就能进面试，然后有人分比我低都有THU一等约？？？？？what？？？？？？血亏.jpg）~~
还好两年OI没有一场空……
# **AFO**
----
---
---
$upd\space on\space 2020.7.8:$
从NOI2019到今天高考结束已经过去差不多整整一年了啊……
实在是发生了太多的事啊……
---
“还好两年OI没有一场空……”
整整一年前长舒一口气说出这话的时候，“强”“基”“计”“划”4个字怕是还没出现在这个世界上……
~~也许当时已经出现在jyb某个内部文件上……~~
1月份这玩意刚出来的时候还以为就是把降一本往上提到600分左右而已跟自招怕是没啥太大差别……
然后……等到了5月发现各个学校真的都不招Computer Science……
然后就被打电话告知D类选手**不能破格入围**
nmd
这tm就是在
被推下了火坑？？？？
然而SJTU的强基还得报，然而一看到报名页面上的专业类别选择
我竟然不知道选啥
不是
我本来应该能是个敲代码的
然后我只能去选个物理之类的
woc
算了，**我不报了**
然后貌似整个竞赛班就我没报强基？？？？？？
哦值得一提的是——
我们高考前的倒数第三次语文考试的作文是这样的：
> 给你列出“自主招生”和“强基计划”对于人才选拔的宗旨
> 让你写作文**赞美**“强基计划”的变化
……不说了……一堆反语走起……
~~那一天我们整个竞赛班的同学看到这作文题心情都是非常复杂的~~