XCPC欢乐赛体验

· · 个人记录

人在济南。昨天下午 XCPC 欢乐赛，搞的挺正式的，有五彩斑斓的气球插来插去。还有大量（？）奖金。

比赛名字就取【太伟大了 syk】，企图增加 rp。

三人一机，事实上是三个人机。可怜队爷当苦命打工人（坐在机子前 5 个小时写代码，只有小小一段时间换了人）

下午一点，比赛开始。下发了三份纸质题面，厚厚一坨。图方便直接看了 A，发现是个树形 dp 就通报给队友，然后飞速拿下（提交时间为比赛开始后的 1 分 53 秒）首杀。

看到某个队也是一分钟过 B，然后发现是个 if()cout<<"Yes"; 的题，于是在 00:03 拿下。

又看到 K 首杀没了，这就清楚 K 也简单，一眼瞪出答案 m^{n-k}。队爷写个快速幂，过样一遍过，此时时间来到 00:11。

看榜发现我们竟是榜一。可能与 A 有一定关系。

接下来 E,I,J 同时开，I 被队爷瞪出是矩阵乘法，挂在后场写。然后另外一个队友看出 J，于是换题写 J。但是写着写着，假啦！然后我看出 E，简单说了一番队爷写 E，过样例一交，WA 了！罚时吃饱（胃口太小）。后来随便改了一些可能会出锅的问题，奇迹般的又 A 了。来到 00:43，但是一血被抢了。

一看榜，还是榜一。但是很多人写了 3 题。几个人又看了一眼其他的题，发现 M 过的人比较多，比较典型的字符串哈希最小值表达，写了一刻钟在 00:58 A 了。

另外一个队友看起 G 来，发现是个倍增，糊了一通过去了，时间来到 01:07，超第二两题！稳了。

接下来 J 想出了新的解法，写着写着写着写着一遍过样就 A 了，拿下 J 一血，进一步拉开差距。

还剩 C，D，F，H，I，L。C，H 都是随机化数据，D 树，F 一眼有无与伦比后效性的状压定平。不知道从何下手，各题都有思路，但都写着写着假了。最后看到 C n=5 \times 10^4 ，于是写个暴力冲。然后注意到一些性质，在关键的地方 break 一下。3s 时间轻松跑过。这个时候时间来到 02:30，进入半场，领先第二一题。 于是半场开了香槟。

接下来，几个人瞪着 D,F,H,I,L，队爷感觉 I 有新思路在写，然后其他人就看着题目坐牢。

此时 I 被写好，交了一发寄了。原来 $T=10,n \le 500$ 但是队爷看错了范围，写了 $O(Tn^4)$ 的奇怪东西，啊？？？？$5s$ 根本过不去。他添加了一些优化，交上去还是 T 飞。 三小时左右，他用 dijk 优化为 $O(Tn^3 \log n)$，加了剪枝还是 T 飞。此时比较绝望了。 离封榜还有 $14$ 分钟时，一锤定音的事情出现了，榜一此时又切了一题 D。而且后来居上一个 $8$ 题队。虽然在封榜的时候位于榜二，但是由于只有前 $3$ 个队有排名奖励，还是很慌的，而且我们榜一已经无望了。 封榜的时候，另一个队友说用 KD-tree 维护什么什么可以写 L，我想出来 D 的点分治，但我看他很决绝于是就让他先写 L。但他不会写 KD-tree 就让队爷写个板子。大概还有 $30$ 分钟结束的时候写好了。 可是问题是根本调不好，不知道是什么原因，一个人认为是 KD-tree 的问题，一个人认为是写的 check 的问题，最后比赛结束，遗憾离场。 问题是看到榜，一个原来只切了 $6$ 题的人出现三题黄色的 $+x$，这意味着撤榜后他们可能翻到 $9$ 题！ 而且原来的一个 $8$ 题的也有 $+1$，可幸他们的是 WA 的，但是那个 $6$ 是真的给翻到 $9$ 题了，只拿下榜三。 赛后总结，L 压根不是这么写的，为什么不让我写 D！I 的做法没错，但是实现的复杂度不是 $O(Tn^3 \log n)$，因为 dijk 放入了两个参量，可能时间复杂度是 $O(Tn^2 m \log n)$，而 $m \le \frac{n(n-1)}{2}$，笑了。 F,H 赛时无人写，一个线段树 + vector，一个奇怪 dp，$O(3^nnm)$。 最后只是榜三，混了个【原神小月卡】一人一张的奖项，$30$ 元；两题一血，一题每人 $15$，最后相当于一人拿 $60$。但是榜一一人拿了 $150$ 多。还是很遗憾的。 最后晚上讲题的时候，队爷被诚邀上台发言，讲述被翻的心理历程，只能说是鞭策到位（）（）（）（）（）。 把 $8$ 个气球一人拿几个分了，最后也不知道扔哪里了。