AP(CN)IO 干饭记

· · 生活·游记

打得最开心的一届 APIO。

本文记录了活动过程中的每一顿饭。

Day -1

报道日。

从广州前往北京。逃离了蒸笼。

下午在床上蠕动，晚上同校的同学聚餐(小火锅)。点了一杯奶茶喝。

Day 0

讲课日。

早饭是牛肉肠+面包(计士,黄油)+花卷+青菜+热牛奶。好吃。

赵大哥的课掉线了，凯文大哥的课勉强听懂了。

午饭是意式肉酱面。还可以，但是番茄酱感觉调的有些奇怪（？

没有午睡时间。差评。中午在校园随机游走。

下午讲莫队的时候严肃开睡。

博弈论讲得很有意思，讲了 medrcy，好评，但是怎么没讲一般图最小点覆盖的神秘爆搜方法（

晚饭是石锅拌饭(茄子肉末,锅包肉)。评价是属于食物。我不认为锅包肉应该出现在这碗饭里，选菜失误了。

没有看到教练的通知导致本校所有同学没吃饭并等待我吃完饭后合照。这里给所有本校同学磕一个。对不起！！！

试机。神秘键盘，差评。

开幕式很好看，虽然杜子德没来，但是另一位杜老师的讲话也很有意思。

外卖点了一些零食。但是我拿外卖的时候我的饮料已经被开封并喝了一半。何意味？

晚上早早睡了。明天要早起。

Day 1

比赛日。

为什么 9:00 开赛要 6:20 起床啊（恼

（虽然是我早上动作太慢了以至于需要比发车早 60min 起床才能赶上车 w）

早饭是鸡肉肠+青菜+面包*2(蜂蜜,黄油,计士)+热牛奶+小蛋糕。依旧好吃，但似乎拿多了。不该拿两片面包的。

见到了张超老师，此后在楼梯上睡觉等待进场。然而根本睡不着。

似乎由于密码条没发完延迟了 10min 开赛 w。

配置电脑花费 10min。阅读三个题。

T1 和 T3 没绑包，而且一个大 DP 一个大 DS。鉴定为 APCNIO。

首先跳过交互。做了一会 T3，不会做。先去看看 T1。

往去年 CSP T4 靠一靠，编了一会编出了正确的 O(n^3) 状态。写一写拿到复杂度 O(n^4) 40 分。

上前缀和，到 O(n^3)。拿到 50 分。为啥还是 TLE？？？

卡了会常，扔掉了一些不可能转移到终点的状态，似乎卡了个 1/3 的常数下去，100 分了。此时 75min。

决定尝试一下这个交互。观察了一下数据范围，发现 Sub 2/3/4 互相没有包含关系？！

前面的 Sub 的分数都不高，猜测难度不高。遂决定先做 Sub 1/2/3。

Sub 2 所有人类都会。Sub 3 看到 \log_2n 左右的 N,K，猜了个 \{1,2,4,8,\cdots,2^{28},2^{29}\}，推了一会发现能做。

遂开写，获得 45 分。

过了一会突然发现这个东西好像能在 Sub 4 获得 11 分。删掉判子任务再交了一发，获得 56 分（w

开 Sub 4。首先猜 \{1,2,3,4,\cdots,1999,2000\}，发现这样可以获得一些值为 c+[x>c]（c 为常数，x 为未知的蛋糕美味值）的变量。又发现可以通过添加重复元素以获得常数。凑一凑就可以弄出来回答是 [x>a]+[x>b]-1 的询问，然后就可以三分了。

获得 100 分。此时 150min。2.5h 大战 T3，优势在我！

没有读题导致以为可以离线。思考离线做法。

这个东西长得非常像一个在操作序列上扫描线，离线并用你喜欢的数据结构维护询问，询问在 l 时刻加入在 r 时刻弹出并统计答案的题。而且走到相同点上的询问可以拿个并查集并成一个询问，这部分复杂度可以均摊一下，就只需要考虑不产生合并的操作如何批量维护。看起来就很有道理（不是

然后发现这个操作过于复杂，不大可能逐操作维护。开始思考如果已知 i+1 号操作将要被执行，i 操作能否被替换为一个更简单的形式。这里赛场我真的编了点东西出来，但由于是错的就不在这里写了（

还剩 120min，准备开始写了。看了一眼交互格式发现不！对！劲！

终于发现询问是在线的了。呜呜。只能重做了。

又思考了一会，发现上面那个东西是错的。彻底倒闭。决定如果再做 30min 还做不出来就写暴力去了。

前面的做法在两个邻域相交的时候假了，所以重新思考这个部分。

研究了一会，发现连续走到两个相交的邻域等价于直接走到两个邻域的交？！

于是操作可合并？！

严肃开写。

开摆，懒得写 O(n\log n)-O(1) 的 k 级祖先，也懒得写猫树。复杂度 O((n+q)\log^2 n)，相信树剖常数。

树上 k 级祖先调了一万年（> 打成 < 了 qwq），好不容易调出来了但是本地跑了 4.5s。害怕。先交一发。

过了？？？

280min 极限拿下。

上个厕所，拿了点考场外的零食。发现有好丽友派和棒棒糖。好吃。

意识到刚才跑 4.5s 是因为 -fsanitize 没关。乐。

回考场玩贪吃蛇，等待比赛结束。

出考场找同学，怎么没问到 AK 的，害怕。张老师似乎不相信我的成绩。

午饭是淮南牛肉汤(烧饼)。它攻击了我的消化系统。暂未查明它到底被投放了什么调味料。

与广东队长聊天，听到了他没推完但是胡姐推出来了的神秘 T1 容斥解。惊为天人。

APIO 嘉年华。踢毽子好玩。获得了一组键帽。好耶！

查分，没挂。

听讲题，但其实没在听，Lichess 谜题好玩。drc 试图给我讲 NOIP T3，我声称我已忘记题面并希望重新思考，但是过了几分钟发现大脑已关闭。

晚饭和 drc 吃汉堡。发现餐券足量，遂加了一些小吃。好吃。

回酒店后在床上 [小手机真好玩.jpg]。

和 llx、drc、张超老师吃夜宵。聊天很欢乐。

Day 2

讲课/社会实践日。

6:50 起床。困。

早餐是猪肉肠+鸡块+青菜+风味披萨+面包(黄油,计士)+橙汁+小蛋糕。披萨咬了一口就扔了，什么鬼东西。其它的还不错。

Ad-hoc 题感觉很 ad-hoc。有几个见过，有几个做出来了，有几个根本不会做。

量化分析全程睡觉。Segbeats 试图听了一会，但是还是睡了。

午饭是石锅拌饭(茄子肉末)。好吃！！

在没有午睡并且背着一个电脑和一瓶水的情况下被拉去社会实践。科技公司很厉害，北大很美，但是我好累。

晚饭依旧是石锅拌饭(茄子肉末,黑椒牛肉)。我爱石锅拌饭。

小卖部好多人。我用两张餐券兑换了 9*苹果汁+1*牛奶。我是苹果汁爱好者。

闭幕式。听到了杜子德讲话，与 ORzyzRO 大神交换了徽章。作为 rk1 上台领奖还是很开心的。

晚上加入了音趴群，但是没去，在房间收行李。

现在写游记的时候后悔了，应该去玩一玩的 qwq

Day 3

疏散日。

早餐是牛肉肠+黑椒里脊+广东菜心+麻酱花卷+面包(黄油,草莓酱)。好吃，但是作为广东人我不承认那是菜心（

同校学生出了不少状况。drc 的充电宝落在酒店了，yhr 的包忘记拿了，教练忘记给 ymh 订机票了。

由于选座太晚只能坐中间座位。但好像也问题不大。

落地的时候似乎 ymh 刚刚从大兴机场起飞。可怜的 ymh。

回家啦！家长在 APIO 这几天给家里的床换了新床垫，软乎乎的很舒服。[小手机真好玩.jpg]

The end。

后记：饭评

满分 10 分。

Day -1 晚 8.2

Day 0 早 8.2 午 7.8 晚 6.9

Day 1 早 8.3 午 4.0 晚 7.0

Day 2 早 8.1 午 8.0 晚 8.1

Day 3 早 8.4

北大附中的饭堂种类很多很多，但我似乎没有吃到什么特别惊艳的菜。但还是比华附食堂好太多了。

酒店的早餐每天都很好吃，除了那个风味披萨以外全是好东西。

吃爽了。