嗯哦哎遏玲扼午油继

Coffins · 2025-07-15 17:27:39 · 生活·游记

Day -1

入住，发现空调爆炸了，于是被迫热了一下午，最后给换到了对面的备用寝室，于是复活了，然后就一直在摆隔膜。

Day 0

开幕式聆听肚子的抽象讲话，然后观看了 sxyz 的抽象小品节目，鉴定为完全不是人，只能说薄纱 AIOP 了。

然后感觉笔试忘了好多，于是回宿舍在洛谷有题上面又捋了一遍，感觉没什么问题。

下午出发去笔试，到那以后发现热炸了，让我等待的那个屋子里面没有空调，然后一进答题的屋子发现冷炸了，难绷。笔试轻松阿克，只能说难度不如 unr 笔试一根，然后试机就敲了个 A 题，selfeval 过了就开摆。过了一会笔试结束了，于是开始和雪猫玩皇游，随机卡组大战脚本，后面忘了。

回去突然发现没写什么板子，遂疯狂敲板子，算是复习完了。

Day 1

早起怎么这么坏啊，后面忘了。

robot sequence tree

开场看 A，发现怎么是啥子题，直接写 30min 通过，符合 D1T1 印象。

接下来看 B，感觉很抽象化，看 C 发现啥也不会，于是继续想 B。

想了一会注意到一种合法的操作方式一定是若干段两边向中间，于是直接 O(n^2) dp 通过了第一问，此时已经 1h20min 了。

然后开始犯糖，想了一个很诡异的刻画唯一操作的方式，直接做是 O(n^3) 的，于是通过了 76 分，此时差不多 2h。

接下来开始优化，因为一些唐氏原因调了很久，然而最后还有一步需要优化，但是突然注意到可以 bitset，于是试了试，结果 O(\frac{n^3}w) 啪的一下直接过了，绷不住了。

分析一下发现瓶颈在 A 全相等的时候卡满，而 pretest 这个包每次都只跑了 2s 左右。

于是假设我通过了 B，此时过了 2h50min。

开 C，结果想了半天还是只会 O(2^{2n-1})。

然后思考 A 性质，观察了半天注意到充要条件维每一对点对在两颗子树内的 lca 的顺序相同，直接写是 O(n^2)，于是获得了 28 分。

然后又观察了一下发现没有 A 性质只需要多讨论一种情况，于是有了 O(n^2)，56 分，此时过了 4h30min。

然后发现二叉树每次操作只需要 check O(\log^2 n) 对点，每次check可以转化为二维数点状物，于是就可以 O(n\log^3n) 求 B 性质，因为树状数组常数小所以应该可以过。

于是写写写，结果调不完了，于是丢掉 24 分。

预估 100+100+56=256，感觉差不多 Ag 200 左右，Au 280。

出来感觉跟我预估的差不多，有一坨 256，感觉还是要 Day2 来区分。

出来和 FD 还有雪猫讲我的 B 题，然后越讲我越怀疑我会被卡掉，不过应该卡掉也只有不几个点，应该少不了几分。

复评发现没挂，甚至最大只跑了 1.9s，远远快于 O(n^2\log n)，有点难绷。

Day 1.5

跟着安排随机游走。

回来后啥也没干，一直摆烂。

晚上看了看板子，学了学 BM。

Day 2

首先看 A，稍微刻画一下就知道了结论，写个暴力过了 O(nq)，然后直接上个线段树就过了，耗时 1h。

然后做 B,想了一万年编了个 O(3^n\operatorname{poly}(n)) 的做法，开写，呱呱呱，欸我怎么似了。

然后在 3h 的时候发现假光了，爆爆爆。

重新想，不妨记 f_{S,T} 为f(P)\sube S,f(Q)\sube T 的方案，这个东西是可以 O(1) 算的，于是会了 O(4^nn)，瓶颈在高维前缀和，但是怎么只能过 n\le10，只有 24，又打了个表瞪了一下每一项对答案的贡献，于是会了 O(4^n)，过了 n\le1 2，只有 36，破防了，这个时候 4.5h 了。

没时间做 C 了，瞎写一通 O(nq\log k)，过不去 n,q\le3000，只有 25，破防下播。