NOI2025 游记

· · 生活·游记

Day -??

省选成绩似乎还好，买到 D 了。

Day -?

打 UNR。周日晚上突然发现有笔试，但是好像没有背过题！直接自信选，考出了 85 的高分。

UNR Day 1 一个题也不会，鱼鱼蒸了。赛后发现 T2 不难，补了。

UNR Day 2。上来会了 T1 的 k=0 的全 0，然后又会了 k=1 的全 0。哦哦，我会全 0 了，拿下 60 分。哦，是不是改巴改巴就是正解？然后开始调，又花了 2h 才过，生气了。以为 T3 有决策单调性，写完发现样例过不去。发现后面两个题屁也不会，摆了。赛后订了 0 题。

哇，喜提 Cu。

Day -1

报道，整天打游戏。

Day 0

笔试，没有挂分。Gold 居然挂了 1 分，嘲讽。

晚上玩了一下 QQ 的篮球，听说篮球不会说谎。篮球说今年 NOI 有一道 n\le 20 的题。

Day 1

开场先读了一般所有题的题面，感觉顺序开题比较对。

看完 T1 发现有用的状态一点满足 p\le d_x，那么直接把每个点拆成 d_i 个就好了。别急，你是 NOI D1T1？又读了一遍题，发现没有看错，于是开始写。

比较唐，写了半天。写的时候还发现最后一步可以不满足 p\le d_x，要特殊处理一下。差不多 1h 的时候终于过了 T1。

开始研究 T2。看起来第一问简单一点，那么先来研究第一问。操作一个点后一个点会被清空，那么可以有 \mathcal O(n^3V^2) 的区间 DP，不过这复杂度也太大了。

考虑能不能弱化条件：把操作改成每次选相邻的两个点都减去正整数 x。简单手玩了一下发现好像不太有问题（伏笔）。看了半天没有看出别的性质，去看 T3，看了半天屁也不会。那么开始 DP 吧。设 f_{i,j} 表示 [1,i] 操作好后，a_i 减去了 j 的最大答案，直接做是 \mathcal O(nV)，但是可以维护值域的连续段，那样就是 \mathcal O(n^2) 了。

写了个 \mathcal O(nV) 过了第一个样例，改成 \mathcal O(n^2) 后发现第二个样例过不了，怎么回事？瞪了半天发现好像没有写挂，发现第三个样例有小的，测了一下，有一个没过！拿 \mathcal O(nV) 记录转移点跑了一下，草，结论是错的！原来 2 3 3 -10 10 -10 就可以 hack 掉！

看了一眼时间，已经过去快 3h 了，只剩 2h 多一点，而此时我后面两个题还一滴毛也不会！

丁\quad丁\quad吓\quad断

赶紧来拿一点分，感觉那个 \mathcal O(n^3V^2) 只记录有用的状态可以跑过数据随机的小数据，于是写了一个。但是写挂了，调了半天调不出来！此时仅剩 110min。

别急，模拟一下样例。在纸上随机画了几个箭头，由小的指向大的。突然发现一个点最多指向一个点，那也就是序列可以分成 \rightarrow\rightarrow\leftarrow\leftarrow\leftarrow 这种东西，那我对着这个 DP 是不是就好了！想得明白了一点之后写了一个 \mathcal O(n^3)，过了 24。此时还有 80min。

我们来考虑数数！我要序列和箭头双射，那么需要保证操作成 0 的数不指向另一个点，写了几下发现挂了。仔细思考，对于操作出来的两个相邻的相同的数，应该只算一次，写了几下又挂了。测了一发，发现过了 B 性质，说明肯定还是相同的数的处理有问题。仔细看了一下，发现有个地方判得不对，改完就过了样例，获得 60。

能不能骗点分？代码里 \mathcal O(n^3) 的部分是处理所有区间的答案用于转移，试着在 n>500 时只转移 r-l\le 150 的区间，结果直接过了 85。感觉优化比较困难而且没啥必要，还是去看 T3 吧。

还剩下 40min，思考了半天 T3，无果，最后写了个 8 分罚坐 15min。

selfeval 得分：100+85+8=193。

走之前偷看了眼旁边老哥，发现他 280，太牛了。出场后发现群里大家都说自己 200+？那我不是爆蛋了。

查分发现没有挂。

Day 1.5

去绍兴博物馆+城市规划馆，有点唐，流汗。

下午电影翘掉，ztr 帮我下了 MC，那就和 ztr jzh yzl 打 MC 吧。打到睡觉。

Day 2

开场读了一遍所有题的题面，发现篮球确实没有说谎。

感觉还是要顺序开题。感觉 T1 就像是得到结论之后维护的题，并且两部分应该比较割裂。首先发现只有 101 和 110 会变，玩了几下发现 101 没有什么影响，第一个 110 会逐渐扩展，把后面都变成 1，那找到第一个这个的位置 p，答案就是 n-p+1。但是如果没有 110，那么就要看有没有 101，如果有的话还是要操作一次。

写了个暴力获得 55。这个东西是可以线段树维护的，但是感觉常数会很大。想一下有没有更加简单的做法，去上了个厕所，回来感觉应该没有。开始写，到 1h 的时候写完了，最大点 1.1s 通过。

哇，这个 T2 看起来就是集合幂级数题！首先可以 \mathcal O(8^n)，感觉瞎搞搞可以 \mathcal O(n4^n)，但是再优化就很困难了。随机思考了 1h，但是还是啥也不会，于是去看 T3。

首先要二分 k。感觉这个就是经过上下界走折线，考虑防御牌个数减攻击牌个数，范围就是 [-k,k]。但是 n.k 奇偶性不同有 corner case，很讨厌，不过这个时候可以在 n 后面加个 0 或者 1，两者都合法就是合法。操作相当于后缀整体抬升，那从前往后扫描，如果需要抬升且可以抬升就抬升。写了一个过了 35。

思考了 10min，感觉这个做法很难优化。又会了一个做法：从后往前，可以取的初始值是一个区间。写了这个也过了，不过看起来还是很难优化。

这个时候还剩 2h，感觉 T3 非常困难，不如看看能不能做出 T2。突然发现隔壁老哥草稿纸上全是式子，想到能不能容斥处理 P\cap Q=\varnothing，然后就得到了 \mathcal O(n2^{n2^n}) 做法，绷。又想了半天，还是不会呀，我急了。这不是集合幂级数题吗，咋能不会的！

想了半天，还是他妈不会，摆了。开始写 \mathcal O(n4^n)，这个就是求出 g_{x,y} 表示 f(P)=x\land f(Q)=y 的方案数。随便写了个的东西发现样例二过不去，然后发现要用 a_i+1 的逆元，畏惧了。不过这个东西可以 1.8s 过 n=12，看起来不错。哦，原来 FWT 的时候贡献算算就可以避免逆元了，写完过了样例二。但是，一测发现 n=12 要跑 2.1s，彻底怒了！

还剩 10min，开始卡常。但是卡到 12:59，还是要跑 2.02s，无语。其实我知道可以取模是可以优化的，但是我忘了怎么写了，呜呜呜。

selfeval 得分：100+32+35=167。

查分发现没有挂。听说 Ag 线 450\pm\epsilon，那 460 应该有 Ag 了吧。

篝火晚会去了一半感觉太无聊，回来了。

晚上我们教练问我们认不认识一个选手，我一看，这不是 irris 吗。看了群才发现他用凳子扣篮砸坏了地板，无敌了。打 MC 打到零点。

Day 3

文艺汇演，居然有《夏天还不算开始》，很开心。

颁奖的时候没有空调，非常热，但是《海阔天空》很好听。Au 571，Ag 410，这也太抽象了。

边哥家长群 13 人出征 NOI，0 Au，9 Ag，4 Cu。唉，怎么会这样？看不到未来了。