「Summary」THUWC2020游记 | hk

运气不错

Day1

题意：

T1

一开始有一个长为 $k$ 的数组 $a_i$

$n$ 次操作，每次给出一个 $p$ 和 $b$ 数组(长为 $k$ )，若 $b_p > a_p$ ，则用 $b$ 替换掉 $a$ (整个数组的替换)

$q$ 次询问，每次给出数组 $a$ ，求最终得到的数组

$n, q \le 10^5, k \le 20$

T2

给出一张 $n$ 个点 $m$ 条边的有向图。每条边有权值 $w_i$ , 表示它被经过 $w_i$ 次之后会消失

$q$ 次不独立的操作，每次给出 $x$ 和 $d$ 。从 $x$ 开始，每次走其编号最小的出边，知道走了 $d$ 步或无路可走。

每次操作完后输出停在了哪个点

$n, q \le 10^5, m \le 1.5 \times 10^5, s \le 10^9, w \le 10^{18}$

T3

给出一棵 $n$ 个点的树，每条边长度为 $1$ ，给定常数 $X$

$m$ 次询问，每次问编号 $\in[l, r]$ 的点构成了多少个联通块。两个点联通当且仅当它们的距离不超过 $X$

$n \le 3 \times 10^5, m \le 6 \times 10^5$

开考之后脑子不太清醒，感觉 $T1$ 是思博题，但是没怎么想清楚就开始写，结果写了一个假做法，拍了半天才意识到有问题。最后写了线段树二分，前前后后总共花了一个多小时才过...

然后去写了T2暴力，写完一交直接过了前三个包和倒数第二个包（pretest好水），然后写了一下 $w = 10^{18}$ 和树的部分分。本来想写环套树的，想了想感觉有点麻烦就先看T3了

T3看了好久题才看懂题意，然后自闭了，根本不会。写了一个裸暴力和 $X = 299999$ ，加起来才8分。想 $X = 299900$ 的部分分想了好久，只想到一个根号做法（考场降智），最后一个小时写了一下，根本跑不过

pretest分数165，垫底了

Day2

题意：

T1

给出 $n$ 个函数，形如 $a_i|x| + b_i x + c_i$

给出一开始 $x$ 的值 $s$ ，要你将这些函数重新排序，并按顺序复合后，把 $s$ 代入函数中，使得结果尽量大，求这个最大值

保证答案在__int128范围内

$n, |a|, |b|, |c|, |s| \le 15$

T2

给出一个 $n$ 个点 $m$ 条边的DAG，保证 $1$ 号点能到达其他每个点。把每个点的所有出边排序后dfs得到DAG的一棵以1为根的生成树

$q$ 次询问，每次给出 $a, b$ ，保证 $a$ 在生成树上是 $b$ 的祖先。问删除生成树上 $a$ 到 $b$ 的路径的所有边后， $b$ 子树内有多少个点不能从1号点出发到达

$n, m, q \le 10^5$

T3

给你一棵 $n$ 个点的点权树，点权构成为 $n$ 的排列

$m$ 次询问，每次给出 $u, v, k$ ，问有多少个序列满足冒泡排序 $k$ 轮后等于树上 $(u, v)$ 这条路径上点权构成的序列

$n, m, k\le 5 \times 10^5$

开场感觉 $T1$ 是睿智状压，推了一会儿之后发现好像并不太好搞，有点慌。写了一个记正/负数最大最小值的乱搞状压，过了后三个包(pretest好水*2)，但是实在想不到正解怎么做，就套了个暴力和退火走人了

先把T3的5分暴力写了，剩下时间基本都在搞T2。先写了20分暴力，感觉 $m=n$ 的随便做，意识流写了一发，结果拍WA了。但是小数据都拍不出错，只好自己手动构造数据hack。考场上不太清醒，手玩的时候玩着玩着就忘记保证 $m=n$ 了，然后以为根本不可做。第二档部分分也想了半天，无果。

最后半个小时一直在打摆，玩了好久土豆OJ。F12的时候惊奇地发现可以把每道题的config调出来，点开T1的config看了一眼，发现最终测试数据中最后一个subtask居然有二十多个测试点，而pretest只有5个左右...

pretest分数125，又垫底了

下午跟着大哥清华里转了一圈，骑了44分钟的自行车，在咖啡厅聊了很久的天，还在食堂吃了饭。非常感谢大哥在即将期末考试的百忙之中还陪我溜达了一下午！

Day2+

考了cache相关

T1调了一个半小时，猜了几次终于把执行顺序猜对了

T2很快写完了，但是T3的交互库玩了半天都没看懂什么意思，最后96分自闭了

Day3

踩线苟进了面试，晚上准备了一下自我介绍，写了篇稿子

早上在候场的时候特别紧张，进考场之后感觉三个老师都比较和善。自我介绍讲了比较长的时间，然后老师就抓着我的自我介绍问了很多问题。

读了一篇关于图论的英语文章，恰好早上在准备的时候才翻到了一篇thuwc2018的游记说读了图论的文章，于是早上在Wikipedia搜了图论。感觉读得比较流畅，只有一个很长的副词不太认识，卡了半天。翻译的时候看左边的老师一直在点头233

问了一点专业性的问题，形如“你以后想从事计算机哪个方面的工作”, “你了解些什么计算机相关的前沿科技”

估计是自我介绍时间太长，问完这个问题就时间到了。没有问到数学问题，自我感觉良好

最后苟到了一等奖，居然靠面试翻盘了。jwb、hh、初三的zzm也拿了一等，cxr二等，xhb和csy三等。北大那边gc拿了二等(好可惜，差一点就一等了) 不过这次的奖似乎发得前所未有的多，一等奖也很多，可能以后真的没有大幅度的降分了吧

Summary

这次THUWC算是吃了一颗定心丸，但更重要的还是之后的省选。况且这次考试还是脑子犯浑，丢了很多不该丢的分(D1T2的环套树，D1T3的 $X=299900$ ，D2T2的 $m=n$ ，包括D1T1浪费了太长时间)，如果不是因为这次约发得多，我可能连进面试的机会都没有。以后决不能再犯这样的低级错误了

接下来的时间，要尽快把省选知识点补完，多做题，提高思维能力。希望今年省选不要留下遗憾吧！