Date: June 8th 2021
Tag: Daily
THUSC 今年在 5 月 15~16 号，写个游记记录一下。
- 至于为什么现在才写呢？
因为考完就被抓去卷文化课了，现在才难得有空写
挺好的，竞赛生涯的阶段性终点。
Day 0
夏令营之前就从学校搬出来了，那天晚上就住在学校旁边的家里，没啥特别的。
这次反正就在杭州办，也就不需要特别的奔波了。
那天晚自习嘴巴了一下 PKUSC Day 1 的题目，听说有德州扑克模拟题，害怕。
大概是 9 点下的晚自习，然后就变成睡觉人了，没有特别紧张。
没有什么记忆深刻的细节，大概是时间过得有些久了。
Day 1 Morning
6 点就自然醒了，8点不到就到了考场，结果发现没法签到。还是得等到 8 点，去行政楼签到，拿了张身份卡和一个纪念品袋子，有个 THU 钥匙扣和卡带，整挺好。
上午先是试机环节，三道简单题(A + B Problem, 模拟 Vector, 模拟 List)，后两道都可以用 STL 秒了。Linux 的桌面环境稍微有些奇怪(比如把窗口移到屏幕边缘会开启一个新的虚拟桌面，而不是放大到占据一半的屏幕)，不是很习惯，但是关系不大。
试机去拍集体照，烈日炎炎，只记得热了，还好时间不长。
之后是经典环节：授牌仪式，以及招生讲座。
感觉招生宣传有点意义不明，难道真有人不愿意去 THU？
上午很快就过去了，午饭也就在学校里吃。跑回原来的寝室，占领了阙宝的床睡了个午觉（搬出去后我自己的床只剩木板了），精力充沛。
Day 1 Afternoon - Test 1
今年形式比较特殊，传统题都在 Day 1 并且有 $4$ 题，而不是以前的 $3 \times 2$ 的形式。
不过对我这种菜鸡来说是好事，因为不确定的成分更多，拼一枪机会也就更大。
T1 搬运
有 $n$ 个物品，第 $i$ 个物品重量是 $a_i$。现在你有一个大小为 $m$ 的背包来搬运这些武平。在保证所装物品数量最多的情况下，选择物品编号字典序下标最大的方案搬运。问将所有物品搬运完需要几次。
范围：$n \le 5 \times 10 ^ 4, m \le 10^9$。
考场上以为是 dp 先跳过了这题，去做了第二题。
之后回来发现没有决策可言，于是敲了个小根堆贪心 + 线段树求后缀 $\min$，轻松过了 pretest。不会证复杂度，只知道跑的很快。
不过从这次夏令营的结果来看这题应该是过了。
正解用树套树求最小 $k$ 个数的和，没意思，而且恶心。
T2 白兰地家的西瓜
- 给定一棵 $n$ 个节点的树，每个树有点权，求树上最长上升子序列。范围：$n \le 10 ^5$。
一道霍比特人背景的题目，写了个简单 dp，转移每个点向下最长上升/下降序列的长度，然后在每个节点合并答案。正确性显然。
加上特判链和菊花图的数据点，得了 60 分。
正解线段树合并维护 dp 转移。考场上其实想到了，但是觉得每个节点统计答案的复杂度是错的，所以没写。实际上统计答案和合并复杂度相同，可惜当时没有意识到。
T3 Emiya 家明天的饭
- 给定一个 $n$ 行 $m$ 列的矩阵。每个点有一个权值 $a_i$，若 $a_{i,j} = -1$ 则称这个点是坏的。现在你需要选取若干列，若选中坏点 $a_{i,j}$，那么第 $i$ 行的贡献将为 $0$，否则第 $i$ 行的贡献为所选列的 $a_{i,j}$ 之和。最大化 $a_{i,j}$ 贡献之和。
- 范围：$n\le 20, m \le 10^6$。
当时不会，写了个 $2^n \times m$ 枚举选择的行，然后去除包含这些行内的坏点的列，其余列全选俨然最优。
拿了 $20$ 分滚出了。
正解：结束后才知道这是道简单题，FWT 做子集 $\max$ 卷积 dp 就行了。但是我不会 FWT，就算想到了子集 dp 也写不出来。所以拿了暴力分就不算亏了。
T4 校门外的树
- 通信题，用 $128$ 位二进制数据，实现对一棵节点不超过 $70$ 的树实现加密和解密。
对于 $20$ 分的数据，$n \le 65$，括号序列去头去尾恰好是 $2 \times 65 - 2 = 128$ 位。然后根据这个括号序列编码就好了。
同样拿了 $20$ 分滚出了。
正解：本质不同的括号序列数量为卡特兰数，在 $n \le 70$ 恰好略小于 $2^{128}$，所以可以算出当前树的括号序列是字典序排名来加密，和解密。
Day 1 总共 $100 + 60 + 20 + 20 = 200$，其实还行，但当时有点担心 T1 会假到 $60$ 分。
其实那天晚上没抱多大希望，就想着第二天好好打工程题，尽力而为。
（刚好早上演讲的 zyb 学长之前也是靠工程题翻盘的，还算有点心理安慰）
Day 2 Morning - Test 2
THUSC/WC 传统艺能 - 工程题。
主要考了个光线渲染和追踪技术，反正大家都不会，现学现做。
- 第一题 bitmap 图片输出，$40$ 分。
被占位符($0$)和有效符($1$)坑了，$2$ 字节的数据，我以为是 $01$，实际上是 $10$。调了两个小时左右，心态略炸，不过还是坚持往下写。
听说有人不会二进制输出和linux 操作，被这题搞自闭了，还好我平时喜欢乱搞早就学会了。
- 第二题 三维空间求射线和三角形交点，$20$ 分。
从这题往下都是提交答案题，需要用你的程序渲染出一张图像提交。
我并不会立体计算几何，很慌，但是发现头文件里基本上已经把需要的函数写好了，包括直线和平面求交，三角形的面积等等。阅读一下文档然后调用封装好的函数就行，轻松通过。
有一些 vector3, vector4 和仿射变换，不懂，但是直接用就完事了。
- 第三/四题 计算光线漫反射和镜面反射，$60 + 30$ 分。
求一个点光源到平面上一点的光照贡献，需要考虑模型遮挡。还是去说明文档里找计算公式，然后查头文件找有用的函数和类。
改来改去，漫反射都过不了，但是发现镜面反射很简单，只需要一个向量计算，于是去写镜面反射，结果发现拿不到分。后来才发现 T4 依赖于 T3，不过题目没明确写。
T3 的渲染程序运行很慢(虽然是多线程的)，大概要 10 分钟渲染一次。后来用 T4 调试就快很多，大概 2 分钟能渲染一次。(结束后出题人说文档下面有白字，提醒通过调低分辨率来提高渲染速度，吐了，这谁看得到。据说还有禁止使用 ssh 的白字提示，这是《紧跟时事》)
（对了，这次机子是 4 核心的，渲染程序是 2 线程的。如果遇到类似情况，请不要尝试调高程序线程数，或者同时运行多个程序，因为线程卡满容易死机…）
终于在最后十分钟得到了清晰的图像，从而陆续过了 T4、T3。（没错，是先过的 T4 再过的 T3）
- 之后的题和摄像机定位，光线追踪相关，没时间写了。
Day 2 最后过了前 4 题，拿了 $150$ 分。
出来之后发现大众分是 $0$~$60$ 分，感觉自己挺好的，但还是没太多想法。
Day2 Afternoon
午饭出去吃面，同时稍微和周围的同学讨论了一下，发现自己分数还可以，两天不保守估计有 $200 + 150 = 350$ 分。不过不知道今年究竟什么情况，心里还是有所期盼，但是又不抱过大希望。
下午到报告厅闭幕式，先放了很久 AI 和进化相关的纪录片。然后开始讲题，总体来说 Day1 偏简单，都是可做题。Day2 槽点众多，吐槽持续了至少一个小时，远超预期，并且之后还放了写和光线渲染相关的资料视屏，挺有意思。
不过因此闭幕式真正开始时间推迟了一个多小时，很多外地老哥为了赶火车都先走了。
说是闭幕式其实也就是发纸，发完就结束了。因为今年 THUWC 没办，所以这次纸发的特别多，整挺好。
然后说一下最后的结果：
fAKe 这次没有打铁!
细节以后再补吧，想睡觉了，BYE。
9.6 补记：
Summary:
不论从什么方面看，这都是一件极大的好事，毕竟在高一就搞定了，属于是没想到。
不管是靠运气还是实力，或者二者并存，结果已经确定了。
现在开始就可以全心投入文化课了，不需用左顾右盼，或是任何形式的犹豫。
最近还经常被 Q(班主任) “正义演讲”——“你们比别人多大半年时间，要好好努力，目标明确”，这话倒也没错吧(听起来觉得自己优势好大)。
只是要和 OI 说再见了，尽管最后几个月的停课已经将我对其的热爱消耗殆尽，但还是有些可惜。
在 OI 生涯中以除了保送之外最高的终点结束，按理说是毫无遗憾了，那就简单的说再见吧。
再见 OI，退役之日至矣。
