2020省选自闭记

<area/> <base/> <br/> <col/> <command/> <embed/> <hr/> <img/> <input/> <keygen/> <link/> <menuitem/> <meta/> <param/> <source/> <track/> <wbr/>

英文标题（链接末尾）叫 “HBSX2020” 是因为前两年文件夹名字都叫 “HBSX201X”，虽然今年是 “NOI省选”。

子标题带“2020 省选”是因为听说这样更利于 SEO。

2020 省选 Day 1

因为曾经遇到过：

1. 模拟赛自己写的 ${\log }^2$ 树状数组外面二分比别人写的 $\log$ 线段树里面二分快；
2. NOIP2018 D2T1 在所有 OJ 上不开 O2 都过不了，但在 8700k（全国统一评测机）上过了

这么两件事，于是不假思索地否掉了 T1 的线段树二分写了个树状数组外面二分甚至还花了半小时给这个做法卡常最后用时 8s 左右。

做了上述这件事的我自闭了。

打开题面立刻看到编译选项有 O2，但下面又写了“评测时不开启任何优化选项”。

考场是 Windows 10 + NOI Linux 虚拟机。往虚拟机里拷贝文件的时候虚拟机卡了，然后在任务管理器里直接 kill 掉了，然后就打不开虚拟机了。

后来对拍的时候不小心给暴力搞了个非常大的数据，然后 MLE 了，然后就死机了，然后就重启了，然后就可以进虚拟机了。

2020 省选 Day 1.5

就一天没处理 CP Editor 相关的事，结果就遇上了 CP Editor 除了我开的 PR 的 PR 最多的一天，有两个 first-time contributor，处理 PR 就搞了一下午。有新 contributor 倒是好事 ，毕竟过不了多久我可能就要文化课了。

晚上写了 AGC 的 A，然后看了眼 B 好像不太会，看了眼 C 会了但懒得写了。

2020 省选 Day 2

打开题面立刻看到编译选项没有 O2，但下面貌似改成了（也可能是我 Day 1 看错了）“评测时除编译选项外不开启任何优化选项”。

发现 T1 好像会，在草稿纸上写了下转移方程后就开始写，写完发现过不了大样例，然后发现假了，而且比较 naive 地改对会让复杂度变成 $O(n+2^m{m}^2)$。想了一会儿后发现一个空间复杂度 $O(2^{m}m)$ 的做法时间复杂度是 $O(n+2^{m}m)$，但貌似要 MLE，于是把 vector 都换成了数组，但还是爆了。然后发现一个性质：$n$ 只有 ${10}^5$，而那个非常大的数组每个值最大是 $\frac{1}{2}n$，于是不会爆 unsigned short，然后就卡到了 $470\mathrm{M}\mathrm{i}\mathrm{B}$ 左右。

然后感觉 T2 比较可做，于是先把 T3 的暴力写了。感觉 Matrix Tree 没有那么好写，于是先只写了 $30$ 分。

T2 先打了个暴力，然后发现貌似可以 $O(n\sqrt{n}+n{\log }^{2}n)$，然后发现用 bitset 可以 $O(n\sqrt{\frac{n}{w}}+n{\log }^{2}n)$ ($w$ 是字长, 一般为 $32$)，这时已经快 12 点了，T3 的 Matrix Tree 还没写，很方，但因为（当时以为）有 30/70 分（实际上是 30/90 分），就还是写了，然后很快就过了大样例，然后小数据过拍了，然后大数据没过拍，然后发现是 bitset 开小了，调了之后过了，然后在 Linux 上测了大样例，然后在 Windows 上测了链跑了 $4.3s$，感觉 8700k 肯定能过，但还是最好在 Linux 上测一下，然后在 Linux 上段错误了，然后调了一会儿数组大小，然后想起来可能是爆栈了，然后发现自己并不会在 Linux 上开栈，然后就自闭了，然后没时间了，Matrix Tree 写不了了，考试结束了。

出考场听说 T2 是原题可以 $O(n{\log }^{2}n)$，听说 yls T2 写的和我是一个东西但没用 bitset，听说机房电脑很快所以不会比 8700k 慢太多，听说 Day 1 前两题很简单，听说 wcx 500+。