AHOI2020 游记

省选完了（一语双关），被whk折磨死，趁着上OI课，补篇游记。 ## Day 0 去`ASDFZ`试机，上下左右前后全是神仙，就我一个菜鸡... 前排是`lxm`巨佬，无限膜拜。 原来的键盘被盘出了包浆，换了一个，感觉挺顺溜。 ## Day 1 $8:25$ 开题，打开文件夹，感觉题目都不可做。 #### 先看了 $T2$ $30pts$ 白送。然后就不会了，写了溜了。 #### 看了看 $T1$ ，很可做的样子 想到先二分答案，然后线段树求出冰和火的温度极值。随便写个线段树二分就有 $60pts$ 了。 造了组大数据， $1s$ 出解，挺稳。 和暴力拍了下，也没问题。 #### 然后开 $T3$ 完了，不会算 $v$ 上界，要爆零了... #### 再开 $T1$ 发现好像可以让冰与火尽量接近，然后又写了个线段树二分。细节有点多，写了好久。 写完试了样例，没过。调了一会儿，还是没过。但是发现第二个数好像是对的，于是和 $60pts$ 的代码随便拼接下就对了。 和 $60pts$ 的代码拍了下，也没问题。 还是怕出锅，就写了个数据分治。 造了组极限数据，好像卡线 $3s$ ，有点慌。 #### 然后就交卷了，预计 $100pts$~$130pts$ 。 ## Day 2 场外毒奶有字符串。 打开解压文件夹，发现没有`string`（看来翻不了盘了），但是找到了`tree`。 #### 还是先开 $T2$ 感觉像个线段树合并板子，然后发现 $\oplus$ 和 $\sum $ 看反了... 不会，告辞，溜了溜了~ ... #### 然后开 $T3$ 一开始想把编号大的点向编号小的点连边，然后随便叉，就没写了。 打了个 $30pts$ 暴力，滚粗。 #### 重开 $T2$ 发现好像可以按位做，想了下发现是个树上差分。 先检验下正确性，写了个 $v=0$ 的点，和暴力拍了下，应该没问题。 然后写 $v\not= 0$ 的点，$O(n\log^2n)$ 随便写，然后发现每一位可以继承上一位的贡献， 推了一下就改成$O(n\log n)$ 了。 码了好久，终于过了样例。拍了下，也没出锅。测了下极限数据，要 $3s$ ，感觉要凉。 #### 然后开 $T1$ 推式子，无果，码了个暴力。 只有 $30pts$ ，不甘心，写了个随机化乱搞，没过大样例... #### 交卷，结束，预计 Day 2 $70$~$160$ ## Day 3 发现 $D1T2$ 数组开小，只剩 $15pts$... 现在 $275$封顶了。 ## 2020.6.24 分出了，$280pts$，出题人用脚造数据，$D1T2$ 多过了一个点... 但是还是不够E啊... ## 2020.6.25 省队名单出了，果然卡线没进E...