AFO 记

· · 生活·游记

写在前面：感谢 noip 出题人黄紫黑黑给老子送退役了。

Day -INF

摆烂，打云斗集训。

中途参加了个济南 CCPC，被 K 区分掉了，铁。

中途参加了个 YCPC，赛时 rk3，赛后毙掉了 rk1 和 rk2，成为 rk1，得到高达 27 元的奖金加上一个小 U 盘。

然后吃三次盒饭 60 块钱给我的奖金送走了。

Day -1

打了一天板子，终于写完了。

在群里聊天，突然发现我不会 Manacher，慌慌，寄希望于 noip 不考串串。

睡觉。

Day 0

中午吃火锅，好吃。

下午开车到达淄博。

晚饭吃的超意兴，好吃。

直奔考场试机，挺快的，打了个 1e8 的和加上取模，只跑了 1.4s。

但是这个虚拟机是何意味啊，打开之后对其使用 g++ test.cpp -o a，然后 ./a，无事发生？

重启了一遍，就好了？

发现虚拟机和本机剪贴板互通，豪。但是怎么必须重启才能运行啊。

出来，发现似乎我的机子还算好的，有人的机子编译之后需要过 n 秒才能输入，何意味。

Day 1

早上特意少吃了点，害怕考场拉肚子。

到达世界最高城，在群里发了 noip 2025 rp++，转身进入考场。此时我还不知道我将会遇到什么地狱。

开题！

使用优先队列开题法，先瞪了一遍 T1、T2，都没有一眼，不慌，edit 都吃过了，还怕这个？

感觉判断不了前两题的难度顺序，所以决定顺序开题。T1 感觉是个背包问题，但是容量怎么是 1e18，这下贪心了。想了想，觉得直接贪心的选当前最小的比较对，然后把每个糖果选到了奇数次还是偶数次赋权成 01，然后把状态状压，hash 成一个数，找到循环节就做完了。打了打，发现不对，其一是怎么实现这么狗屎，其二是想了个小样例把我自己 hack 了，这下这下了。

不过无伤大雅，又想了想，发现实际上循环节一定是 x+y 最小的那个糖果，然后买的顺序无关，于是直接贪心前 4n 次，然后枚举每一次剩下多少钱，全部买 x+y，取个 \max，就做完了。打完就过了大样例，此时 30min。

很稳啊，30min 切 T1，把 T2 切了再去拼拼暴力是不是就队线了，开始看 T2。数数，很好啊，瞪题。20min，觉得为什么这题放 T2？怎么这么简单，开打。欸这对吗？搂了一眼样例解释。不是？怎么你们家最优策略还不一样啊？？？

读错题了，怎么是按你每一次价格判断策略啊，这做个毛线？想了八辈子，根本想不到怎么做，去看部分分，才发现我又把数据范围读错了，怎么是 5000 啊，怎么是 n^2 啊。

状态状态状态，不是？怎么设状态？想了想，首先肯定是把 a 降序排序，然后 12 赋权，1 选一个前缀，2 选一个前缀，策略不优当且仅当你可以用两个 1 替换成一个更优的 2，那我能不能记录下这个 2 的位置，设其为 f_i，转移转移转移，不是这 B 玩意限制怎么这么多？？？这转移个毛线！！！

2h 过了，失败了，策略逐渐从冲 T2 正解到冲 T2 高分，从冲 T2 高分到怎么做 T2 部分分。发现只会很狗屎的 O(n2^n) 做法，打吧。打了半天，过了小样例，没过大样例，调调调。怎么是这么狗屎的 corner case，改了，过了，20pts，润。

看 T3，这位更是一眼不可做啊，想了半天，觉得可能可以做到 O(n2^n)，但是好像又不会，润。

看 T4，怎么又看错题了。以为直接扫描线就做完了，瞪眼数据范围？？？？？？怎么正解 O(nq) 啊，正常这种复杂度的东西不应该是暴力吗？？？

不会啊，怎么只会 qn^3，只能过第一个包，完蛋了呀。

又仔细想了想，发现 O(qn^2\cdot(r-l)) 中间的一个 n 可以直接用滑动窗口干掉，这样就是 O(qn(r-l)) 的了，写写写。

3h 或者 3.5h，过了这部分分，回去瞪 T2。从头开始想，但是只要想到设状态，就完全离不开那个最后一个 2 的讨论，这怎么办？

去 T3，把 O(n^n) 的暴力 dfs 打了，然后想了想感觉可以剪枝，剪了一下，还是只能过第一个包，摆烂了，失败了，寄了。

去 T2，不会。去 T4，看了看，发现打的东西能直接把性质 A 过了，很牛啊。性质 B 是 32，那不是预处理然后 st 表？打了，调了调，怎么还能把 lg[i]=lg[i>>1]+1 写成 lg[i]=lg[i>>1]=1 的，改了就过了。

然后就没时间了，T3 T4 真的燃尽了，不会更多的分了，剩下的时间全部瞪着 T2 的题面，发呆，质问我自己。

出考场，遇见的人没有会 T2 的。怎么 WSR 切了？

去吃烧烤，后坐遇到 cyf，都爆炸了。

此时洛谷题目难度评级出了，我放声大笑，哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈！

怎么是黄黑黑黑！

晚上去逛了海岱楼，吃了碗很宽的宽面。

看了疯狂动物城 2，挺好看的。