ICPC 邀请赛南昌站游记：六兆年怎么没来打

· · 生活·游记

依旧一车 ddl，就简单记录一下吧。

首先是赛前一天。依旧热身赛已经开始了，我们还在高铁上。那怎么办呢，就把 The 4th Universal Cup. Stage 22: Grand Prix of Kyoto 当热身赛吧。

上来先看 N 题，是个构造。真吓哭了吧，要求黑格和白格均有 m 中不同大小的连通块，完全没有想法。直接跑路。

A 题比较简单吧，维护个前缀积做个 DP 就没了。然而由于第 0 位没处理好导致调了半天。还好样例比较强（概率题的样例一般不会弱吧）。

I 题是个神秘构造。n 为偶数的时候是显然的，全填 1 就行。为奇数时每行每列和每条对角线各一个 2 一个 3。n = 3 显然无解，手玩构造了个 n = 5 的解，然后又构造了个 n = 7 的解，感觉自己理解了一切！

这也是题啊。

总之就是交上去一发过了。

然后 K 题，给定 300 个单位电阻，构造一个等效阻值为 \sqrt{D} 的电阻器。D \le 5000。误差不超过 10^{-6}。

？

啥？有理数阻值的电阻还能构造出无理数阻值的电阻？？？

总之队友提出了一个连分数乱搞的 idea，作为数学飞舞显然我不懂怎么搞。于是我开始使用同余最短路乱搞，好消息是跑出来了！坏消息是太慢了只能打表。另一个坏消息是精度不够。全剧终。

晚上吃沙县小吃，三个人加起来开销似乎没有以前在外面吃一个人的平均开销高。赢！

十点睡觉。本来闹钟定的七点起床，结果五点四十五就醒了，睡回去然后六点又醒了，六点十五又醒来一次。每次都在梦里梦见要迟到了，醒来一看还早的很。

报道参赛物资居然给了个书包，疑似目前收到的最牛的伴手礼。

赛前讨论打不到金牌怎么办，打不到金牌解散吧。

骗你的打到了也解散（不是）。

原因是，在报名的时候，我们的原队名 ACM of Six Trillion Years and a Night 太长了填不进报名系统，所以就改用了队名 Team Name Limit Exceeded（我有一个绝妙的队名，可惜这里空太短了我写不下）。这场打完当然就不用这个名字了，这个队伍也就不复存在了！

再说说比赛情况吧。

上来一直在看 M，“构造王坝”。如何判断有解是显然的，构造一个解也是容易的，但是把步数卡进要求就很困难了。

此时队友让我去看 I，发现 I 是个裸 DP，秒了。

后面去看 K，感觉是个矩阵题，但是直接矩阵快速幂会是 O(n^3q \log k) 的，显著的无法通过。那是不是先预处理 2 的幂次，然后用一个 1 \times n 的矩阵去乘它就就变成一个 O(n^2q \log k) 状物质了呢？于是上机写了一发。写了一半突然想起指数等于 998244352 取模后得到 0^0 的没好回忆，于是又下机了。

一时半会儿想不清 K，于是去想 C。思考一会儿后发现这不是定长最短路板子改一改就没了吗，写一发居然真过了。

什么，一场两个矩阵题？

后面回头继续看 K，发现可以在开个矩阵维护每一个指数是真的 0 还是取模后得到的 0，然后就能判别了。同时完善了一下后面的实现，此时是 O(n^2q\log k \log mod)，n = q = 200，k = 10^6，mod = 998244353，5 秒应该能跑过吧……？

发现本地样例 RE 了。怎么一回事呢？

在半天调试无果之后选择了静态数组换掉 vector，这下不 RE 了，但是答案不对。怎么一回事呢？

原来我写的是 0-based，但输入是 1-based 的。笨笨猫猫。

改完过样例一交，哇跑的好久，感觉是过了的节奏吧。

TLE？？

后面一个小时一直在卡常。本地压力测试跑出来大多在 4.6 秒左右，然而交上去一直挂。最后遗憾离场了。

等讲题。如果讲到 K 发现正解是单 \log 的就释然了，如果是双 \log 就永久拉黑。

什么叫讲到 H 就不讲了开始滚榜了？？

在一番漫长的等待（指隔壁晚半小时开赛的武汉滚完榜）之后也是终于滚到了榜单最上方。好在大家都做不出 K，我们前期手速比较快，也是拿到了季军杯。本质手速队。

赶到机场时已经有点饿了，但是看到机场高昂的物价想了想算了。于是又拿出西安邀请赛发的糖。不得不说带上它真是个正确的决定啊，从高铁上吃到机场，要不是有它我指不定就在路上饿趴下了。好吃爱吃。

第二天终于看到了题解。K 题最后的卡常思路是对的，不用二进制，用更高的进制拆分。可惜最后就写了个五进制没写二十进制。但标程这样写也跑了整整 3 秒 75 怎么敢开 5 秒时限的。不懂。