THUWC2020

Day -inf (12.06)

thuwc 的报名网站反应是真的慢,中午特意请假去机房填表,结果被这反应速度折服了,一中午还没填完。
好事是,借着这个,我得以手动翘掉了下午的语文课,又跑去机房填表,
网站太慢了,就趁着加载的间隙打了一道题,边听歌边填表边打题,十分舒适。
然后实在是太慢了一节语文课还是不够,算上盖章一不小心把物理课也翘了一半,回来的时候正好全班人围在门口看老师做实验。
目测今年分数线不高,就迷之自信地在 12.06 这个时候就开坑写游记了。

Day -1 (12.19)

上午突然搞模拟面试?

有点懵逼,随便准备了一下自我介绍,还是中英双份的。

英语面试简直全程懵逼,问的问题基本都是这样回答的:

Q: blablablabla ? A: emm...emm.. (沉默) maybe...emm...

然后被要求读短文,发现好多词不认识,就瞎读,好不容易读完了,突然问我:
这篇文章讲了什么?
卧槽我刚才一直在纠结这个单词那个单词怎么读压根就没有去看文章本身啊。
然后 emm 了一下,就默默低下头又看了一遍。。。

Day 0 (12.20)

提前一天来到北京,说起来这是第 3 次了。

下午先去了 PKU 转了转(PKUWC 的同学今天下午报到),见到了学长,然后就回到宾馆快乐颓废。
事实上并不是宾馆,西郊宾馆早没地了,住的是公寓楼。
租了两个套间,一开始为了不与教练住分组猜拳,最后 3 个人跟教练住,4 个人跟家长住。
我就是那 3 个人中的一个。
但是超级奈斯啊,最后教练压根就不住这,这里 3 人住 3 个房间,另外一边 5 人住 3 房间。
颓到 11:30 左右就睡了。

Day 1 (12.21)

报到,发了一个紫色的包(为啥 THU 如此钟情于紫色?)。

下午一试,汉堡没 ACM 的好吃,差评。

T1 是个签到题,对于每个维度离散化一下用个扫描线 + 树状数组就差不多了,1h 做了,

T2 不会,打暴力。

  • \(q \cdot s = 10^7\) 以及 \(m \cdot w = 10^7\) 意味着跳的次数是十分有限的,直接模拟就好了。 (16')
  • 数据随机我不知道意味着什么,但是我的暴力莫名其妙就过了 pretest 。 (8')
  • \(w=10^{18}\) 意味着边永远不会断,直接倍增维护每个点走 \(2^k\) 步后的点即可。 (12')
  • \(m=n-1\) 是颗根向树,只会往根上跳,树剖+线段树维护边权,当前重链无法跳到顶的时候倍增或者二分来确定跳的位置。 (13')

T3 一开始看到题目名“某科学的动态仙人掌”就懵逼了,还好是标题党,可是还是不会,打暴力。

  • \(n, m, x\) 极小的直接暴力搜。 (4')
  • \(x=n-1\) 说明任意两个点都是可以相连的,输出 1 。 (4')
  • \(x=1\) 的话就是计算联通块数量,大概离线下来然后扫描线+树状数组可做,但是没时间写。 (0')
  • 树退化为链的情况我搞了一个莫队,复杂度 \(O(n\sqrt{n}logn)\) ,跑极限数据 7s+ ,时限 6s , 本来链是有 16' 的,但是实在卡不过,最后只过了 \(l=1\) 的那一档,此时莫队复杂度为 \(O(nlogn)\) 。 (4')

pretest 100 + 49 + 20 = 169.

晚上快乐颓废,1 点才睡。

Day2 (12.22)

上午二试。

T1 不会正解,打暴力。

  • \(n=10\) 的直接阶乘爆搜。 (13')
  • \(c=0\) 以及 \(a=0\) 的都可以状压集合中可以得到的最权值和最大值来求最后的答案。
  • \(a=0\) 时在确定顺序的前提下最后答案是关于 s 的一次函数,没有分段,因此 s 始终只需保留两个最值。 (19')
  • \(c=0\) 时最优决策只与 s 的绝对值有关,考场上我似乎是晓得为什么只需要保留最值的,但现在忘了。 (23')
  • 正解不会,但是不知道为什么上面的状压做法能过所有 pretest 。 (45')

T2 不会,打暴力。

  • \(n, q, m=10^3\) 的直接暴力搜。 (20')
  • \(m=n\) 说明非树边是唯一的,询问只需要对这条唯一的非树边分类讨论来确定它带来的影响即可,没有非树边之间的相互影响。 (11')

T3 推了好久,想了好几个假做法,然而还是只能打暴力。

  • \(k=0\) 说明根本就不进行排序,直接输出 1 。 (1')
  • \(n=10\) 的直接阶乘枚举所有可能长度的所有全排列,然后用康拓展开把排列 hash 一下,处理出所有排列的答案即可。 (4'+3')

pretest 100 + 31 + 8 = 139.

鉴于昨晚睡得太晚,本来打算下午补觉的。
真香,饥荒真好玩。

晚上三试,学习题,身败名裂。

这次是要简单地模拟 Cache 的底层工作。

我 (wo) 带 (diao) 你 (ni) 们 (ma) 打 (de)。

学习手册看得我一脸懵逼,看了整整 1 个小时才大概看懂意思,到这时候还没开始打代码。

然后看 T1 直接就是 Cache 一致性协议,出现在学习手册的最后一页,好像还综合了只读、替换、读写一堆乱七八糟的。
最骚的是不久后管理发了通知:

通知

这是暗示啊!这直接让我以为 T1 是最难的,果断弃掉,开始码 T2 。

码了前面 6 个子任务,把实现逻辑优化了一下,同样的逻辑用同样的调用,
只有不同的逻辑(也就是使用的替换算法 R )用 6 个不同的函数,
框架打完后写起来就贼方便,敲完了 6 个子任务后就先弃了第 7 个去肝交互了。

T3 交互直接在 T2 的框架上魔改,然后 6 个函数加个参数照样用,过了两个样例然而不停 WA 。
真的自闭了,后面一直在 debug 查错,肝到最后 5min 深感绝望,此时我还只有 T2 的 40' ,
大概是凉了吧。

好在最后 3min 的时候通过静态差错发现魔改的时候漏了一个地方,T2 是没有 index 的,默认都是 0 ,
而在 R = 1 的最简单的那个子任务上 index 仍然默认是 0 没有改过来,哇塞这 B 玩意害死我了,改成 index 后就成功过了 pretest 。

最后 pretest 40 + 32 = 72 。
考完后一问,好像大家都 100+ ,高如韬神 150+ ,低如 master 都有 90+
究其原因,是因为大家都只花了 1h 不到打了 T1 的 40' 。。。

好吧,我自闭了,整个 thuwc 就栽在这场学习题上了。

晚上快乐颓废,想着明天不考试,颓到了 1:30 ,饥荒真好玩,然而我活个 18d 就因为各种奇奇怪怪的东西狗带了。

Day3 (12.24)

早上 6:40 就被家长的电话吵醒,说我进面试了,赶紧起来收拾行李直接去西郊宾馆。

我擦?我才睡 5h 诶?

没办法,昨晚的咖啡还没喝完,一口闷了下去,收拾收拾就出发了。

面试人好多啊,目测 100+ ,数座位就有 150 左右。

面试,自我介绍先理性自吹一波,感觉说自己的竞赛成绩太千篇一律了,比我强的人多了去了,
于是我就有很大一部分讲了自己的辉煌的小程序历史,诸如 yzzl, pychat, retest ,还有折腾的 keoj, keblog 等等。
还提到到了 tuna 。
然后面试基本就是针对自我介绍问的,一开始问我文化课成绩,然后就问我写的小程序最满意的是哪一个,
都挺满意的这时候不能犹豫,抱着情怀我说了 yzzl ,然后对于 yzzl 的整个游戏规划,
包括已经实现的和有想法实现但是咕咕咕的侃侃而谈。
然后有问我有没有 tuna 的线下活动,emm 我一草民只是平时用用镜像水水帖子刷刷聊天室,那谈得上线下活动?

最后还问我对于昨天学习题的看法。

这个我有话说!我可以说上一整天!
时间少,题目多,分数设置得极其不合理。
学习资料写得真是牛皮,尤其是给的那三张示意图我的天啊没有任何解释你还指望那这三张几乎一毛一样图来描述 cache 与主存的关系,
这图让我误解一脸懵逼,本来对 index, tag, offset 的解释就是一句话带过,
在图上就更迷了,直接就是 [x:y:z] 下面一排 tag, index, offset ,
尤其是 offset 这个东西我至始至终不知道是个啥,盲猜是个可以忽略的东西,
可以它又特么出现在输入数据中,占了两个二进制位啊你要我怎么办,
我又只能通过盲猜输入的地址中保证 offset=0 并且找到学习手册的一句话“保证给出的地址已经对齐”来解释这个猜想。 等等等等。。。
死在这上面真的让人非常不服气。

所以我最后的回答是:

我觉得设置的很好,很考验选手的理解能力和实现能力。

:joy:

最后阅读英语短文,还是懵逼,硬着头皮乱念。

颁奖,二等奖。
(数据已删除)

晚上回去,订 11 点多的机票不知道是怎么想的,到了凌晨 1 点多才到长沙,
一个人回到寝室,大家都已经睡了,默默放下行李箱和背包,小心翼翼地走到床上,盖好被子,舒一口气。
结束了。