APIO 2024 游记

· · 生活·游记

5.16

早上坐地铁到北京南站，然后坐高铁下午到杭州，酒店房间号是平方数（

5.17

上午还可以，下午根本听不 dǒòng。

莫名其妙地成为了网管（我的 iPad 不需要认证可以直接连上网，然后扫了别人之后别人就能连上了），非常乐。

晚上做去年 T1 最短路（flag）一直 RE 44。

5.18

注：以下时间均为开考后多长时间。

倒叙：喝了 5.5 瓶水，上了 4 次厕所。

试机写了一些东西，结果一个没用上。

开场先开 T1，稍加思考之后发现越短越好，然后直接 O(1) 维护节点个数，每个点有几个子节点没选，有几个这个值大于 0 的节点即可，时间复杂度 O(nm)，不到 30min 过了。

看了一下 T2，第一眼湖北省选模拟 D1T1，第二眼不一样，而且更难，第三眼这不是不可做题？开 T3，思考了半天不会 Sub1，后来写了个巨复杂的 n=4097 二进制做法，此时 80min 拿到 5 分，赛后发现我是小丑。

继续思考部分分，一直在想用重复点得到信息，想了 20min 没有结果。

开 T2，心急如焚地我发现完全可以最短路（flag），相当于只需求区间内部有多少个吃饭区间，然后写着写着发现复杂度是错的，而且还要写二维数点，因为有可能一个点入度出度都很大。

进而写区间不交部分分，不用写二维数点，试了一下果然 TLE 被卡。试图乱搞卡过去，但也只卡过去了 Sub2，Sub3 死活过不了。（180min）

忽然想起限制 25 次提交，而我已经提交 19 次了，这个时候开始写正确的部分分。写完之后交了两发 WA，然后发现做法有一个很隐蔽的细节问题，但极其难处理。经过很长时间的调整终于拿到 35 分，不会写 Sub1。（260min）

继续思考 T3，想了半个小时之后忽然发现可以 60 个一组如果二进制这一位是 0 和 n-1 连边，否则跟 n 连边，交了两发果然被卡了。后来发现可以写一个 Hash 函数，让得到的结果跟输入的值有关却又尽可能随机（类似树哈希），这样交互库也不知道树代表着什么。注意到 Hash 值需要对 60 取模，然后我的异或之间少加了一个括号，导致运算优先级出了问题。但当时我只测了编译，由于图巨大所以不方便测样例。并且当时评测机卡，导致代码结束后才测出来，然后我才发现我写挂了得了 0 分。

赛后同学指出这个做法是可以卡的，但我认为这题出题人一定不会想到我这种做法，所以可能没有卡，等过几天哪个 OJ 有了我试试。（upd：稍微改改就卡不了了）总之这个 T3 出得还是很不好的，毕竟出题人没发现的假做法就是正确做法……

最后就是 100+35+5=140，T2 用时 180min，大概是铜牌线上下。

5.19

颁奖，Cu * 1。