【线上游记】2024 ICPC Asia Taichung Regional Contest

这次和 @Iceturky 和 @Garry_HJR 组队，我们的 CF 名字分别是 Iceturky,deng_wo_ni_xi,vector.never_fst。

队伍名称采取了 Iceturky 的 "活人不能被车将死"。

策略是跟着排行榜做题，每个人选一道。

根据我平时对他们的印象，Iceturky 擅长高思维难度的题，2400+ 的题不能没有他；deng_wo_ni_xi 写题的罚时很少，调试快；我比较喜欢 dp，数据结构之类的，但是遇到 Ad-hoc 之类的就寄。

比赛开始后，deng_wo_ni_xi 先正序开题，我中间开题，Iceturky 倒序开题。

deng_wo_ni_xi 在 2min 时秒了 A，恐怖。

我选了一道看起来比较友好的，D 题。

D 题一眼就是 bfs，我写了写，结果挂样例。
在我调试的过程中，deng_wo_ni_xi 和 Iceturky 分别切了 B,E，震撼。

反复的 D 题 wa 样例让我很紧张，求助了 deng_wo_ni_xi。

过了一会我突然意识到状态转移漏了一个加号，改对之后 AC 了。

这个时候 Iceturky 在写 M 题，我和 deng_wo_ni_xi 一起想 C。

我一开始看错了题，以为只需要选择 3 个，然后构造了一个解决方案。

然后在 deng_wo_ni_xi 的提醒下，我才意识到。

这时候 deng_wo_ni_xi 提出了一个方案，好像是跟 1 的个数有关，但由于我刚搞清楚真正的题意，并没有听懂在说什么。

突然 deng_wo_ni_xi 把这个方案否定了，我就去自己想了。

想了会，构造了一个看起来很有道理的状压 dp，展示给了 deng_wo_ni_xi，结果这个做法就是刚刚 deng_wo_ni_xi 的。

不过这时候我发现 deng_wo_ni_xi 否定这个方案的时候实际上是算错了总复杂度。

不过我自己也分析不出来严格的复杂度，就写了一发，过了。

此时 Iceturky 的 M 题 wa 了，deng_wo_ni_xi 去协助他调试 M 题。

我想了一会 H 题，可是并没有想出来。

在此期间，deng_wo_ni_xi 发现 Iceturky M 题多写了个负号，改对之后 AC 了。

看了眼通过率略低的 I 题，发现是我喜欢的数据结构。

然而我被怎么维护字典序排名卡住了。

一度想着用 vector.insert 插入。

Iceturky 提醒了我，可以离线询问预处理，成功解决了这个问题。

在此期间

我写写写，在 3h 的时候过了 I 样例，然而交上去 MLE。

Iceturky 指出我代码的问题在于 trie 空间占用过多，改成了 map 存储下一个节点就可以了。

然而又 wa 了。

和 Iceturky 讨论了一下发现，我查询的时候有可能查询到不包含当前前缀的字符串，一个解决方法是 trie 每个节点上挂一个三元组。

我和 Iceturky 各自进行修改，并同时重新通过了样例。

Iceturky 交了一发，被卡了哈希，发现是 base 太小了，改了一发就过了。

后面，尝试了 F,H，无论如何也做不出来，定格在 7 题。