ZJOI2019 Day2 游记

不知道会怎么样呢

update: 凉了

update: 进队了…欧是真的欧

Day -3 （4.22）

雀魂好难啊。

Day -2 （4.23）

早上到机房颓颓颓，被打到自闭。

中午坐车去余姚中学，去年也是在这里呢。

住的余姚宾馆，好大喔。

到了之后继续颓颓颓，后来把手机上隔膜都删了，比赛前还是不打了 = =

走到江对面去吃了顿金拱门，店很大倒没几个人。

还写了道题，晚上洗了澡穿着浴袍串门真是爽，十一点多才睡。

Day -1 （4.24）

酒店的早餐还不错，早上走去余姚中学，过江的时候还以为没人行道，然后发现桥下面有台阶可以走上去，但是走上去了还是非机动车道 = =

到了之后已经没什么休闲养生座位了，最后坐了板凳。

上午是 zzy 讲课，感觉也还好？后来提前跑出去看妇联4了。

在万达吃了金拱门。

其实也没太大感觉，看看还是挺好看的，还看到最后 1s 什么彩蛋都没看到，出去被收眼镜的嘲讽了。

回来下午是 zzq 讲课，好像也还是可以听的。

听完跑去和鸽了一下午的人吃 KFC 了，吃完去试机。

桌子好高，凳子好矮，贺指导想必会适应一点吧。

机子速度也不是很快，$3$ 次长度 $2^{21}$ 的 NTT 跑了 1.8s，记得基本上同样代码在一试的机子上跑了 1s。

回来之后看到 yf 的讲稿好丑啊，然后改 LaTeX Beamer 改了一个晚上 = =

十点多才睡。

Day 0 （4.25）

上午就是 yf 和 myc 讲课。

题目也还行吧，但是掉线了。

中午溜出去吃了 KFC = =

下午讲课鸽了 = =

鸽了也没干什么，写了一道题，然后就一直在划水了 = =

好焦虑。

六点多去泡澡。

问了好多人应该怎么办 = =

后来随便看了一下写的博客，八点就睡觉了。

果然睡不着呢，还突然想起来还不会 Linux 下面的一些编译选项和对拍什么的 = =

赶紧背。

九点多她放学了来安慰我……最后睡着了。

Day 1（4.26）

六点半起的，好像之前就醒了，也睡不着了。

比较早到学校了，至少不像一试那样 = =

谢谢某位小哥哥送的星巴克 ⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

进考场还是有点慌的，zzy 就坐旁边 = =

开场先看了一下三道题好像都有 $40$ 暴力，感觉稳了。

由于一些原因决定开 B，先写了 $O(n^2)$ 的暴力，然后再去写了 A 的 $O(2^{3n})$ 的高斯消元。

大概 1h 不到就开始刚 B 了，走上不归路。

感觉这种点对的问题可以分治搞搞，点分想不太清楚，就写边分了。

钦定一条边之后考虑跨越这条边的路径和点对，左侧一个点在右侧对应的是一个包含根的联通块，左侧的一个点对应的联通块可以从儿子里合并上来，并且新加入若干以该点为端点的路径。

在右边维护的就是一个虚树状物。

直接拿线段树启发式合并，$O(n\log^3n)$，$n=10^5$，时限 3s，稳了。

写了 1h，然后调调调，过了小样例之后就挂了个对拍，大概在 2.5h 的时候发现边分是假的 (╯‵□′)╯︵┻━┻

出去上厕所冷静一下，想大不了再堆三题暴力 = =

碰到了 lyc，他好像以为我稳了。

回去冷静分析了一下挂掉的情况，是一条路径的 LCA 和下面的某个点的贡献没有计算到，因为边分重构的部分有问题（之前模拟赛题也这样 GG 过，这次写前虽然想过但是也没想到 = =）。

于是想到暴力把一条路径拆成三条，LCA 和两个端点再连一条，这样好像就对了。

最后调出来了，觉得自己 win 了，这种东西应该比 D1T2 难一点吧（当然最终是 lose 了）。

$5000$ 的随机数据拍了好久没挂，$10^5$ 的只要 3.1s，由于觉得本机挺慢就很自信。

后来发现一条链段错误了，好像是爆栈喔，觉得很凉 = =

开了栈跑了 90s+，冷静分析了一下之后发现没加之前想到的一个东西导致复杂度和路径长度总和有关，但是随机数据随便过 = =

加了之后链只要 1s，随机只要 1.9s。

然后爆栈的问题一顿瞎搞之后发现是 -ftrapv -fsanitize=address 的锅。

再次觉得 win 了。

大概已经 3.5h 之后了。

先把 C 的 $O(n^2)$ 暴力写了，后来再写了 A 的 $p_i=1$ 的 10pts。

陷入无所事事状态，反复幻想自己 win 了。

吃了点东西。

最后考完了。

zzy 主动问我怎么样 ⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

出来好像大家都过了 B 啊，这怎么树链剖分啊 = =

觉得也还好。

后来，听说是一个 $\log$ 的，而且 $\log^3$ 过不了 = =

好凉啊。

希望别的题别 fst 了啊..

等退役了。

update 4.29

没 fst = =

$\log^3$ 草过去了，然后就..B队队长了?..