HEOI2019游记

## Day 0 在火车上瞎学了下BM算法顺便复习了下单纯形的板子。 早早地到了燕大以后先去吃了个午饭。然后午睡时发现房间太吵于是换到了后楼。 下午试机的时候就随手写了点板子就摸了。 晚上随便逛了逛洛谷和博客就滚去睡觉了。 ## Day 1 一上来先按顺序读了三道题，发现啥都不会，开始慌了。 于是开始搞T1，过了两分钟发现就是超级钢琴那题，然后在加个可持久化01trie就行了，然后开始糊代码，写完了直接过了小样例，然后发现死活过不了大样例。眼查了5分钟以后开始对拍，一开始拍权值比较小的根本没问题，然后把权值范围调到 $2 \times 10^9$ 以上才会挂。调了一会发现好像是32位机上$\text{long long}$的问题，改好了以后就拍上了。 然后搞T2，随便想了想发现是个后缀树优化建图然后跑拓扑排序的题。然后意识到直接搞好像只有80分。于是不管了，直接冲上去写个80分的跑路了。~~调了半天清空数组。~~ 然后开T3，发现？？？什么玩意，我好像一分都不会。打开了前几个点的数据，发现好像是个数列，直接糊了个BM上去，然后调不出来了。于是开始盯着数据看，半个小时以后发现好像是个等比数列，公比是19。结合提示，又猜出了那个爆int的点。接下来我就啥都不会了，~~开始摸大鱼~~。 出考场以后十分崩溃地发现大家好像都会T3后边的分啊，那我岂不是退役稳了。 于是绝望地度过了一下午+晚上，发现我T2还挂了40（SAM加nq的时候忘跳parent了）。 ## Day 2 和第一天剧本差不多，一上来先按顺序读了三道题，发现啥都不会，开始慌了。 还是先搞T1，发现50分好像很好拿，然后就不会了，于是糊了个50分暴力就跑路了。 再搞T2，一开始先想了个$\mathcal{O}(2^n \times n)$的暴力，又想出了链的做法，于是以为有60分就开始写了，写完以后发现过不了样例，发现假了。又开始慌了，于是赶紧开始YY新的做法，从链的做法推广了一个新做法:每次选权值最大的没被覆盖的点，然后从大到小依次考虑每个没覆盖的点，能加就加，好像挺对的，写了个$\mathcal{O}(n^3)$直接过了样例。然后发现这玩意好像跑不满，我猜出题人没卡，于是加了个$\text{random\_shuffle}$就跑路了。 再开T3，和昨天一样，发现？？？什么玩意，我好像一分都不会。于是开始看部分分，一开始想了$k=1$的好像可以长链剖分，然后发现自己其实并不会。于是开始看各种部分分，挑了半天发现我只会4个点的，于是开始糊代码。 大概在11点半的时候就写完了全部代码，然后开始反复检查文件名什么的。在12点多一点的时候神仙ztb提前离场了。就这样摸了一个小时。 考完以后发现全世界都会T2，就我不会，我写的暴力还可能是WA的。又虚了，开始考虑回去怎么学文化课。刚上火车得知LOJ上有数据了，赶紧测了一发T2，发现我的做法好像没问题，还能把$\mathcal{O}(n^2)$的点也过了，于是松了一口气，发现不会死的太惨。 过了一会老师告诉我好像擦线进队了。我：？？？？看了一眼发现是省队最后一名。 于是又可以继续搞OI了 ~~进 队 大 成 功~~ 晚上看四位神仙在UOJ群中疯狂嘲讽：    Update：