APIO2026游但是没有特别寄

· · 生活·游记

Day -1

来北京了，领了一大堆东西，然后在酒店开摆。

Day 0

讲课。

zsh 讲的图论，第四个听懂不完全，第二个完全听不懂，剩下两个感觉是典题和水题。

xqw 讲的用代数方法做格路计数，只能听懂引入了，我是代数低手。

ljw 讲的莫队，前面还行，后面还是听不懂。

hyx 讲的博弈，终于能懂得差不多了。

大部分时间在睡觉，感觉比赛要废，但是食堂的饭还是挺好吃的，就是队排得特别长。

下午去试机，题是 NOIP2025（你们 APIO 没有自己的题吗？），然后发现忘了怎么做 candy 了，花了若干分钟想起咋做，然后写了，sale 懒得做了，发现有 Selfeval，太好了，妈妈再也不用担心我挂分了！

后面就去开幕式了，dzd 竟然没来，说是去新加坡追星去了。节目都非常不错，尤其是那个街舞确实很有新意，情景朗诵节目也不尬。

晚上依旧开摆，十点多就睡了，感觉心态比较正常，希望好好发挥。

Day 1

提前到考场门口，站了一个多小时，中间开始随机复习数论内容（为啥现在才想起来），发现很多都记得不太清，只能死记硬背。

考场外面有地方能免费领吃的和笔，领了一根棒棒糖，希望自己不要太糖。进了考场，发现座次条上面没密码，登录账号又需要密码，一开始以为是要开始的时候统一公示之类的，结果是密码条还没发。

于是志愿者把密码条发了下来，比赛在延迟了十分钟后正式开始。

先把所有题看一遍，感觉 T3 > T1，T2 有些神秘，开始尝试拼分。对于 T1 的 A 性质，想了一个状态 f_{i} 表示确定了前 i 个位置的情况，每次转移到 f_{i+j}，系数是从 i+j 中选出 i 个然后乘上区间的积，感觉很有道理，配合状压能砍掉 35pts，然而更多的分没啥思路。

然后去看 T2，神秘交互题，一共四个 sub，第一个读懂题就能随便做，第二个很明显是要一次询问区分出 3 种情况，也就是说对于询问的三种结果要分别对应一种情况，随便画了画发现取 \{ 0,3\} 和 \{ 1,2 \} 就行。再考虑 sub3，很明显是需要 log 级别，于是开始构思类似于二分的算法。然而构思不出来，但这个想法提醒了我，可以尝试构造 2^k 组成的序列，就可以把答案限制在两位之间。但是如何检测答案在哪呢？发现 1+\sum_{0\le k < i} 2^k=2^i，于是可以在序列前面插一个 1，这样正常情况下，序列中一个位置就等于前面所有数加起来，假设答案的位置为 ans，考虑 >ans 的位置 id，发现这时 id 前面的数加起来必定大于 id 位置的值，于是可以扫一遍，其实也类似于二分。如何确定答案呢？发现原来序列中的每个数就对应值一个二进制位，类似于倍增地再扫一遍就行，当然这样是 2log 的，但只需要把确定位置的过程倒过来扫，这样序列中每个位置只会被扫一遍，实现精细就可以做到 K=29。

最后看 T3，不会，感觉 nqlog 能做，A 性质想了一个巨复杂的倍增做法，大概是维护从某颗宝石的区间的 左/右 端点开始进行移动的倍增数组，感觉很难写。

这时突感便意，于是去上厕所，运气好随机到坐便，于是在马桶上思考 T1 和 T2，这时大概感觉到签到题在 T1 和 T2 之间，T1 想了半天没啥进展，就开始想 T2，发现 \log_{3}N 大概等于 7，而一次询问最多有三种不同的结果，所以正解一定需要三分，如何三分呢？上完厕所，回到座位上，现在的问题在于如何利用 = 的条件，因为如果只在乎 < 和 > 两种返回结果应该是可以瞎搞的。怎么办呢？此时再次观察到 N>W，于是想到构造一个从 1 到 W 的等差数列，而等差数列中容易想到的数量关系就两个：按照位置奇偶性，画一画就发现没有搞头；另外一个性质是 a_{i}+a_{j}=a_{i+k}+a_{j-k}（这个式子瞎写的，可能不严谨），于是想到按照当前序列中点对称取一些点，这时就成功想到了正解的构造方式，就是把两边分别最靠边的 X 个点放到一个集合里，再把两边的 X+1 到第 2X 个位置放到另一个里面，可以证明 <，> 和 = 分别对应了答案在左边 2X 个位置，右边 2X 个位置以及中间的其他位置。然而我考场上很糖，只大概想到一个很劣的实现，这导致如果返回结果为 =，中间递归到的区间并不是严格三分的，因为我的实现要保证重复的两个数都在当前区间内，具体来说，手玩一下可以发现在 len=7 时会出现一个极劣的情况：可能递归到 len=5 的区间。当然，具体确认需要写个程序验证，程序告诉我最劣情况下 K=8，但如果成功把 len=7 的情况简化，就可以做到 K=7，然而我想了很久没有进展，这时已经过去了两个小时，就开始先写这 89pts。

经历了一些很糖的问题，代码总算跑到了 89pts，这时时间只剩两个小时多了。感觉这个 T2 也是紫题难度，就果断放弃去做 T1，打出了 35pts 的代码，但是只有 20pts，一看发现 A 性质的式子假了，就重新去做 A 性质，然而竟然做不出来，急了。去搞 T3，但发现 28pts 以上也一点不会了，20+89+28=137pts。难道，我就止步于此了吗，难道，我注定无法场切出紫题吗？

不！还没有结束！此时我感觉想拿更高的分，最好的方法就是继续 all \ in \ T2！我把 len=7 时的六种方案画了出来，开始尝试选一些位置，使得能在两次询问内区分出这些情况，但是找了很多种看起来很对的做法，都只能做到三次询问，这时已经特别慌了，因为比赛还有一个小时多一点，如果再做不出来就只能去写 T3 暴力了。

就在我即将放弃之时，我重新瞟了一眼我画的六种情况，突然发现，最中间那一列，也就是 len=7 时的第四个位置，恰好有三种情况 =3，有三种情况 =4！于是，只需要判断中间那个数的数值，就可以确认重复的位置在前 4 个位置还是后 4 个位置！而区分连续的 4 个位置，sub2 已经做过了，而想要判断一个位置的值，只需要用到 \operatorname{O}(1) 个位置，按照区间左端点的大小分别用最左边的位置和最右边的位置去判断就行。我赶紧去改 T2，终于在只剩 45min 时通过了 pretest，我终于拿下了一道紫题！

我来不及激动，赶紧去写 T3，突然发现对于测试点 8\sim 10，因为 n 的范围并不大，可以不需要维护倍增数组，直接暴力维护每层父亲，而 lca 可以通过类似树上背包的做法维护，于是所有的查询都变成了 \operatorname{O}(1)，我获得了 \operatorname{O}(nq) 的做法。

写完 T3 后，还剩 20min，又赶紧去推 T1，然而不知为何，无论如何都想不到 A 性质的正解了，最后比赛结束，好在并没有留下特别大的遗憾。

考试结束后，看见右边的大神场切了 T1，出考场时听到别人讨论这场人均 200+，顿感 Ag 不稳，不过考完了也就不想了。

怎么好多认识的人都烤炸了，并且都没切出 T2，这个 T2 确实太灵机一动了。

为啥食堂的番茄鸡蛋这么甜啊，之前不理解为啥要争番茄鸡蛋是甜是咸，现在知道了。

吃完饭随便走了走，才想起来要去嘉年华，去的时候已经排满队了，感觉我的身体协调能力很抽象，就排了一个投壶的队，也只来得及排这一个了。

去看分，没挂，20+100+40=160pts。走出去以后发现群里有人把牌子拿走了，于是又返回去一趟，把牌子带走了。

讲题，T1 的 35pts 怎么这么简单，我怎么这么糖，T1 的 65pts 怎么也不难，我怎么这么糖。呵呵，我之前一直以为我很会组合计数的，并且一直不认同 OI 中出现 Adhoc 等非传统题，然而讽刺的时这场我分数还行全靠 T2，T1 发挥得依托。讲题都听懂了，有人说有两位数的人 ak，感觉真不是不可能。

晚上开摆。发现我好像成为了 SX 分最高的，SX 今年怎么这么寄。

Day 2

听课。听了一些 Adhoc 题，愈发觉得自己也许真的更会做非传统题。感觉那个投资的课挺有意思的，虽然感觉并不算特别深入。然后整整一个小时在讲区间最值操作的复杂度证明，睡了半个小时。

中午去吃食堂三楼，烤鸭饭真好吃。去嘉宾休息室买了一杯葡萄果茶，挺好喝的，但感觉有点小贵。

去社会实践，逛了中关村和北大。在中关村确实看到了很多之前想象不到的前沿科技，北大的风景也确实非常好。

晚饭还是去吃了食堂三楼同一家店，脆皮五花肉饭真好吃。就是吃到最后有点腻。

吃完饭，距离闭幕式一个半小时，开始在学校里随便找位置打坐。后来去找了 byr 一起打坐，安慰他，不过貌似没啥用，最后我说啥他都只回答“批”了。

闭幕式的座位我竟然正好排到了最中间那一列，还是后排座位的第一排，属实是 c 位了，感觉是个录制节目的好位置。

去闭幕式。实际上，因为我那个位置前面是一个比较宽的过道以及正好在中间，全程被摄影师挡的很严。上午就有群友透露 dzd 回来了，还真回来了，甚至还有演讲。感觉只要主持人提到 dzd，全场的掌声比提到任何其他人时加起来还要大。全程录音了，因为画面实在拍不到。下面是最新 dzd 语录：

dzd：“我回来了”

dzd：“黄埔军校”

dzd：“whdgm”

dzd：“克罗地亚总统”

dzd：“距离 APIO2000 过了 37 年”

dzd：“我是 IOI 主席”

dzd：“我还不会凉”

（只是复述 dzd 的言论，请过审）

以及 160pts 竟然贴线 Ag 了。

然后一切就结束了，晚上请 SX 其他人喝蜜雪冰城。

这次活动真的非常有意义，对我而言是一段很感动且值得纪念的旅程，之前我一直调侃自己永远无法场切洛谷评级为紫的题，这次我终于做到了，而且作为一个在基本没人打 OI 的小城市里长大的孩子，很少能见到这么盛大的活动。感觉各方都很努力让这个活动顺利举办，除了某个协会（听说官方数据解包出来 T2 的 sub3 出现了 d_i > W）。

Day 3

六点就起来了，去赶高铁，然后发现竟然和 dzd 同一趟车（昨天闭幕式 dzd 说要去 SX 视察），在候车室看见 dzd 并拍了 dzd 的帅照。

Day ?

四天（也许是三天）一转眼就过去了，现在在回程的路上写游记，还有两个月就 NOI 了，个人的提升空间还非常大。社会实践拍了很多照片但是懒得放了，有时间再补吧。