(PKU+NOI)WC2025

· · 生活·游记

1.13

到达绍兴，然而发现宾馆订到了绍兴一中而不是龙山书院旁边，遂火速换掉。

期末考试出分了，他妈的历史薄纱物理，地理薄纱化学，政治薄纱生物，没救了。

随便看题，摆摆摆摆。

1.14

上午好像啥也没讲也啥也没干。

中午吃饭，但是等了一万年才吃上。

试机是去年 pkuwc d2t1 和 UOJ52，但是我压根啥也没敲，光敲缺省源了。

开始比赛！！！

开 A，发现好像是个神秘题。贪贪贪，假假假，急急急，爆爆爆，a,b\le4 都不对，一看发现已经过了 40min 了，有点红温，决定先打个暴力。

然后观察了一下 a,b\le 4 解的方案发现形式一定是若干个完全图，然后写了个暴力拆方案的 O(V^4) dp，然后就炸了，又调调调，差不多 1h 对了。然后打个表，观察 a=3 发现规律，然后又一看发现这个规律可以推广，然后在 1h20min 才过，我他妈有点太唐了吧我敲。

然后又点急了，直接打 B，C 的部分分。

B 写了个常数感觉还比较小的 O(n(n+m)) 过了 24pts，然后 C 显然缩点之后是等价的，然后 k 从小到大依次算，每次直接对着拓扑序 dp 一遍就好了，然后就 O(n^2+(n+m)k) 了，有 20pts， 这个时候过了 2h。

想了想 C 发现一点想法都没有，决定直接弃掉看 B（虽然一点数据结构都不会）。然后也是啥也不会，然后想了想发现好像 l=1 直接对 r 扫描线就好了，然后差不多 2h50min 过了这 17pts。

然后发现扫描线可以推广（？，复杂度貌似是一个 O((S(n)+q)\log^2n)，决定写一写，万一过 5e4 了呢？然后写一半突然发现我可以算一算 S(n)，一算发现 n=5\times10^4 的时候差不多有 S(n)=5\times10^6，这我过你妈，这时已经 3h30min 了，于是决定卡一卡平方，从 8s 卡到 5s 就卡不动了，可惜了。

赛后听 cqz 说直接裸莫队就是 $O(m\sqrt{n\log n})$。 草草草，我是傻逼我是傻逼我是傻逼，他妈的我真蠢吧我草我草我草。 不会正解是因为我菜，但是没想到这个莫队就是纯粹的蠢了。 ymh $100+100+20=220$，%%%。 ymh B 用了链表+回滚莫队，$O(n\sqrt m+m\sqrt n)$，很牛啊。 感觉虽然 B 有点蠢了但是还可以吧，至少没有蠢到 $l=1$ 没过。 ### 1.15 摆摆摆。 听讲座还挺有意思的。 开考。 发现 A 是一坨，猜测签到是 B，一看发现这不裸题！！！直接写写写，然后就过不了样例。发现题目看错了（？，改改改过了样例但是 0 分，发现假干净了。 一想发现好像没那么签到，遂又回去想看 A。发现不会不会不会不会不会！！！然后就一直瞪着 A，一直不会，有点红温了。大概 1h20min 有了一个应该是 $4n$ 的做法（？有 83pts，准备先写了，感觉如果再搞剩下 17 pts 容易爆。 然后就写了一万年，有一车细节，交上去发现只过了 sub1，剩下的 WA 了？？？这不对吧，怎么会 WA 啊，有点红温了。然后写了 gen，结果 $n\le 100$ gen 了 1e4 组才 WA。然后调调调，发现还要再加上一些操作次数（？，但是貌似没卡（虽然卡了也能加随机化草过去），所以在 2h10min 过了 83pts。 有点慌，感觉要没有二等约了，火速看 B/C。 B 先敲了 $c=1$，然后上个厕所发现 2 种决策之后应该剩的都是一段没操作过的后缀，然后直接 $O(n^2) $ dp 就可以了。然后就有了 73pts（？感觉能做，但是还是先去搞了 C 的 36pts，然后回来看 B，发现瓶颈在于求每个点开始操作之后第一个决策点 $g_i$，发现其实就是最小的 $j\gt i$ 满足 $S(i,j) \mod k+S(j+1,j+m-1)\lt k$，套路的拆一下取模就可以直接二维偏序了，先打个暴力证明条件转化的对，然后直接改成二维偏序，最终在 3h30min 过了 B。然后就卡 C 的 5e6，发现卡不过去，为啥我常数这么大啊（？？？ $83+100+36=219$，感觉算是翻了（？？？ 感觉 A 害人不浅，ymh 和 cqz都似 A 导致没有啥时间 B/C，可惜了。 $100+41+20+83+100+36=380$，除了傻逼莫队感觉都很满意了。 摆摆摆。 ## WC $100+40+5=145$ Fe，我是打铁大王，wcnm，这比分写你吗有机 算了还是写一点吧。 ### 1.17 啥也没干，认识了雪猫，FD，pjy。orzorzorz。 ### 1.18 上午听咋克讲，$\frac{1}{3}$ 完全能听懂，$\frac{1}{3}$ 不完全听懂，$\frac{1}{3}$ 完全听不懂。下午 rainbow_qwq 讲的就比较容易听懂了，除了最后掉线了 30min 都听懂了。 摆摆摆。 ### 1.19 上午如听，下午感觉讲了能听懂但是对我来讲思维难度有点太大了。 摆摆摆。 ### 1.20 试机 NOIP2024，写了下 T4，1h 过了所有样例。 感觉信心 ++。 开考！！！ A 不是啥子题，写完只有 65pts，然后调了 30min 才过，原来是数组输入反了，难绷。 然后看 B 发现一坨，看 C 发现很简洁。C 想了想发现只会 sub1，由于是 **难度巨大** 的 WC，所以理所应当的扔了（实际上当时确实状态不佳，以为不能 $O(nV)$）。 然后看了看 B，发现 $O(nV^2)$ 和 性质 A 是容易的，写完就结束了。 ？？？ $100+40+5=145

？？？

本来就比较担忧，听 pjy 说他 100+0+100 之后秒了 C，于是安心的似了。

然后又听 FD 和 AC_love 说 B 的 B 性质的答案部分也是不难的，于是感觉要铁。

1.21/22

铁了。摆摆摆。感觉没什么胃口。红温透了。

往好处想只是 WC，又不是什么省选NOI之类的炸光了。

考虑到去年 APIO 也出了 Fe，于是我觉得我可以加冕 LN 打铁王。

22 号下午润了。

我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬我吃柠檬