Day 0

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

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

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

Day 1

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

T1

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

T2

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

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

T3

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

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

所以最后一共拿了 分。

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

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

 

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

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

出来遇见 stdcall,听说他只有

下午和晚上没干啥。

Day 2

考前坐在门口看 NTT。

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

T2

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

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

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

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

T1

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

T3

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

 

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

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

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

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

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

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

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

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

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

Day 3

面试 day。

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

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

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

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

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

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

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

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

总结

感觉这次遭的最惨的一点就是开题顺序,两天都在没有拿到几分的题上花了太久时间,而在提答这种时间与分数成正比的题上却没有做到很好,感觉非常可惜。对于有提答的这种套题类型的时间分配还是缺乏经验,经常容易给提答留的时间不够。总之就是以后再有提答题的时候要注意时间分配。

如果题能公开的话我还是很愿意改一改的。