ICPC 2024 Kunming

比赛之外的部分之后更。

因为要赶传奇 lab2 所以昨晚零点之后才睡，起来的时候觉得很困。吃早饭的时候遇到了 aw，和他打了招呼。

到了场馆之后才发现开始时间是 9:30 而不是 9:00，于是加睡。

开场我上机先把头文件写了，X 和 N 找签到题。我写完之后，N 说他觉得 C 题简单。我看了一眼，觉得求出轮数然后把过程倒过来就可以求出答案。但是我被首杀冲昏了头脑，竟然认为直接模拟的时间复杂度是对的。于是我写了一发，交上去之后发现 wa 了。

此时发现有队伍过了 M 和 J，于是两个队友分别去想这两道题。X 说他会 M 了，于是我把机位让给他。N 跟我讲了 J 的题意，并说他有一个想法，想让我检查一下。我听了之后觉得很对啊！X 的 M wa 了，于是我就上机写 J。代码很短，只需要求逆序对个数，但是交上去又 wa 了。

X 说他意识到 M 的错误了，于是再次换他上机。我和 N 继续讨论 J，发现有个 case 没判，于是把键盘抢过来改了一下，但是又 wa 了。为了以防万一我把题面拿出来自己读了一遍，发现居然读错题了！我们原本以为 Alice 只能交换相邻的位置，但是实际上可以交换任意两个不同的位置。好在思路大差不差，我们改了一个做法出来。X 的 M 又 wa 了，于是换我写 J。写完之后点击提交，心想总该过了吧，可是屏幕上的灰字又一次变成红色。

随之变红的是我。我注意到我在关闭流同步的同时混用了 printf 和 cout，于是把前者改掉了，再次提交。为什么依然是 wa 呢？我非常不解。X 声称他对于一种情况需要打表求出答案，于是又一次让他上机。我和 N 细致地检查了每个 case，终于发现还要特判 n=3 的情况。正好 M 的表打完了，X 也观察出规律来了，在一发 re 之后，我们终于在第 46 分钟开张了。我上机改完代码后，也终于过了 J。

但是此时的罚时已经寄完了，我们只能靠题数获胜。我返回看 C，注意到之前那发提交竟然是 tle 而不是 wa。我立马意识到了问题，把直接模拟改成整除分块，果然过了。

现在终于算是松了一口气。但是出现了一个非常严重的问题——刺眼的阳光透过场馆的窗户，直接照射到了我们队（以及左右两支队伍）的桌面和电脑屏幕上。放眼望去，整个场馆只有我们这块地方是亮的。尝试询问志愿者，但是心里其实比较清楚解决这个问题的可能性十分渺茫——因为窗户太高了。志愿者给了我们一把伞，但是显然无济于事，我们只能等待太阳继续升高。

剩下的题目中过得最多的是 H，之后是 L 和 G。在我写 C 的过程中 X 和 N 貌似已经把 H 编出来了，于是 X 马上接着上机。我和 N 继续分头想 L 和 G。L 我有一些想法，但是和 N 讨论之后被他毙掉了。在 N 给出的反例的引导下，我又编出来一个看起来很对的做法，和 N 讲了一会儿之后他也理解了并觉得是正确的。X 的 H 在神秘 wa 了一发之后过掉了，于是换我上机写 L，X 和 N 想 G。实际上 L 的代码远比我想像得简单，十几行写完了。第一发提交 wa 了，修了一个小 bug 之后过了。

G 的进展并不顺利。X 过 H 到我上机之前我让 X 打了个表，但是并没有什么发现；听了 X 和 N 目前的做法之后也觉得一头雾水，于是我决定去上个厕所。路上我想到热身赛的 C 题，意识到答案肯定不大于 2 \left\lceil \log \max(a, b) \right\rceil。回到座位上，把这一点告诉了 X 和 N。X 突然意识到这个上界可以被缩小为 2 \left\lceil \log a \right\rceil + 1，于是直接搜索即可！顿时三人都感到有些难蚌，X 上机并迅速把这题过了。

X 在写 G 时我和 N 继续看 EF。由于 E 过的人多一些，并且其是交互，我决定先想 E。看完题之后我觉得很迷惑——这不是直接枚举所有合法路径，加入线性基，再解方程就结束了？时间复杂度是 \mathcal O(n^4/\omega)。我跟 N 说了做法，他也觉得很对。于是我立马上机开写。代码不短但是也不难写，在因为忘记输出 YES wa 了一发之后，我们顺利通过。

下机之后无题可写了。X 说 F 题的答案就是 2 到 n 所有数质因子个数的乘积。我们讨论了一会儿分段打表的可行性，但是之后发现居然给定模数。我转而想到一个 dp 做法：令 f_{i, j, k} 表示考虑到前 i 个质数并且选择了第 i 个质数，当前有 j 个不同的质数，n 除以选择的质数的乘积为 k 的方案数。并且，对于最大质因子的幂次为 1 的数，我们统一在去掉该最大质因子处计算答案。这样只需要用 min25 预处理出 n/x 以内的质数个数即可快速统计，并且可行的状态要求 p_i \le k，转移要求 p_{i'}^2 \le k，这也和 min25 十分相似，复杂度是 \mathcal{O}(n^{1-\epsilon})。看上去对麻了，于是我直接开写。因为带了 min25 板子所以很快就写完了，也没怎么调就过了大样例，可惜要跑 3 秒。把 unordered_map 改成 gp_hash_table 之后只要 1.8 秒了，于是果断提交，但是 tle 了。未必评测机开了 -O2 之后比本机跑得还要慢啊？我只得继续卡常。首先我发现 dp 值都很小，于是把 i64 改成了 int，但是收效甚微。之后我注意到，如果确定某个转移到对状态不可能继续转移的话，就不必将其加入哈希表了。改了这个之后立马跑到 0.6 秒，交上去果然过了。

终于暂时进前十了，但是只剩一个小时多一点点的时间了。此时需要决定是集中力量做 B 还是 D。我们最后还是因为过题队伍数量选择了 B。我和 X 意识到一个区间只要不是一段右括号 + 一段左括号就一定寄了。那么这题就就简单了啊！直接线段树 + 哈希即可。但是代码十分难写。我在还有 40min 的时候开始写，到最后 5min 才刚刚写完。我们决定编译通过之后直接提交，结果是不出所料的没有通过。

听讲题，感觉 D 并不困难啊！要是想 D 说不定就赢了。打星队里貌似谁都没打赢：哥哥自不必说，洛谷队和小粉兔队也都在我们之上，还有一个不知道什么成分的队伍。不过有一说一，封榜过三题确实厉害。感觉这场就是实力差距啊，要是开场没有那么唐或者封榜后过一个题，都能获得高得多的排名。