NOI2025 游记

· · 生活·游记

书接上文，rk9 进入江苏省队。

7.2

代码源公益 day1。

T1 一个小时发现结论，再写了两个小时通过了。

T2 和 T3 拼暴力，那咋办。

学会了 T2，竟然能这样建二叉树。竟然最大流等于最小割。 ## 7.3 代码源公益 day2。 T1 一个多小时过了。感觉没啥难度。 T2 一个多小时就已经求对答案了（只有我是二分答案然后 dilworth）。然后上 trie 直接构造答案构造了将近三个小时，玉玉症了。最后写了个搜索答案的 $O(k^n)$ 获得了 $60$ 分（$n\le 10^5,k\le 4$）。 T3 写了八分钟的 $27$ 分，没调出来，只有 $9$ 分。 $100+60+9=169$，rk33。倒闭了倒闭了倒闭了。下次应该稳住心态写暴力的。 下午胡了一下 T3，一下子就会 2log 了，但是要写很多代码。逆天场。 T2 学会了。这怎么想到的？ 晚上和 pak 和 mygr 打斗地主。 ## 7.4 早上和半个下午写了【数据删除】题的若干份代码。没有补题，因为想补的大概当天都补完了。 然后后半个下午做一下 mx。感觉 T2 很简单。T1 咋做 T1 咋做 T1 咋做？？？为啥大家都会做？ 然后 T3 编了个结论，不会 dp。学了 yrq 的平方 dp，然后感受到大概可以树剖然后凸优化。这是人能通过的？ 晚上接着斗地主。 ## 7.5 代码源公益 day3。 T1 怎么这么难啊？我的 $O(n^3)$ dp 在一个小时的时候才通过 $n=3$，原因是忘排序了。然后二十分钟过了。 T2 怎么这么难啊？竟然不是停时定理啊。那咋办。概率难算那就考虑放回，然后编一下。怎么编。大概想了接近一个小时得到了一个看上去有点道理的做法，决定手算一下样例。算了十几分钟发现竟然是对的（中间可以借助代码状压算一个的期望）。然后就开写了。然后发现我的转化的 $O(2^mm)$ 过了，开心。 然后尝试考虑容斥。我容斥太差了啊。做了半个小时才把容斥写明白，这时候是 $O(3^m)$，但是非常有扩展性！花了十分钟改成 $O(m^2)$ dp 然后通过了。 感觉 T3 完全不可做，拼了一个多小时包通过了所有特殊性质。 $100+100+47=247$，rk1。耶耶耶。 原来大家 T2 竟然都是不放回啊，这么变态，理解不了。然后发现我连自己的第一个转化都理解不了了。不管了，就说过没过吧。 T3 有点唐，不想补。 晚上四人斗地主和爆炸猫。新学的游戏还能十把赢了四把，好玩。 ## 7.6 代码源公益 day4。 T1 三分钟看完题加写出 $O(nq)$ 的暴力，还通过了 $n,q\le 10^5$ 的包。 然后改线段树。扫描线把 `i` 写成 `l` 了（往左扫左端点，而 `l` 恰好是用过的变量）。在二十分钟的时候才通过。 T2 感觉很困难。二十几分钟才发现每个国家竟然必须连通。然后又想了十几分钟才发现充要条件。然后又想了十几分钟直接树 dp 距离区间，发现不会做。然后发现可以直接把状态设成每个点。那限制是邻域加。那淀粉质。那做完了。 半个小时写完了。现在是两个小时。 T3 是题吗？好像四个的一定能全覆盖。真的吗？如果是上升点列呢？玩了一会儿发现好像也行。那就三方枚举。 写一个点的情况的时候发现需要二维数点。但是离散化完了好像是 $m$ 啊去你妈的，然后写了主席树。写完发现离散化完了是 $n$。然后把主席树删了改二维前缀和。愤怒。 然后总共写了不到一个小时，拍了一拍就过了。挂的地方竟然全是只选一个点和二维前缀和。复杂度是 $O((4n)^3\times 7\times 2)$（算答案的时候划分成 $7\times 7$ 的矩形），这个常数还没算上二维前缀和的四倍。反正跑过去了。 $100+100+52=252$ 跑路，rk1。T2 过了 48 个，T3 过了 0 个，如此模拟赛，令人汗颜。 mx t1 都不会做，那咋办。 晚上 UNR 笔试。意识流做完之后还错了一个题，这下质疑精神状态了。 警钟敲烂。 晚上看了一眼 CF。怎么 DEF 都这么难。然后 DE 和 F1 会了，睡觉了。 ## 7.7 F2 怎么这么难。 UNR day1。 T1 怎么这么难。 想了一下发现好像 C 性质挺好做的。写一下。画了几个图手玩一下，写一写，调一调样例 2，运气很好，在四十分钟的时候通过了。 感觉剩下的部分也不是很难。写一写，调一调。最后样例 2 挂了 $O(1)$ 个点，找出来发现竟然是 C 性质。那你数据也太弱了。然后改了一个错的时候就过了，这时候是七十分钟。 旁边 pak 本来一直在看知乎，然后突然说会 T2 了然后开写了。吓。 然后想了一下贡献可以摊平了拆到每条边上。平方都不会咋整。然后想了一下感觉至少应该有个东西是增量。好像是点集。写一下三方，然后 wa 了。这时候是将近两个小时。 然后自闭了二十分钟，感受了一下，感觉费用流就证完了，然后调一下样例才发现是三方写挂了。改一下就过了。 然后打一些表看看性质。猜一下是不是互相包含的。assert 一下发现挂了。改一改又不挂了。大雾。然后又想了好久，想起来打个表看看是不是先选的一定不会包含后选的。然后想想好像就只要维护区间信息就做完了。这时候是两个半小时。 然后写了二十分钟的暴力。然后平方过了。改了十五分钟主席树。然后被卡常了。卡一卡就跑到 1.3s 了。 T3 这么难。写了个乱搞，直接求每个点是否可达所有点。交上去只过了 sub1。然后跑一下样例发现知道哪里错了，必须选一条路径，两条分叉不能同时选。好像这个 hack 规模都在 10 以上，那 sub1 就对了。 $100+100+12=212$。 没挂，rk 22。怎么这么多 T3 高分啊？？？？？金线 208，那咋办那咋办那咋办那咋办那咋办。 下午，代码源公益 Day5。 奋斗一小时不会 T1，只会 T2 的 $24$ 分。遂开始跟进 unr 的 st。然后又奋斗了一个半小时只会把 T2 的 $24$ 改成 $32$ 然后改成 $46$。 这个时候被透了 T1 要思考区间被删的充要条件。那会了啊。然后半个小时就通过了。牛气冲天。 T3 不想看。 $100+46+0=146$。 晚上出去吃火锅。斗了两个小时地主。回来四人斗地主，爆炸猫，毒药，毒药连着三把第一，好玩！ ## 7.8 UNR day2。 T1 怎么这么难。找找规律过了 $a_i=0,k\le 1$。这个规律有点好玩，然后就发现了一些关键性质，通过了 $a_i=0$。 然后这个连 $k=0$ 我都不太会 dp 啊？大概会了一个跟 $2k$ 有关的状压，可能是 $2^{2k+\epsilon}n\text{poly}(k)$。但是不想写。 然后对着暴力验证了更多有用的结论。在两个小时的时候终于通过。调代码的时候 pak 举手高呼会了会了我无敌了然后写了几行接着刷知乎（大雾）。 想了一会 T2，发现和 CTT2024 D3T3 有点像，有点想法！写完了一部分代码，然后又想了一会儿发现划分独立集部分好像根本做不了！然后又想了一会儿用一个很蠢的办法大概解决了。 写一写调一调，毛估估按照 $f(\frac{\text{myans}}{\text{require}})$ 这个评分的话有不少分。然后获得了 $72.8$ 的好成绩！然后拼了一下 sub1（对的，它过不掉 sub1），变成了 $74.63$。 pak 由于刷知乎刷太久了，现在才通过 T1。 然后写一下 T3。发现了 $O(n^2)$ 可以通过 sub3！！！获得了 16 分。 然后开摆了。相当于每天只打了四个小时，那咋办。然后开始写游记了。 最后是 $100+74.63+16=190.63$。没挂，rk18。 下午去线下打麻将了，打了两把都吃四了，好耶。 然后中途出榜了，$99+100+100+12+100+74.63+16=501.63$，喜提 rk10，以及前十名唯一一个 D1T3 低于 $40$ 的（而且还只有 $12$）。 ## 7.9 早上发现两天前的模拟赛出榜了，rk16。想不到 T3 不动也有这么高，好像是大家都没认真打，T3 貌似不是很难啊。 然后是，代码源公益 Day6。 T1 看着就非常困难。看一眼 T2 发现又是这个从来没做过的经典大模型。T3 看着非常分流器。 然后 T1 看到 $A_i=3$ 上去猜了一手 $3^m$，然后发现依赖开错了？然后想了一会发现他妈的怎么不连通。然后也不想写，想了一会儿 $A_i=2$。发现是环计数，好像并非困难，然后写了一发，得 0 分。 然后急眼了，写了个 $O(2^mm)$ 的暴力开始检查。发现我式子打错了。然后又发现这个沟槽的图不连通答案还要减掉连通块数再加一。然后过了这个 sub。然后一分钟过了 $A_i=3$。 然后不会做啊？还不知道为什么 $A_i=3$ 一定可以构造出来，至少毛估估感觉是对的。然后就开始猜做法了，大概是每个连通块先把 $\frac{w}{[2|w]+1}$ 的权值乘上，然后就是乘上选择偶数边使得合法的方案数。编了一个 dfs 树相关的做法，调不过样例，发现假完了。然后脑电波了一个把奇数边缩起来，写了一下就过了。 然后才发现奇数的构造。 T2 看着就很唐。首先一看就是暴力修改，要找到修改的位置。好像很多地方直接暴力是对的。好像二度链上是错的，那是不是直接在树上维护链剖。我会把链底放到链顶！但是询问的是编号为 $A_i$ 的蚂蚁，那只要找到它在哪个点就对了！然后发现不会做。 然后开始编维护蚂蚁的相对位置。这个感觉比较有道理。考虑把相对位置建成一棵新树。每次修改相当于把所有度数至少是三的点的儿子合并成一个。看上去很可以 lct。举个例子： ``` 7 1 2 1 3 1 4 2 5 3 6 4 7 ``` 如果在这棵树上操作 $1$，那我们要把 $2,3,4$ 合并。这时候首先需要合并集合，然后选一个主元。以 $2$ 为例，我们可以把 $3,4$ 两个点删掉，然后把它们的儿子 $6,7$ 连一条边到 $2$。这样就全对了。唯一的问题是找到它的父亲，所以使用 lct。 考虑合并顺序，其实应该从下往上合并，这样每个三度点操作的时候的儿子都应该是二度点（可以发现合完之后新的点就只剩一个儿子了）。具体实现可以不按深度排序，而是采用递归的方式：如果一个点的儿子是三度点还没操作，那就操作一下。中途维护一下三度点集合就好了。 贺了 deepseek 写的 lct 板子。写了好久，拍了好久，到比赛三个小时的时候还是 $0$ 分。中途还调了它的 lct。问题是它在 `pushdown` 里交换两个儿子，但是找父亲的时候竟然先判断儿子是否存在再 `pushdown`。 然后最后在三个半小时的时候通过了。 T3 打了 $23$ 暴力跑路。 $100+100+23=223$。 最后 pak 声称会了 T3 $77$ 但是写不完了.jpg： ![](https://cdn.luogu.com.cn/upload/image_hosting/t5nkl5i2.png) 结果结束一看怎么不仅有 ak 的还有十三个通过 t2，那咋办，感觉天塌了。 结果一出榜一看居然是唯一 rk2。大家 t3 暴力都打不过我？？ 晚上去 pak 房间看超天酱 cos，学了好久怎么把彩带挂到假发上，好高妙！还充当了一会儿衣架子（戴着假发让别人操作），但是被抓拍鬼图了/ng。后面让我拍照，但是没拍出来好照片啊，那咋办，最后还是对镜自拍的一张最好。tyx 真神了。 ## 7.10 代码源公益 Day7。 怎么这么快就要到 noi 了？？ 我草，三个 $n$ 很小的 dp，那做你妈呢。 奋斗 T1。先按性价比贪心，然后可以微调。那特殊性质都会了啊。然后编了一个折半，编了一个小时细节，做法是枚举两边的路径，然后求出每个性价比分界点附近的 $O(1)$ 个点（开了 $100$ 左右），然后合并。然后发现 $n=2$ 就卡掉了（理由是分界点处的值可能在某一半边去了一半，就错了）。 一个半小时了得 0 分？？然后想了一会儿 T2，二十分钟通过了。这是人？？？ 然后写 T1 的乱搞，大概证了一下复杂度是 $O(\exp(\frac{n}{e}))$ 状物，然后写微调 dp，犯了五六个低级错误，然后在三个小时的时候通过了。 然后 T3 先写 $O(3^n)$，发现怎么转移有环？把环去掉怎么这么难？发现不会合理写出转移顺序，遂写记搜，调了好一会儿（二十分钟），然后光荣 tle。 然后想了想好像可以压一压状态（关心每个 $a$ 的出现次数），然后以最大点 $73$ms 的好成绩通过了 sub1。 然后想了想为什么不能跑 sub2 呢？改了半个多小时改对了，sub1 最大点 $12$ms，然后 sub2 光荣 tle。 赛后发现一点点剪枝都没加，完全倒闭了（例如加起来足够多的时候就可以 `return 1;`）。 那咋办那咋办那咋办。这能 $\text{poly}(n)$？这能 $\text{poly}(n)$？这能 $\text{poly}(n)$？ $100+100+20=220$ 跑路。 七场平均 $\frac 17(175+169+247+252+146+223+220)=204\frac{4}{7}$，还行。平均每场过了 $1\frac{4}{7}$ 个题。 然后出来一看大家搜索都有 $60,80$ 的好成绩，破防了。被搜索剪枝干爆了。我为什么不会剪枝？？ 最后是 rk12。 ## 7.11 没搬地方。 上午十点半突然想学 lct，紧急突击，午饭前背出来了，过了板子。 中午吃了烤肉，又贵又油，那咋办。晚上吃了烤肉隔壁的煲仔饭，还挺好吃的。 晚上妈妈和弟弟来了。好耶。 ## 7.12 上午搬酒店。哇新酒店好牛的样子，但是我住不了。 下午睡了一会儿去学校了。沟槽的下雨啊。然后找宿舍没找明白，一开始到 3 栋 3 楼去了，绕了半天，回到 2 楼找到了宿舍门口，然后终于找到了宿舍。发现了三餐券，真唐。 然后打了一会儿斗地主去吃晚饭了，晚饭还挺好的啊，还有拿走一整瓶雪碧的传统艺能。 晚上开了把雀，由于故意乱打终于下到了杰二。四麻的豪一就不动它了。 发现没带毛巾？？洗脸巾启动…… 九点四十睡觉了。 ## 7.13 晚上睡的不是很好，醒了两次都不敢睁眼，怕睡不着。然后七点起床。 开幕式启动。感觉后面的节目都很有趣，很好看，很震撼，非常好啊！有人喷节目是抄的，但是有乐子本就挺好了，抄不抄的不重要啊！连舞蹈和唱歌都是很不错的！ 然后定着大太阳拍照和领密码条。 中午背了一会儿笔试，然后睡了一觉，打算到一点半，然后再去集合。结果一点四十多到那一看大部队正好要走，无敌了啊！ 然后场馆里非常热，出了好多汗，又看了一会笔试。 进场，左边 pmd，右边 xzh，wrk，tyx，畅聊，优势在我！然后试机写了 noip t2 和 sam，然后考前两分钟畅聊 Fn 那些命令。然后笔试轻取满分，耶！然后中途不知道干嘛，十分钟写对了 lct。 然后不让回去，玩了出包魔法师，完全玩不明白了。 晚上写一下 sa（重点可能是 height），检验方式是和暴力求两两 lcp 比对。七分钟通过。 晚上八点半熄灯，然后翻来覆去将近两个小时睡不着，然后不知道怎么睡着了。 ## 7.14 五点半的时候梦到自己醒了，然后被诈骗得睁眼睛了，结果真醒了，难过。有点晕，小问题。 快进到进考场。三十八分就坐到座位上了，然后不知道怎么度过了二十多分钟的时间。密码是 `noi45*45=2025!`。 先看了一遍所有题目，发现两个 $10^9+7$，吓人。读懂 T1 之后发现是宝宝题，但是先写了个平方暴力，过了样例之后写正解，二十分钟通过了。这时候是 `8:23`，考虑到总次数有点少，先不交，等下一档想交的部分分再说。 看一下 T2，大概想明白了一些性质。大概就形如一个点开始一直往后推进，然后两处推进会合。那第一问至少有 $n^3$ 了吧？感觉很像二轮省集训 day 忘了 T3。写了一下，写法是对于 $[l,r,p]$，先枚举 $l$，在 $p$ 的位置存下来，再在枚举 $r$ 的时候枚举 $p$。在 `8:50` 的时候和 T1 一起交，获得了 $100+36+0$（对的，$n^3$ 第一问除了后两个点都过了，连 $3500,3\cdot 10^4$ 都过了）。 然后把 $r$ 处的枚举 $p$ 改成了二分，就是 $n^2\log n$，通过了第一问，但是这里莫名其妙花了 $30$ 分钟，还写了拍子。这里是 `9:20`。 然后想一下第二问，感觉确实很容易算重。一开始魔改我的第一问做法，写了点 $\frac 12$ 和 $\frac 14$ 状物，测样例发现 case 太多了，遂换做法。想到了直接转移一个区间，令其中有 $1$ 个或 $0$ 个非零，推了一点条件，发现最后的和大概是 $\sum (-1)^ia_i$ 状物。然后写了一下，好像直接暴力就是 $n^3$。这个时候还没想明白会不会算重。然后运气很好直接通过了，获得 $76$（有 $60$ 的满分，剩下是 $40\%$）。这时候是 `9:53`。 毛估估可以直接二维数点。先看区间和是 $0$，我草是不是只要一个 cmp 就好了。然后再看非零怎么二维数点。欸好像是不是枚举完 $l,r$ 之后形式非常简单，是不是不需要二维数点。写一下前缀和。那 $n^2$ 了。调了一会儿，`10:07` 交了一发，直接过了，跑 $3$s。 然后发现我的第一问实在是蠢完了。把它改成第二问的做法，又调了好久 $i,j$ 写反，在 `10:21` 的时候 $0.6$s 通过。那 $6$s 何意啊？ 然后开 T3。首先看样例发现答案是 $2$ 的幂。那也不会啊。这个 AB 性质竟然没给样例，那是不是猜猜猜。那不得不写暴力了。花了好久才写对 $2^{2n-1}n^2$，原因是根本不知道怎么搜索所有 dfs 序。然后手造了 $n=10$ 的完全二叉树，发现本机跑了 $4$s？？？然后加了点卡常，然后发现一点用都没有。然后发现编译命令写成 `g++ 2.cpp -o -O2` 了。然后直接对着 $n=4$ 的满二叉树猜猜猜。好像答案是每次除以 $2$ 啊。然后不想交，接着思考。 然后想了想还是想要验证一下 AB 性质的结论。在 `10:52` 交了一发，得到 $100+100+16$ 的好成绩。还有两个小时，怎么输？？？ 然后随机思考了一会，发现没有往 $2$ 的幂上思考。然后想了一下刻画 dfs 序，那就是每个非叶子节点抉择一下先往左还是先往右。那大概是不是有一些点可以随便选，剩下的点就固定了？那好像根是随便选的，然后呢？ 然后想起来那个条件了，我之前竟然忘了。那就是不存在 `abab`。那这是不是充要条件啊？枚举一下两个颜色 $a,b$，然后呢？对于 A 性质相当于根的两侧有两个点作为两边 $a,b$ 的 lca。那限制大概就是这两个 lca 的走向必须相同或不同，那是不是连起来。那如果不是这个形态呢？从合并的角度分析了一下，只有三种情况，如果是 $a,a$ 先连起来那就没有限制（这四个点完全没有祖先后代关系，真厉害），否则除了那个就是一个 $ab$ 连起来然后依次往上挂上 $a$ 和 $b$。想一想大概也是，两个点的决策相关啊！那是不是，对完了。 大概想了一下怎么实现，好像需要写树上问题了。那就写个 $O(1)$ lca。然后大概就是每次加入一个颜色就枚举之前一个颜色，然后用并查集合并非叶子节点。运气还行，调了一会儿就过了，这时候是 `11:25`，获得 $100+100+64$，怎么输？？？ 然后想开摆了。想了一下 A 性质，发现完全不会做。B 性质怎么有这么多分？想一下满二叉树难道有性质吗？欸这个深度是不是不大？那是不是加入一次颜色，影响到的点对只有 $\log^2n$ 个？？？想一下 A 性质的部分大概可以套个 `map` 解决，后面估计差不多，那是不是做完了？？？ 然后调了好久才调明白，中间不小心改到了输入的一行 RE 了好久。然后才发现跑样例 $5$ 竟然没 diff 出锅。然后发现样例 $5$ 本机 $7.5$s，那咋办那咋办那咋办？？？ 然后先加上快读，稍微快了一点点。然后发现三个 case 里有一个好像限制都是祖先后代关系，不需要 `map`，改成数组，又卡了卡，变成了 $4$s。然后玉玉了一会儿，发现另一个限制大概也可以开数组，然后变成了 $3.7$s，哦耶。 这时候是 `12:12`，交一发，$100+100+80=280$！！！发现本机 $3$s 样例，交上去 $1.6$s？？？然后感觉剩下的东西完全不可做，开始罚坐。 一开始重新看了一遍三个代码，长度大概是 $3,2,4$ KB。然后又重新交了 selfEval。然后还有好久，发现没举过牌子，举了水牌。不想吃东西。然后想了一下 T3，感觉完全做不了，然后突然发现可以用满二叉树跑最后几个包。然后交上去发现 $24$ 跑了 $4.4$s？？？但是好像我完全卡不动常数了。（flag） 然后开始数秒，又用了不知道什么方法终于熬过去了。出场问了 pmd $256$，感觉要赢了！然后直接给爸妈打电话，吼不可能输（最后发现这只是 Au 的必要条件，结果真输了）！然后冷静下来发现这个分好像很简单。 然后出来问问发现好像有些 $280$ 的。但是比队线高就行。 问 dyh 发现他说 T3 巨大傻逼，然后说了一个等价类结论。我操你妈？？？这他妈啥？？？不管了，活该做不出来。然后回宿舍讨论了好一会队线相关，发现队线好像没啥意义。感觉 day2 还是需要好好打的。 查分，发现没挂，结果 $24$ 跑了 $4.05$，$25$ 跑了 $4.2$？？？？？那不是再卡卡就过了？？？？？急眼了，但是没办法了。好像有阿克的，那咋办。 听讲题。`VegChicken`，忘了，`1kri`。T1 出题人在说啥。T2 说了啥，反正是不是一下子就做完了。T3 题解怎么只有三页？第一页给出结论，后面给出调整和证明。那咋办。然后正解是线段树合并维护 01 串，然后这个竟然是可以直接排序的？？？好深刻，好像之前就想不到这种东西。那不是 $\log^2n$ 吗？然后这个优化是一层一层做，那类似整体二分啊，也好妙！但是感觉根本做不出来这种东西啊？ 晚上不想吃饭，吃泡面了。脚有点疼，那咋办。发现趣多多很好吃。 晚上聊到了十一点。 ## 7.15 五点多就醒了？？？然后看手机到七点半，直接走。 过去的路上玩飞行棋，到最后我和另一个忘了谁一对一拼运气大获全败。感觉 noi 期间所有运气游戏都全错了，好耶！ 科技馆，为什么带队走这么快？第一层还跟上了，第二层直接不管了，都玩一遍再说！发现这种可以上手操作的设施还是太吸引人了，感觉仿佛还是小朋友。 然后光荣走丢了。找了半天，最后在影院找到了。好看，感觉很棒啊！但是不知道为什么看一半就没了。看的时候感觉这个社会实践活动还是很好玩的啊！ 然后后面逛了一些展厅，就没啥意思了。然后换了一个馆继续逛？？还是走过去的？？顺序又是神秘的 312？？ 后面都没啥意思，还有点困。 下午怎么没事干啊啊啊啊啊。 ## 7.16 先不记了。等有心情了再回来写。 反正 Ag 了。死因大概是 T2 的容斥方向全错，得到正确方向之后只剩一个小时，赛后又做了一会儿就做出来了。 评价是 noi 为什么只有两个题？