Star's Blog

概览#

相对去年来说还是比较惨的

学校排名 132，险胜中国石油大学（北京）。

第一场#

和题目内容和代码相关的在档案库

上来 wm176 猜 I 和 M 是签到，然后我读 I 发现不对，接着读 M 发现真是签到，然后 3 min 的时候切掉了，然后看榜发现 F 也是签到，再切一个。

然后在看榜发现 A 和 C 都有过的，我看了一眼 A 大模拟丢给了 wm176，然后读 C 发现本质是一堆偏序构成的图的拓扑排序，然后经过 MoScenix 的高速推理发现没什么问题，用优先队列跑 topsort 在 30 分钟的时候一发过，完美开局！

wm176 和 MoScenix 研究了一下 A 似乎有初步结论了，然后我下来开始读其他题（唯一一个过六级的人是这样的），感觉本质是大模拟放心丢给 wm176 写了。

然后我读了很长一会儿题，D 是计数，M 是字符串，我们先看了字符串，然后锅开始出现了。我把题读错了，原来的题意是

单测，有 $n$ 个字符串 $s_1 \dots s_n$，对于每个 i 输出 $\sum_{j = 1}^{i}\left( f_{i, j} \oplus j\right)$

然后我跳着读 + 自动填充曲解题意读成了

多测，长度为 $n$ 的字符串 $s$ 有 n 个后缀 $s_1 \dots s_n$，对于每组测试输出 $\sum_{i = 1}^{n}\sum_{j = 1}^{i}\left( f_{i, j} \oplus j\right)$

然后我们两个人在那研究 SAM 研究了 1h +，期间 wm176 的 A 成功过了（吃了两发罚时，大模拟 WA 几发很正常）。他字符串不太行我给他翻译了一遍 D，他想了一会儿（< 20 min）直接说会了，然后接着上去写了。

这个时候我还没意识到不对，还在研究 SAM。瞄了一眼别的题，发现 N 似乎可做，上报给 MoScenix 但是因为堆积的题太多请求被拒绝。

大概在 wm176 写了一会儿之后我们猛然发现 L 读错了，其实我们那会儿已经先想到了《暴力 Trie 做法》（正解），但是认为对所有的后缀建 Trie 直接 MLE 了，最后怀疑人生了重新读题，发现读错了🤯。

然后我和 MoScenix 抢到电脑我迅速开了一个 Trie 然后 MoScenix 接力写核心代码，然后我们发现 TLE 了，经过一些常数优化仍然 TLE，然后我又一看他 cout << endl 刷新缓冲区 20000 次😡。

因为我不会计数，后来就是帮 wm176 写暴力程序和对拍程序调代码，他们两个讨论哪里出问题了。

然后，在找到错的数据之后，wm176 开始质疑我的暴力程序，但是他读错题了，题上说

You are given the integer n and the multiset $\{p_1', p_2', \dots, p_n'\}$ of the values $\{p_1, p_2, \dots, p_n\}$

多重集啊，我翻译的时候强调了这个东西没顺序，然后他们调了很久过了。

我还是感觉 N 能做，感觉像是数据结构优化的 DP，继续想 N，他们发现 G 是个双向搜索他们两个开 G。

然后就是我们换着调，他们的 G 交了三发都没过，然后我的神秘线段树最后没写完。那会儿脑子已经乱了，一个线段树维护一个区间 max 一个区间求和，一个后缀和最小值，一个后缀和最大值维护晕了，6 个题遗憾的结束了。

结束之后我们惊人的发现 G 的思路是完全对的，但是，他们读错了题，不认识 directed path，当成无向图做了。

我的 N 是错的，因为在我推到能转移的状态的时候的一些逻辑运算不等价，线段树维护这俩就必定会损失位置信息，但是要求是最靠近右侧的两条都满足的位置，我这样会找多。

第二场#

和题目内容和代码相关的在档案库

又到了 wm176 猜签到的时间，这次猜了 A，E 全部都不是，然后遍历题目发现了 J 是签到，立刻签了（12 min 的时候）。

然后发现 L 过的非常的多，去读 L，这道题一开始读错了题，以为第一行是 a，剩下的每行都是上一行但是循环左移，但是很快发现了不对劲，因为这样答案是恒定的，样例也对不上。

又看了一眼发现是第一列是 a，每一列是上一列的循环上移。我和 MoScenix 思考后发现一定会在两个收益最大的位置左右刷然后回去，那么枚举这个位置就行，然后在 31 min 的时候成功过了。

然后我读题，发现 A 似乎会，MoScenix 提醒似乎是线性基，D 是个树形 DP 也疑似可做，E 题是 wm176 的数学题我没什么读的直接就丢给他了，K 题是 wm176 读的。

他们俩讨论 K 我继续读其他的，越看 A 越对，又找 MoScenix 问线性空间的结论但是请求被拒绝了，说是先做完 K。

一个多小时的时候他们用神秘均摊暴力做完了 K。wm176 去打表 E，当时榜上 A 过的非常的少，D 比较多，然后 MoScenix 让我回来看 D，他又想复杂了，想多项式。

这次我的直觉是对的，瞪了又差不多一个小时左右发现思路完全被带偏了，每个数放在哪怎么排列根本就不重要，按照 x 小到大枚举限制算一下当前 x 管辖范围内 x 可以放的位置，然后排列组合小于 x 的数，不断的这样做就可。

然后我会了跟 MoScenix 讲，MoScenix 认可了，然后我去写代码，MoScenix 在旁边检查。但是我们的实现方案产生了亿些分歧，我大部分听他的了，但是我的理解能力好像有限，没有完全听懂，我叫他上来写他说让我写，间接导致挂了非常多的地方。

然后一点一点调调到最后对的时候就 4:30 了……期间 wm176 也是一直在努力打表，可惜最后没成功。

最后 30 min 我 request MoScenix 看 A，他终于看了，然后我想给他讲做法又被打断一次（这个时候的做法是 $O(2^m m^2)$ 的，还需要一些小优化），然后 10 min 后再次尝试沟通终于成功了，他表示认可，但是写不完了。最终 4 题结束了，惨。

后记#

我们现在上限很高下限很低，说实话有点想学姐了。去年真是身在福中不知福，有一个和我脑回路相近的，且英语很好的人真不容易。

我们似乎已经克服了牛客签到签不上的问题，但是我们还需要大量的磨合，每个人主观能动性都太强了互相不让容易起冲突，如果 MoScenix 佬状态在线，一个人直接秒了当然是没问题。但是就普遍理性而论现场赛的时候我们都紧张，状态谈不上很好，这时候如果一致出现这种冲突就会导致出题出的慢。如果我多顶回去几句，如果 MoScenix 多让我两嘴说不定都会变好，我们都需要调整。希望之后会更好吧。