Visits: 3993

奇奇怪怪的比赛

Day 0

早上八点起了床，然后开始颓。

颓到十点去吃了顿早饭 + 午饭，然后买了个大西瓜冰着。

然后打点模板，忘了打的啥了。

下午两点跑去把大西瓜切了一半，夏天吃冰西瓜真的爽。

然后去外校试机，实际上是去跟 EternalAlexander 和 ustze 聊天，顺便讨论一下怎么暴打作弊小朋友。

外校的校园就比二中好无数倍，足球场是真的漂亮。

晚上继续颓，颓到了十点半上床睡觉，发现睡不着，然后就睡着了。

Day 1

闹钟订的 6:45，但我恰好在 6:45 之前两三分钟醒来了，感觉如果白天有事的话早起也会很清醒。

早餐吃的热干面，其实好久没吃了，准确地说是好久没吃早餐了，再准确一点就是好久没早上起床了。

8:00 到了外校，8:15 碰键盘，8:25 开题。

瞟了一眼试题的第一页发现 T1 -lm T2 T3 -O2，好的这场比赛有喷点了。

读完 T1 会了 $\mathcal O(q \log^2 q)$ 的树状数组 + 二分，打完之后发现过不了样例，冷静了一下发现还需要用一个 multiset 记录一下位置，然后就过了样例，9:10。

读完 T2 发现啥也不会，先把裸暴力打完，9:30。

读完 T3 发现除了知道那个奇奇怪怪的条件本质上就是个线性基之外啥也不知道，看了眼数据范围发现连暴力都不会打？？？

看一眼时间，怎么 10:00 了。

去了趟厕所，在厕所中想起了树状数组和二分的 $\log$ 可以合并，树状数组上二分，一个有味道的 trick。

滚回来打 $\mathcal O(q \log q)$，打完之后跟 $\mathcal O(q \log^2 q)$ 的拍，没挂，很好。

然后跑了一组极限数据发现怎么这么慢啊，这俩复杂度分数怎么一样啊啊啊怎么还不开 -O2 啊出题人给我爬。

然后开始卡常卡卡常常卡卡卡常常常，加了快读去掉 multiset 好像从 $7\text{s}$ 优化到了 $4\text{s}$，发现已经 11:30 了感觉不会再卡了没救了就扔了。

看了眼 T2 的部分分发现有不少分的二项式定理，先水掉。

然后把那个式子各种转化发现没啥头绪，12:00 了就也扔了。

然后发现 T3 第一档部分分好像是大大大暴力，算了下复杂度好像有点卡，骂了句这什么破出题人啊暴力的数据范围都不好好出然后专心打暴力。

打完之后还剩半个小时，觉得 T3 不是我能做出来的就滚回去看 T2，但好像 T2 也不是我能做出来的。

然后，就结束了。

出来之后就自闭了，而且是题题自闭。

T1 是不是只有我会把树状数组上二分写成递归形式然后直接变成线段树了啊。

T2 是不是只有我想到了组合意义没有去想 DP 啊。

T3 是不是只有我写了个看上去是暴力实际上是个乱搞的没分代码啊。

估分：$(60 \sim 100) + 40 + (0 \sim 15) = 100 \sim 155$。

被吊打了。

水了会儿 UOJ 群发现 T2 是原题 T3 是论文题，我怎么都没做过啊。

以及这个 T2 好像就是个第二类斯特林数常幂转下降幂的经典用法，我明明学过为什么考场上忘掉了呢？学过的东西不会用那学了有啥意义呢？

不过话说回来，这似乎就是我的正常水平，这个成绩对我来说应该是非常的正常，所以也就是自闭于自己的菜，而不是遗憾。

晚上猜 Day 2 的题，感觉必有一个字符串，一个树，一个非传统题，于是打了个 SA 板子。

被兔拉去打 AGC046，秒了三题，第四题不会，1.5h 就扔了跑去睡觉了，然而事实上比赛结束了还没睡着。

Day 2

早上吃的豆皮，感觉没有昨天清醒，可能要凉凉。

全不开 -O2，差评！！！

然后把题目都看了一遍，题面很短好评，不到 5min 就看完了。

开 T1，一脸的不可做，啊，$n \le 23$ 啊，可做了。

大概半个小时写完暴力 + $\mathcal O(m^22^m)$ 的做法并且拍上了。

但是这玩意儿跑得真慢，想优化到 $\mathcal O(m2^m)$ 也可以但是就得牺牲空间的代价从 $\mathcal O(2^m)$ 变成 $\mathcal O(m2^m)$，然而 512MB 开不下 $\mathcal O(m2^m)$ 的空间！

这种时候我们应该干什么？

卡时间吗？不！

卡空间吗？不！

骂出题人！！！！！！

骂完之后权衡了一下，感觉 MLE 就直接爆零去世了，TLE 还能多拿点分，于是放弃了把时间复杂度优化到 $\mathcal O(m2^m)$ 的想法，专心优化 $\mathcal O(m^22^m)$ 的常数。

大概随便做了些比如把

for (int j = 0; j < m; j++)
    if (s >> j & 1)

这样东西换成了枚举 $\text{lowbit}$ 就快了不少，最后好像 $n \le 21$ 2s，$n \le 22$ 4s，$n \le 23$ 8s，9:15。

开 T2，重新读完题之后发现整体 $+1$ 求异或这玩意儿前几天的 AGC 不是刚考过吗，而且我之前也见过一次嗷，还记得当时兔没切掉 AGC 那题我还把他暴 Diss 了一顿。

写完反向建 01Trie 和类似线段树合并的 Trie 合并，过了拍发现，诶，怎么才 10:00？

我还有 3h 去切 T3？？？？？？这是省选？

感觉心情过于激动，跑去厕所洗把脸让自己强行冷静下来，哇，我居然不是在梦里。

回来之后开 T3，重新读了一遍题之后想了想暴力复杂度好像是 $\mathcal O(n^3md)$ 很不满的样子，看了眼数据范围——

居 然 能 过？

我阿克了？

我？？？

再次冲进了厕所洗了把脸，我估计监考都很奇怪我为啥上厕所上得这么频繁。

然后一直到 12:30 都在写 T3，正解写了 4kb 暴力 1kb，中途还忘了矩阵树定理是度数矩阵减邻接矩阵还是反过来，拿样例推了一下才确定。

这个东西真的是好写不好想，中途拍挂了无数次，正当快要自闭的时候发现最后一个错是我数据造假了，改了改之后过拍了。

我在有生之年居然能 AK 一场比赛，尽管是在不被卡常的前提下。

我上次做得这么顺的比赛还是——好像没有比赛这么顺过诶。

美滋滋了一会儿觉得不能再美了，检查了一下三题的代码，题题都拍了觉得很稳。

比赛结束出来之后发现诶好像这个考场没几个 AK 的，更美滋滋了开始逐渐担心自己有没有什么地方写挂了拍不出来的。

华师一那边好像大部分人也都拿到了我能拿到的分数，不过这是意料之中的事。

兔好像还是不会 T2，又把他暴 Diss 了一顿。

代码发下来之后，又跟 Fuyuki 和 srf 的代码拍了一下，感觉没有什么大问题。

估分：$(60\sim 100) + 100 + (70 \sim 100) = 230 \sim 300$。

两天总分：$(100 \sim 155) + (230 \sim 300) = 330 \sim 455$。

有一说一 Day 2 完完全全是超常发挥，当然题目也很奇奇怪怪。

又去水 UOJ 群，发现今天三道原题，梦回 NOIP2018 Day 1。

然后一直到晚上都在研究 T1 会不会 TLE，T2 会不会 MLE，T3 会不会 WA。

Day 3

经过了各种冥间数据的洗礼，我的分数已经变成了 $(60 \sim 100) + 40 + (0 \sim 15) + (60 \sim 100) + (60 \sim 100) + (50 \sim 100) = 270 \sim 455$。

D2T2 变成 $60 \sim 100$ 是因为一个极其弱智的错误。。。

因为每个数要在 01Trie 中存 $21$ 位，所以 01Trie 深度为 $22$，所以要开 $22 \times N$ 的空间，所以

const int N = 525010 + 7, M = 20, T = N * (M + 2);

这样本身没有任何问题。

但是我莫名其妙的加了一句 tot = n 设初值，于是在节点数卡满的时候就少了一个 $n$ 的空间。。。

D2T3 变成 $50 \sim 100$ 是因为 srf 造了数据把我的代码卡 TLE 了，而且不止是正解 TLE 了，有一个部分分也 TLE 了。。。

我真的自闭了啊！！！

Day 4

出分了。

$100+40+0+70+100+70=380$。

rk5 翻到了 rk4 进了 A 队，前面三个都是华师一。

无论如何赛前定下的目标达到了，还是比较满意的。

但这个分数显然不是高分，有很多很多的问题也都肉眼可见。

还有不到两个月就是最终的决赛了，加油加油。

总结

经验

• 该拼部分分拼部分分，也可以根据部分分剪剪枝，免得正解挂了部分分都拿不到。
• 空间大小一定要算清楚，既要避免用 STL 炸空间，又一定一定要开足。
• 学过的东西要学精，要学到考场上会用，否则就是白学了。
• 组合计数以及推柿子技能还要加强。

技巧

• 树状数组上二分只有写非递归的才能减小常数，递归的就还是线段树。