THUSC 2018 游记

Day 0

到了以后在西郊宾馆住下,放好了行李,去对面餐馆吃饭,真咸。

试机赛只有两题,第一题比较水的树状数组题,第二题是找一个高维空间中一些空间球体的切超平面,一看就是个不可做题,但是因为是提答,所以赶紧搞了点奇怪的东西尝试交上去。

然后晚上的时候去超市买东西,我买了 4 袋牛奶,3\mathrm{L} 矿泉水和 12 片面包作为这几天的早餐。

Day 1

进场之前遇到了 kls,谈笑风生了一下,拍了几张照片……

T1

进场以后先看了 T1,发现是一个要求极低复杂度的区间 LIS。但是时限 10 秒又出 10^7 次询问就让人不知道到底是 O(1) 的还是 O(\log n) 的,害得我一直以为有 O(1) 算法。肝了两个小时弄了个 20 分暴力。

T2

做 T2 的时候一看就不太可做,想着状压 DP 但是状态数太多了于是又只写了 15 分暴力。出场以后发现 k=1 其实是送的。

正解比较奇葩吧,k=0,1,3 都有 DP 解法,但对于所有 k 却是直接把 DP 放到 AC 自动机上做的,感觉非常简单。

T3

T3 是个提答,看 T3 的时候都没剩多少时间了,发现居然是个十合一,于是跑去抢分。

  1. 因数分解,秒了。
  2. 每次告诉你与三个点的距离,可是第三个点没给欧几里得距离,搞了半天最后还是 1 分。其实爬山就过了。
  3. 研究了一下发现是给函数和区间,返回定积分。完全不会所以拿了常函数的 4 分。
  4. 给一个行列式值构造一个 01 行列式,用 n\times n 的去构造 n-1 这个值比较简单,所以拿了 7 分。可以考虑递归构造,每个值分解一下把它看作一些小的行列式组成的行列式。
  5. 1 号点到其余点的最短路条数构造图,没什么时间就手玩了 4 分。可以从后往前考虑,每个值一定是若干个比它小的值求和得到的,暴搜一下就行了。
  6. 1 号点到 n 号点长度为 k 的简单路径条数,构造图,没时间做。也是暴搜一下就行了。
  7. 顺次连边,每次输出连上这条边后连通的点对数,构造图。这个仍然从后往前考虑,每次都相当于是给定和与积将其分解。
  8. 给一个语言,只有 X=A+(-*/)Bif A=B goto x 两种操作,并且大写字母不能替换为常值。要求实现 A^BA | B。感觉轻松拿 10 分啊,可能是练了 Hack VM 的原因。
  9. 是一个类似 galgame 的东西,每次给几个选项选。很轻松就能拿到 7 分,但是我刷满了好感度仍不是 10 分,所以弃疗了。正解是刷满好感度的同时在某个只有 12 的地方选 3,这怎么可能想得到。
  10. 这是 8 的升级版,多一个 toss X 操作,就是这是一个量子计算机,toss X 就是给 X 赋值,其中 p 的概率是 11-p 的概率是 0。一开始没看懂题意拿了 1 分,看懂以后发现特简单。

所以最后一共拿了 44 分。

做这题的时候发现下发的 chk 里有 Type 1,以为是个大彩蛋,但是根本用不了。后来问了猫才知道是废弃的字符串加密忘删了。

又问了下猫琨这题的量子计算机怎么实现的,猫琨称模拟 10^4 次。

考试的时候发了一个“清香鱼汉堡”,感觉还挺不错的。后来这清香鱼汉堡成了一个梗。

考完下来估分只有 79,感觉特凉。

出来遇见 stdcall,听说他只有 78

下午和晚上没干啥。

Day 2

考前坐在门口看 NTT。

进场看了看题,发现 T3 又是提答,但是是个最优化,所以先开了 T2。

T2

先打了暴力,暴力一不小心就过了后面的点……

然后推了一下发现链上是个分治 NTT,于是写了这一半多的部分分。

想了一下推广到树上应该只需要加一个链剖就行了,但是并没有想出来维护什么。

所以加上组合数的一个部分分就是 70 分。

T1

拿了 T2 的部分分后看 T1,发现是洛谷 5 月月赛题的加强版,但是这下完全不会做了。花了一个多小时尝试写了两种贪心都全 WA 了。板板在我身后死亡凝视我,所以我这题光荣爆零。

T3

因为 T3 这个提答是最优化,所以弄了第一个点的 10 分以后写了个假算法,大致就是每次选两个某条边比较接近的矩形拼起来,有一定概率不接受。这样一跑只有 #26 分,后面有一个点有 1 分却因为不满足边长的限制所以挂了。后来发现 #3,4,5 都是有特殊性质的点,#3 研究了一下拿了 10 分,后面的却因为时间原因没拿到分了。一共拿了 26 分。

考的时候发的是双层吉士汉堡,里面居然有酸黄瓜,感觉非常劲。

这次估分是 96 分,感觉超级凉。

下午讲题,发现 J 是全场唯一一个把 T1 过了的人,而且据板板称,Jode 的速度是 std 的 10 倍。

做法呢大致就是先证明连成车轮辐条形是最优的,因为平行变为交叉不会变劣。然后这样就是一个差分约束,边就只有 O(n) 条了。考场上想推出这个性质要花不少时间。

T2 的做法就是长链剖分以后,每个链的一段维护两个东西,一个是链上的积,另一个是链上除开段底的长儿子后的子树积。合并的话也只需要做两次乘法。重链剖分嘛,用 \sqrt n 条长 \sqrt n 的链组成的完全二叉树就 GG 了。

T3 就是把矩形弄成二叉树进行合并,每次跑一遍再调整。

下午接电话时段一个电话都没接到,觉得凉了,于是在 THU 里散步,绕了一个大圈子。本来还想去参观广场的,但是由于一些特殊原因没去成。

晚上林老说电话打给他的……

于是又做了下模拟面试,感觉状态非常好。

Day 3

面试 day。

我比较早地进场,还是照常做了个自我介绍。

考官问的第一个问题是我未来想研究的专业,我自然而然回答了 AI 相关。紧接着他又从 AI 扯到了社会学,然后又扯到了停课相关,这些问题幸好都是我有所准备的。

第二个问题比较简单,一副扑克牌分成 3 堆每堆 18 张,大小王在一堆的概率。我基本上没怎么思考就回答出了 \frac{17}{53} 这个正确答案。

最后还是老套路给了我一个英文材料朗读翻译。读起来比冬令营的时候感觉简单多了,冬令营发给我一个数据挖掘相关,这次是个通俗易懂的最长简单路径问题。我翻译得也比较顺畅。

J 和 zht 比较惨,都是最后几个才面试到。

下午讲座讲了若干 THU 生活,讲的时候开了弹幕感觉特别好玩,刷的最多的就是清香鱼梗,甚至给 THU 取了个“清香大学”的外号。

最后我和 J 都签了无条件 60,真是菜死了。

晚上和十几个 THU 的 CDQZOI 学长聚了餐,期间一直被某可乐瓶重击

发表评论

电子邮件地址不会被公开。 必填项已用*标注