AHOI2020 游记

· · 个人记录

省选完了（一语双关），被whk折磨死，趁着上OI课，补篇游记。

Day 0

去ASDFZ试机，上下左右前后全是神仙，就我一个菜鸡...

前排是lxm巨佬，无限膜拜。

原来的键盘被盘出了包浆，换了一个，感觉挺顺溜。

Day 1

#### 先看了 $T2 #### 看了看 $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...