THUWC2020 游记

我寻思着现在还没到 2020 年啊（大雾

Day 0

早上赶火车，快进站了发现我妈身份证没带。

下午到了北京，挤地铁到了一家民宿，北京地铁感觉好破旧啊。

晚上清华的 panda_2134 爷请客吃饭，签了 pku 1= 的两个外校高一神仙 EA 和 ustze 也来了。

怎么人均 tp 啊，就我只能去工地，人没了。

睡前敲了几个板子，啊喂，我咋啥也不会了，自闭了。

Day 1

睡得很不好，一直睡不着，不知道是因为平常生物钟就不正常还是因为要考试了紧张。

不过早上起来感觉状态海星。

上午报到 + 试机，发现跟 ouuan 一个考场。

试机题目是 THUWC2018 Day1。T1 sb 题，T2 是个线段树合并，T3 字符串神仙题。

打了一会儿一抬头发现机房就只剩我一个人了，就溜了。

下午照例的照相开营踩北大，我寻思着有啥好踩的，要能来你清华还不来吗？

然后就开考了。

---

T1

• 有 $0 \sim n$ 共 $n + 1$ 个具有 $k$ 维属性的物品。
• 一开始手上拿着第 $0$ 个物品，然后依次考虑物品 $1 \sim n$，若物品 $i$ 的第 $p_i$ 维属性要比当前手上拿着的物品的第 $p_i$ 维属性大，则放下手中的物品拿起第 $i$ 个物品。
• 现在，物品 $1 \sim n$ 都已经确定了，$q$ 次询问当确定第 $0$ 个物品时，最终剩下的物品是哪个。
• $n,q \le 10^5$，$k \le 20$。

T2

• 给定一张 $n$ 个点 $m$ 条边的有向图，点的编号为 $1 \sim n$，边的编号为 $1 \sim m$，每条边有一个经过次数的上限 $w_i$。
• $q$ 次前面影响后面的询问，每次给定一个点 $x$ 和一个步数上限 $s$，求从 $x$ 开始每次走编号最小的出边，一直到走了 $s$ 步或没有出边可以走时停止，问停在哪个点上。
• $n,q \le 10^5$，$m \le 1.5 \times 10^5$，$w_i \le 10^{18}$，$s \le 10^9$。

T3

• 给定一棵 $n$ 个点的树，$m$ 次询问只考虑编号在 $l \sim r$ 之间的点有多少个极大 $X$ 连通块。
• $X$ 连通块：对于一个点集 $S$，若对于任意 $i,j \in S$，都存在一个点序列，满足序列的每一项都属于 $S$，序列的首项为 $i$ 末项为 $j$，且相邻两项在树上的距离均 $\le X$，则称 $S$ 是一个 $X$ 连通块。
• $n \le 3 \times 10^5$，$m \le 6 \times 10^5$。

---

开始以后很紧张，读题读得比较慢。

结果还没读完周围就一圈啪啪啪的键盘声，看起来 T1 是个一眼题啊。

瞪了一会儿，诶，我咋不会啊。

又瞪了一会儿，诶，我咋还不会啊，我是不是凉了啊。

强迫自己冷静下来，又瞪了一会儿。

这不是二分吗。

10 min 打完，不想拍，扔了，开 T2。

先读完题，A 掉不太可能，于是看部分分。

看起来暴力可以过 Subtask 1/2/3 的样子，这样就有 24pts。

Subtask 4 就是个倍增啊，+12pts。

Subtask 5 树剖一下就好了吧，有点难打，+13pts。

Subtask 6 就在 5 的基础上处理一下第一次询问就好了，+15pts。

Subtask 7 看上去就不可做了，那这题大概能拿 64pts，大概可以了吧。

于是就把每个 Subtask 的解法写草稿纸上，放着不打，开 T3。

「某科学的动态仙人掌」，这什么玩意啊。

暴力有 4pts，输出 1 有 4pts，找到重心然后分两棵子树做有 16pts。

一条链的情况，写个莫队有 16pts 的样子，如果 6e5 的根号能在 6s 内卡过的话，感觉挺可以的？

然后就有 40pts 了，那 day1 204pts，嗯，很稳。

此时 yy 完 T2T3 的 100pts 部分分，大概过去了 2h。

开始打吧。

从 T2 开始，先写个暴力，诶，32pts 了？

这个 subtask7 的 pretest 咋这么水啊。

然后写个倍增，44pts，此时过去了 2.5h。

然后开始打树链剖分，打着打着，诶，好像有点假？

又回去想想，好像能改真？

然后继续打，发现越打越假。

发现状况失控了，一下就 3.5h 了。

强迫自己去了趟洗手间，在洗手间里相通了。

结果回来之后硬是调不出来。

4h 了，果断放弃，扔了。

然后打 T3，暴力和输出 1 很好打的样子，但是分太少，先过。

分两棵子树做的 20 min 打完了，居然一遍过了。

然后打莫队，打着打着发现要用 set，这样复杂度就多一个 log，交上去拿了 8pts，不管了。

这个时候只剩下 10min 了，决定把 T3 暴力打了。

于是开始疯狂敲键盘，终于在还有 26s 结束的时候交上去了。

最后 T3 拿了 32pts，pretest 总分 100+44+32=176pts。

由于全程没停下来过所以发的汉堡也没吃，饿死了。

出来之后感觉这个分不算低，但也有神仙 A 掉了 T2 拿了 200+pts。

实际上 T2 是个 LCT 套路题，奈何我上次打 LCT 都不知道是几年前了（

T3 似乎是 lxl 题？毒瘤！

Day 2

前一晚睡得还行。

进了机房后发现我那台电脑的分辨率不正常，大概赛前 5min 的时候换了座位，导致快读板子没打完。

---

T1

• 有 $n$ 个函数，第 $i$ 个函数形如 $f_i(x) = a_i|x| + b_ix + c_i$。
• 你一开始有一个整数 $s$，你要按照某个 $1 \sim n$ 的排列的顺序经过这 $n$ 个函数。
• 当经过第 $i$ 个函数时，$s$ 要变成 $f_i(s)$。
• 求最终 $s$ 的最大值。
• $n,s,|a_i|,|b_i|,|c_i| \le 15$，可以使用 __int128。

T2

• 给定一棵 $n$ 个点的以 $1$ 为根的叶向树。
• 除了 $n-1$ 条有向树边之外，还有若干条从祖先到孩子的有向非树边，一共有 $m$ 条边。
• 有 $q$ 次询问，每次询问给定树上一条从祖先到孩子的路径 $a \to b$，需要求出去掉 $a \to b$ 上的所有树边后 $b$ 的子树中有多少个点无法从根到达。
• $n,q \le 10^5$，$m \le 1.5 \times 10^5$，保证无重边。

T3

• 给定一棵 $n$ 个点的树，每个点有一个点权 $p_i$，点权互不相同且 $\in [1,n]$。
• 有 $m$ 次询问，每次询问给定两个节点 $u,v$ 和一个参数 $k$，设树上 $u \to v$ 的路径经过的所有点的点权为 $t_{1 \dots l}$，求有多少个序列经过 $k$ 轮冒泡排序后会变成 $t$。
• $n,m \le 5 \times 10^5$，答案对 $998244353$ 取模。

---

T1 的数据范围看起来很状压的样子，然后很 naive 的以为维护最大值就好了。

但是如果是这样应该跟昨天一样，我题都还没读完就键盘声四起了啊。

键盘声呢？

冷静了一下，发现假了。

结果这个时候键盘声四起了，心态崩了...

大概 30min 想到了维护正负最大最小值的做法，看上去很真的样子。

然后就打了，打完交上去，结果暴力的 Subtask 1 没过，其他的都过了？？？

这 pretest 是有多水啊，心态再次爆炸。

写了个暴力交上去过了 Subtask 1 然后开始狂拍，突然意识到这是我第一次在 Linux 下对拍。

然后 TM 拍了 100w 组居然没错？

此时已经 2h 了，撕烤了一会儿，决定数据分治一下，Subtask 1 给暴力后面交状压。

不过这玩意儿挺好写的，先放着开 T2。

暴力 20pts，$m=n$ 11pts，$a=1$ 19pts，好像都很好写？

大写一通，2h 后发现 $a=1$ 的不知道为啥 WA 了，造了好几组小数据都是对的，由于只剩 1h 所以不对拍扔了。

T3 瞪了半天也只会 5pts，15min 打完。

然后回去看 T1，还是没拍出错来，自闭了。

15min 数据分治交上去，过了但是一定会 fst，但也没办法了。

此时还剩 30min，pretest 总分 100+31+5=136pts。

最后 30min 调 T2 的 $a=1$ 19pts，没调出来，炸裂。

出考场之后发现有不少人 T1 跟我一样的情况，不过我这个写法有 55pts。

晚上 day2+ 工程题，赛前拉着小粉兔让他教我二进制文件输入输出（结果发现 p 用没有。

考的内容有点 OI 相关——简单 Cache 系统实现。

花了 30min 看完了学习手册（赛后证明这个做法非常的错误。

1.5h 调完大模拟拿到 40pts。

1h 搞完 T2 的前 6 个点，+40pts。

出来之后发现垫底了，人均 112pts。

唉......

Day 3

前一天晚上因为考完所以把手机放到了被子里打算玩儿一晚上结果因为太累睡着了（

然后早上就被通知面试的电话吵到炸裂。

当时大概是 8:10，要我 8:30 到西郊宾馆。

好的，早饭吃不成了。

骑自行车赶到西郊宾馆，结果在里面坐了 3.5h。

饿成狗了。

面试先自我介绍，我说的内容大概是：

1. 我是从高一开始学 OI 的，所以现在还很菜。
2. 我创办了 X Round，办了四场，有 7.5k+ 人次参赛，也有集训队爷赏脸来打，但是这不是重点，重点是团队里其他人都是 THU 爷，就我不是，所以，嗯，THU 你们懂的。
3. 这是我的倒数第三次机会，还有一次 Summer Camp 和一次 NOI，但是要跟一群高中之前开始学 OI 的神仙拼还是很难。

面试官似乎对 XR 产生了点兴趣，于是问了问比赛的平台，规模，以及收获。

最后磕磕巴巴地读完了一篇讲图论的英语短文，也没翻译也没说主旨就放我出来了。

下午 THU 的学长做了一大堆广告，但基本没人听（

终于到了发奖的环节，老师一开口就心里一凉。

发奖前 UOJ 群里就在说 PKU 在疯狂发奖，情况不太对。

结果这个 THU 更甚，面试就有奖，没面试还有。

通 货 膨 胀

最后拿到一个 2=，恭喜 ouuan Fuyuki Itst 1=。

然后发现全场 2=，自闭了。

至于这个 2= 有啥用？

用一句别人游记里面的话就是：这玩意儿只有义务没有权利......

Day 4

回家了。

不管如何，我现在没有任何理由退役或是不全心全意学 OI。

愿，自己不再辜负自己，奇迹不再辜负奇迹。