APIO 2025

wzj33300 · 2025-05-19 10:32:41 · 生活·游记

noip 这么低都过了，真唐。

5.14

不知道谁订了一班提前一天早上八点起飞的飞机，让我五点半起床。中午到了酒店后发现没地方好玩，打了一下午 bedwars。

发现有六块钱两瓶的可乐，早知道多买一点。

5.15

晚睡晚起，起来就去颓废了。

下午三点去报道，发现学校非常大。下雨了几个人还被拉着去拍了张合照。

去到宿舍发现宿舍有电，比较牛。但是四个人住的宿舍只给了两张椅子，很难评价。

试机的时候感觉键盘比较好用，机子速度没咋看，感觉比洛谷稍微快一点？

5.16

昨天躺在床上刷手机，忘记时间了三点半才睡。早上差点没吃到早饭。四节课上午下午第一节都不错，听到第二节就困了。

开幕式本来想翘掉的，后面发现有合照就还是去了。

5.17

比赛日。比赛开始了，我先看了看三道题，发现第一道题 subtask 最少，然后就开始做 A。

刚开始想的是用某个数的倍数，然后相当于睡了半个小时，发现这样做根本无法让输出非 0，毛用没有。想到生日悖论，然后误以为期望 N=2\sqrt n 才能找到（事实上，只需要 \sqrt {2n\ln 2} 个数就可以），想了分治等方法后发现我无法找到 O(N^2) 对两数差到底哪一对是 n 的倍数（会产生贡献），然后就一直在想这个改进。

中间看了一下 B,C，B 的题目中有一个很恐怖的四重寻址，感觉不是很可做，C 这个旋转的限制，看起来比较松。

回到 A，我想到了类似 BSGS 的询问方式，但是这个似乎只能判断 n\in[1,r]。这时候二分，询问次数是 O(\sqrt n\log n) 的，肯定不行。

然后发现把这个询问方式改一下，我就可以判断 n\in [l,r]，只用 2\lfloor\sqrt{r-l+1}\rfloor+1 代价，虽然这个做法在 n\in [1,\lfloor\sqrt{r-l+1}\rfloor] 的区域内好像会出现问题，但问题应该不大（哈哈实际上是我没想清楚），现在询问次数为 T(n)=T(\lceil {n\over 2}\rceil)+2\lfloor\sqrt{{n\over 2}}\rfloor+1,T(1)=0 即 T(n)=O(\sqrt n) 的。我直接写了，拿了 78。

这时候次数是 \approx 1.5\times 10^5 的，我意识到只要省掉二分的第一步，就可以通过了。注意到，只要找到 n 的一个倍数，就可以通过试除，在很少的步数内找到 n。易得 n 在 (5\times10^8,10^9] 内必定有其倍数，所以我们真的省掉了二分的第一步！我在两个小时多一点的时候通过了这个题。

看到 C，我手玩了一下样例，发现把线两两配对成十字架是最优的，而且配对成十字架之后，这两条边可以直接扔掉，对后面的边不造成影响。我很快得到了 16 分。

注意到 16 分我们每一次都是选一条极角最小的边，然后再选极角最大的边与它配对，这里实际上是选择了与 x+90^{\circ} 最近的边，推广这个事实，我们发现我们一定可以在与 x+90^{\circ} 左右最近的两条边中选一条满足题目条件，具体来说，就是选择的边两侧一定是一边全正贡献，另一边最差全负贡献。这两条边，两侧几乎互补，画图看一下就可以发现一定有一条边正贡献的边数量不小于负贡献的边数量。有了这个事实，就可以简单树状数组统计左右两侧边的数量然后判断。这件事是可以证明的，于是我先写了 O(n^2) 的做法，这其中出现了一些问题导致我调试了较久（啥问题忘了），然后又花了半个小时（中间在树状数组询问边界上调了好久）通过了这道题。

这时候，距离比赛结束只剩下 30 分钟左右了，我打了 B 的 12 分，但是我没能观察出这里树的部分分实际上就只有链是可以操作的，三元环我有一些思考，但是发现好像要分讨很多情况，于是也放弃了，最后检查了一下。