THUSC2021游记

THUSC2021游记

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 的白字题式,这是《紧跟时事》)

终于在最后十分钟得到了清晰的图像,从而陆续过了 T4、T3。

  • 之后的题和摄像机,光线追踪相关,没时间写了。

最后过了前 4 题,拿了 $150$ 分。

出来之后发现大众分是 $0$~$60$ 分,感觉自己挺好的,但还是忐忑不安。


Day2 Afternoon

午饭出去吃面,同时稍微和周围的同学讨论了一下,发现自己分数还可以,两天不保守估计有 $200 + 150 = 350$ 分。不过不知道今年究竟什么情况,心里还是有所期盼,但是又不抱过大希望。

下午到报告厅闭幕式,先放了很久 AI 和进化相关的纪录片。然后开始讲题,总体来说 Day1 偏简单,都是可做题。Day2 槽点众多,吐槽持续了至少一个小时,远超预期,并且之后还放了写和光线渲染相关的资料视屏,挺有意思。

不过因此闭幕式真正开始时间推迟了一个多小时,很多外地老哥为了赶火车都先走了。

说是闭幕式其实也就是发纸,发完就结束了。由于今年 THUWC 没办,纸发的特别多,整挺好。


然后说一下最后的结果:

fAKe 这次没有打铁!

细节以后再补吧,想睡觉了,BYE。


$\mathfrak{the\ End}$


 
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×