THUSC2021 划水记
$\text{NOIP}$ 和联合省选考成小学生水平之后，觉得自己又双叒叕没机会去 $\text{T}$ 或者 $\text{P}$ 了，很沮丧。
记得 $\text{THUWC2019}$ 的时候就没有能够参加，机房神仙 $\color{black}\text{Z}\color{red}\text{cus}$ 当时拿到了一等约。我十分沮丧，觉得自己如果运气好或许也能够拿到一些成绩，但是去不成就是去不成......
结果竟然还能来，能来就好好考吧。
Day -?
在外面集训，然后面了 $\color{black}\text{Q}\color{red}\text{iuly}$ 神仙，$\color{black}\text{Q}\color{red}\text{iuls}$ 真的好强啊/se/se/se，而且为啥初二身高就可以 $180+$，慕了。
几天的考试要么考的自认为还比较靠前，要么直接垫底，很自闭。感觉要是是垫底那几天那个状态，今年又没机会拿约了啊......
Day 0
到了杭州 不过为啥清华的活动不在清华办啊 不懂，记得 $2019$ 年就来过学军，正好就是西溪校区。当时被踩到怀疑人生，完全是被降维打击。希望今年可以有所不同吧......
记得当时在学军边上找到一家不太起眼但是味道不错的餐厅，准备再去一次。
晚上赶紧复习一下，翻了翻板子发现自己啥都不记得了，感觉要直接凉透了。然后听说了 $\text{THUSC2021}$ 的考试分布，$\text{Day1 5h 4}$ 题，$\text{Day2 4h 1}$ 题。
？危了啊，考两场还有工程题？不管传统题了，然后去翻了翻 $\text{THUWC2019}$ 那道关于 $\text{cache}$ 的工程题，读了 $\text{20min}$ 的 $\text{handbook}$ 结果只看了 $2$ 页，被 $\color{black}\text{l}\color{red}\text{k}$ 怒 $\text{D}$ 要凉透。
完全没心情了，于是 $10:00$ 就睡觉了。
Day 1
早上按时到了学军，然后去报道。发了胸牌 感觉有了我来过的实感，还送了一些小礼品，很赞。然后发现胸牌是紫色的，意味着不在西溪校区考试，还要坐车去紫金港校区，无语子。
见到了很久没见的 $\text{l}\color{red}\text{indongli2004}$，然后就在那里等等等，接着去参加讲座之类的。至于讲座......我知道 $\text{THU}$ 很好但是咋进啊我不会啊。
中午甚至不能回酒店，所以买了学军的餐票，好贵啊 $\text{60}$ 块两餐。我校大多数人都在紫金港，然后一起坐车去了。
在紫金港吃完饭进考场，赶紧配 $\text{vimrc}$，发现自己又双叒叕忘了，靠着自己的记忆强行编了出来。$\text{THUSC}$ 是 $\text{pretest}$，登上网站发现试机和考试无缝衔接，于是写了个 $\text{A+B Problem}$ 就摸鱼去了。
考试延后了 $\text{15min}$，到时间之后扫了一下题面。
$\text{T1}$ 好像是个奇怪的东西，数据范围 $50000$ 是什么东西啊这好像是 $\mathcal{O}(n\sqrt{n}\log n)$ 的范围吧，害怕。$\text{T2}$ 就是个树上最长上升子序列，好像十分送。$\text{T3}$ 叫 $\text{Emiya}$ 家明天的饭，瞬间唤醒了我在考 $\text{CSP-S 2019}$ 的时候被那道题支配的恐惧，先扔了。$\text{T4}$ 是个奇怪的东西，当时都没意识到是个通信题。
顺着开，$\text{T1}$ 中字典序最大这个东西不是很好做，但是可以沿用之前模拟赛的一个思路，考虑第一个数字编号是多少。然后问题就转化为多次求编号 $\ge x$ 的位置中最小的 $k$ 个数字的和，带删除元素。
如果不带删除，可以直接主席树，再加个二分做 $\mathcal{O}(n\log^2n)$，带删除是不是直接树套树就行？$\mathcal{O}(n\log^3n)$ 虽然看起来很阴间但是很符合数据范围的样子。
然后意识到自己不会写树套树了，又花了 $\text{30min}$ 纠结有没有别的做法，$\text{1h}$ 了发现不行，想着 $\text{T1}$ 签到题必然要切，于是硬着头皮开始写。写了好久，出了各种奇怪的 $\text{sb}$ 错误，大概在 $\text{2h-}$ 的时候 $\text{pretest passed}$ 了。
然后看 $\text{T2}$，肯定是在 $\text{LCA}$ 处考虑答案的贡献，但是是不是不太好合并啊，然后立马胡了一个长链剖分+线段树合并的做法，复杂度是 $\mathcal{O}(n\sqrt{n}\log n)$，$n=10^5$ 一脸过不去。想了想发现可以换成点分治，就是 $\mathcal{O}(n\log^2 n)$，感觉对了，于是开始写。
写了一半发现自己连点分治都不太保证能很快写对了，感觉是手速场如果花时间在 $\text{debug}$ 会血亏，于是又停了下来。又想了想感觉可以 $\text{dsu on tree}$，用线段树维护一下即可。
这个很好写，复杂度也一样。很快就写完了，一交只有 $\text{60pts}$，最后 $\text{RE}$ 了。手测了一个链的情况，发现竟然过不了？？？但是我过了 $\text{pretest}$ 那个包啊？？？害怕极了，赶紧改掉然后开大数组，交了几发之后 $\text{pretest passed}$ 了。觉得不稳，于是写了个拍，拍上了。
这时候才 $\text{2h 40min}$，觉得很稳，甚至觉得可以切三题 我在想屁。
赶紧看第三题，很 $\text{naive}$ 的想法是 $\mathcal{O}(2^n)$ 枚举留下谁，然后当前答案是枚举的子集可以接受的菜品的极大子集。但是转化之后不会维护，于是就开始自闭了。
中途想了想，是不是可以 $\text{FWT}$ 维护一下呢？感觉不太会，然后就在 $\text{T3}$ 和 $\text{T4}$ 之间左右横跳。$\text{T4}$ 第一个 $\text{subtask}$ $n\le 65$，但是整个题 $n\le 70$？感觉是个 $\text{nb}$ 题，我甚至连第一个包都没想到怎么做 真菜。
就这么荒废了 $\text{1h}$，发现不行了，于是赶了 $\text{T3}$ 的 $\text{40pts}$。交一发只剩 $\text{20}$，很不解。原来我有一个包写了个线段树，然后可以卡到一组数据 $\text{2min}$，自闭了。不想卡常，于是就接着思考。
显然是想不出来的，于是就 $\text{pretest 220}$ 滚粗了。出来发现被神仙 $\color{black}\text{z}\color{red}\text{xyhymzg}$ 爆踩了 $\text{40pts}$，不过也正常，毕竟他一直吊打我。$\color{black}\text{Z}\color{red}\text{cus}$ 反正有约，但是 $\color{black}\text{m}\color{red}\text{entos}$ 和 $\color{black}\text{d}\color{red}\text{eltax}$ 考炸了， $\color{black}\text{l}\color{red}\text{indongli2004}$ 也考的不太好......
不过高二学长 $\color{black}\text{h}\color{red}\text{uhao}$ $\text{AK}$ 了，$\color{black}\text{l}\color{red}\text{k}$ 有 $350$，$\color{black}\text{C}\color{red}\text{raZYali}$ 也比我高，果然还是有差距。
感觉比平均分不知道低了几百分，有些小沮丧。听 $\color{black}\text{z}\color{red}\text{xyhymzg}$ 说 $\text{T3}$ 就是个 $\text{FWT}$ 的东西，没细想但是还是因为往这方面想了但没过而难过。
晚上 $\color{black}\text{l}\color{red}\text{k}$ 说让我明天工程题好好写，做好了还是能翻的。但是我晚上甚至没复习，摸鱼摸到 $11:00$ 就睡觉了。
Day 2
上午考试，所以起床更早了。在去紫金港的路上睡了一下，还顺便再看了看 $\text{cache}$ 的 $\text{handbook}$，仍然发现自己完全没想法，准备凉凉。
到了考场配置好电脑，发现开考时间变成 $9:00$，很阴间。稍微想了想昨天 $\text{T3}$，突然意识到是扇贝题，感觉自己把顺风场打成憨批水平，很自闭。
接着开考了，下载文件下了一百年。
打开文件夹，发现里面一堆代码文件，打开各类 $\text{PDF}$ 资料：《线 性 代 数 与 计 算 几 何》，《光 线 追 踪》，感觉危了。
先快速扫了一下三个文件，看了看 $\text{T1}$，不知所云。出题人说 $\text{T1}$ 可以不做，但是看了看发现分数是 $\text{T2}$ 的两倍，而且说可以对后面有帮助，于是还是开始做了。
大概就是让你写一个转 $\text{bmp}$ 文件的代码，实际上就是跟着他题面上的东西模拟。但是由于我技艺不精，语文水平也不行，所以读了一百年还没读懂。最后依照他给出的那个逆实现代码写了出来，过了 $1,3$ 两个样例，第 $2$ 个样例长宽不是 $4$ 的倍数，意识到是没有补全到 $4$ 的倍数。
于是我在后面补了字符 $'0'$ 而不是数字 $0$，喜提 $\text{30pts}$。感觉如果是 $\text{pretest}$ 那也太水了，十分害怕于是赶紧问了问是不是 $\text{pretest}$，回复说已经是最终结果了，那就海星。
于是扔了去做 $\text{T2}$。发现他需要根据三个点确定一个平面的方程，我完全不会 流下了没有几何基础的眼泪，于是赶紧去找找有没有相关的东西可以用。没想到还真的找到了，在某份代码里一个叫 $\text{Plane}$ 的结构体中间给出了这样一个构造函数，于是就用上了。他还需要输出交点和法向量。笑死，根本不知道法向量是什么，于是我甚至没有管那个法向量，直接渲染，一遍 $\text{Accepted}$ 了。数据真的水啊，但是已经是最终结果了所以很香。
此时发现提交的是一张图片，也就是说可以看见自己写的代码渲染出来的图，突然觉得有意思起来了。
下一题需要计算一个点光源对一个位置的光线的贡献。翻了翻 $\text{guide.pdf}$，发现了十分赞的积分柿子，反正我是高数辣鸡所以直接略过了。然后找到了点光源对点的贡献，直接套上去，渲染一波发现 $\text{WA}$ 了，很害怕，这东西完全没法调吧......
仔细看了看出题人的提示，他说需要判断光源与点相背的情况，那就判一下点积。再渲染一次，很快出解了，交上去还是过不了。
十分迷茫。猜想是因为函数中有一个 $\text{Model}$ 类型的参数，我完全没明白要怎么用。猜了猜感觉是用于判断光线被遮挡，如果遮挡了那么光线就是 $0$。
赶紧去翻库，找到叫 $\text{Model}$ 的结构体，发现有一个叫 $\text{GetIntersection}$ 的函数，返回距离之类的。赶紧加上，根据代码里的提示判断了一下。运行渲染，发现跑得巨慢，估算了一下感觉要 $\text{10min}$ 才能渲染完，很害怕。心里想：”千万要过啊不然今天就要垫底了到时候没约是不是很尴尬“。跑完之后欣赏了一下那张图，感觉很漂亮，交上去并双手合十。
发现过了！十分快乐了，赶紧继续做，发现 $\text{T4}$ 就是给定入射向量和法向量，让你求出射向量。公式在 $\text{guide.pdf}$ 里贴脸上了......渲染得很快，图片里是一堆球，看起来很对。于是一发交上去直接过了。
这时候还剩 $\text{1h-}$，看到下一题叫做 $\text{panorama}$，是全景的意思。当时想着一定要切掉，但是可惜的是最后也没能通过。
于是 $\text{Day2}$ 是 $30+20+50+40+0....=140$，出来的时候感觉写的并不是特别好，但是至少是个大众分的样子。
和我校同学交流了一下，惊奇地发现我竟然是校内第一。感觉好梦幻啊，好像靠今天把总分翻到校内第 $3$ 了，赞赞赞。
吃了饭赶紧回到西溪校区听讲题，发现原来第一天的题都是完全可做的，感觉很可惜。接着工程题出题人上来讲了一下，我的 $\text{panorama}$ 做法是对的却没能通过，还是有些难过的。但是听到了梗：“连雪球都在卷”....../jk/jk/jk
于是闭幕式又双叒叕延后了，整个两天是不是就没几个活动是按时开始的啊，好无语。
先播了一堆 $\text{THU}$ 的宣传片，刷手机去了完全没看，最后开始发“一些比较重要的纸”。感觉自己心里已经差不多意识到能拿到一等奖了，但是就是怕 $\text{FST}$。
$\color{black}\text{l}\color{red}\text{k}$ 要我跟他赌，说我一定是一等奖，赌一杯奶茶（
觉得赌就赌吧，拿了一等请神仙一杯奶茶也不是啥问题，没拿到还可以嫖奶茶，怎么都不亏（
一个一个省地报，$\text{HN}$ 稍微需要等一会。高二学长 $\color{black}\text{l}\color{red}\text{k}$ 和 $\color{black}\text{h}\color{red}\text{uhao}$ 还有高一的 $\color{black}\text{Z}\color{red}\text{cus}$ 都已经签完了，于是这次发了奖的只有 $\color{black}\text{z}\color{red}\text{xyhymzg}$，$\color{black}\text{C}\color{red}\text{raZYali}$ 和菜鸡我。$\color{black}\text{d}\color{red}\text{eltax}$ 和 $\color{black}\text{m}\color{red}\text{entos}$ 都没能拿到约，还是很可惜的。
虽然但是为什么发个奖甚至不告诉你是几等奖，我怎么确定“优秀”是几等奖啊喂
闭幕式结束之后赶紧赶去了高铁站，和 $\color{black}\text{l}\color{red}\text{k}$ 去吃了必胜客。想去找 $\color{black}\text{Q}\color{red}\text{iuly}$ 但是因为不是一班车所以最后还是没找到。到了高铁上发现竟然是一等座 第一次体验了高层社会的高铁生活，于是在高级的座位上来补这篇游记......
Summary
本次考试可以说是运气比较好的了，$\text{Day1}$ 没能发挥出应该有的水平，但是 $\text{Day2}$ 可以算是发挥得很不错，最后还算是保住了。
感觉自己到现在场场被 $\text{T3}$ 杀，不管是联赛，省选还是这次 $\text{THUSC2021}$，说明到了考试的中期后期我的思维能力下降比较厉害，同时这个位置的题确实需要一些思维。所以以后还是要多多锻炼思维才行。
继续加油！