NOI2025 游记

· · 生活·游记

unr 太远了记不清了。

NOI45*45=2025!

什么什么绍兴来着 42nd，可能有个星号。

day-1

白天 vpNOI2024 剩的几个题。

T1 忘了。

树形图：

先考虑 BC 性质，如何在有一个一类点的情况下找出所有一类点。

首先需要可以到达 1，那应该有一条返祖边连向 1，或者间接连向 1。

那如果有两条返祖边覆盖它，就有两条路径了，不好。

所以就是恰好被覆盖一次且可以通向一个已有的一类点。

然后考虑二类点。

首先一类点还得是一类点，如果只有 1，那保留这棵树就够了，但是还有一些一类点，他们需要他们的返祖边，所以这个也要保留。

如果保留后二类点被覆盖两次，肯定就不行了，否则如果有恰好一个就把其他的都删了就行，如果没有就得选一个保留，而且通上去也必须得是二或一类点。

这里把多出来的边挂到上面的点，再树上差分一下即可。

然后需要找一个一类点。

考虑树一定有叶子，从入度为 1 的点往父亲缩，用并查集维护父亲和删点情况，把返祖边都挂到父亲身上，剩一个就是一类点，否则没有一类点。

没有就缩点后没有入度的 SCC 是二类点，剩下的三类。

树的定向：

先考虑暴力，每次找出一个限制还没有被满足，且只剩一条边没填，就填上，否则贪。

这样一定有解，考虑把染完的边缩掉后就是特殊性质的构造。

那么就需要动态染色再维护一些路径上的东西。

直接数据结构很不好做，可以建图，边向限制连边，拓扑，度数为 1 的时候就入队。

使用倍增优化建图就是 O(n\log n)。

放学早了一点，听歌。

然后晚上收拾东西！这次带的箱子特别特别大，所以放了好多东西。

放了旧战服和新战服，放了一些校服，放了一些衣服，放了洗漱什么的的东西，放了拖鞋。

胡乱的塞了一些东西进去，剩余了很多空间。

看了一集星际牛仔，好看。

day0

早上飞机。

机场有一个大喷泉，很厉害。

飞机上拍到了很多美丽的云和天空。

学习了笔试内容，虽然还是完全不会使用 vim！

杭州下雨了，于是延误了很长时间，到的时候已经几乎晚上了。

接送站有很多布丁和小蛋糕，十分美味。

绍兴一中真好。

晚上再次启动了 2208，学习了树形图，好厉害的题目。

上厕所遇到了神秘大哥哥，被塞了一个徽章。

困了的小哥哥梦游到了教室，以二换四，赢！

见到了舍友，好可爱好可爱好可爱，我好幸福。

三个舍友都好可爱，好耶ヽ(✿ﾟ▽ﾟ)ノ

和室友交换了徽章。

day0.5

我缺的这块一剪梅谁来给我补上啊。

早饭还行，优酸乳好。

穿了新买的外套，太显眼了。

上午开幕式。

当 noi 还有 15 分钟结束，Ciallo～(∠・ω< )⌒☆。

诶诶大家怎么开始讨论 tp 了。

肚子演讲！

我认识鲁迅比较早了，米国制度好，让全国人知道你们干的事，把孩子们吃的光光。

逆天，尝试把稿子粘到这个位置结果洛谷没过审。

喷的气体有股怪味，烟花好看。

交换了 50 哥哥和小萝莉哥哥的徽章，他们都有好多种，哇。

然后自习了一会，领密码条了。

获得了钙姐姐的徽章，见到了 cfz 老师。

下午笔试+试机，怎么无法在试机中获得分数？

集合点也太热了。

笔试把所有终端指令相关的都试了一遍，需要计算的全算了一遍。

没挂分，好耶，ヽ(✿ﾟ▽ﾟ)ノ

大师拥有四个形态的徽章，哇。

晚上 gzy 哥哥来了，在教室里转圈转圈转圈。

自习，写完了树的定向，这个题也牛。

NOI 近几年真题都好牛，今年又将如何呢？

但是为啥 loj 上过不去，lg 还得经过卡常，嗯？ o(￣▽￣)o。

这个颜文字也萌。

day1

怎么就到 day1 了。

穿了一整套好看衣服，我真好看。

IA 酱可爱捏。

集合点超级热，这就是夏天了。

走在路上欣赏了沿路的风景，南方小镇的夏日校园风光。

清澈的天空，懒散的白云，朦胧的太阳，还有很高很高的电线塔穿过天空。

很好啊。

开场先看了三个题，第一个题是一个图论，第二个题是一个DP，第三个题是计数状物东西。

看了一会 T1 发现看不懂，于是去看后面的题。

感觉 T2 比较困难，于是看了会 T3 ，没有什么思路。

重新读了一遍 T1 然后会了，写完好像因为一些边界问题发生了一些调试工作，大概半个小时才过。

感觉 T3 看上去就很难所以开了 T2，看了一下可能会 A 性质。之后想尝试一下 n^3，做了一些类似区间 DP 的东西后发现会算重，然后拖到了序列上，又做了一会之后会了。

这东西看上去很好优化！于是先写了 n^3。

因为算重之类的问题调了很久，在还剩两个小时的时候调出了 n^3。

然后优化很好优化，但是因为边界没判好又进行了一些调试工作。

好像写了很久，调完只有 40 分钟了。

测了一下发现被卡空间了，先去写了 T3 爆搜，然后回来把空间卡了卡，过了。

感觉时间不够写 T3 了，于是检查了一下。

最后是 100+100+8.

然而 T3 好像 80 分有很多，欸 (⊙﹏⊙)。

这个颜文字也萌。

下午查分，没挂，ヽ(✿ﾟ▽ﾟ)ノ

听说社会实践去沈园，可以看小鸭子了，小鸭子小鸭子小鸭子。

小鸭子是 xyz。

下午听讲题，然后自习。

晚上自习 cfz 姐姐也加入了，膜 e 队爷。

回宿舍拥有了很开心的自由聊天时间，大家都好可爱！！！

A

每个点拆成度数个点之后跑最短路。

day0 晚上被出题人塞了个徽章，讲题的时候回了一个，好耶ヽ(✿ﾟ▽ﾟ)ノ。

欸ヽ(✿ﾟ▽ﾟ)ノ，这个颜文字好可爱。

B

第一问是 \max+，第二问是 +\times ，可以一起做。

考虑记 f_i 表示 1\sim i 的答案。转移考虑一个极短的操作区间。它肯定是从前往后一直操作，从后往前一直操作，在一个中间的位置停下。

确定操作区间后，这个值也是确定的了，考虑它可以在哪些合法位置上。

从前往后和从后往前的值对这个位置的贡献是一正一负的，那过程中肯定不能出现负。

其次，当区间奇偶数差为 0 时，需要特判转移。

那么在过程中如果出现 0，这个就不是极短的了，所以过程中也不能出现 0。

然后还对这个位置的奇偶性有要求。

所以有一个 O(n^3) 的做法就是枚举合法的位置，直接转移。

还有一个问题，这个转移过程中合法位置上如果有很多地方算出来的值一样，会算重。所以对于同一个值可以用哈希表记录最后的转移点。

优化就是预处理出区间没有恰好一个奇/偶数的和/最值，然后每次有了一段合法转移区间，优化一下就行了。

C

出题人好可爱，喜欢比比划划，这个题挺厉害的。

暴力可以枚举每个点先去左儿子还是右儿子。

然后叶子有值的时候相当于对这个先后有限制了，把这个先后想象成交换两个儿子，然后DFS序是交换后的先序遍历。

那因为保证有解，不妨假设已经转到了一个有解的状态。

现在考虑一个点是否可以交换。

如果有一对点穿过它，形如 ALB BLC，这个点肯定不能交换了，因为 B 会把它卡住。

除非，这个点是 ALB BLA 的形态，此时这个点是可以交换的。

那如果它是 A B 的构型，那后面或者前面应该有一个 B' A' 的点，'表示翻转，如果没有这个点就不能转，否则可以翻转那个点。

因为树可能还没有被填满，所以会有只有某一边有值的点，这种都能翻。

然后就注意到所有能翻的互相无影响的对肯定子树里所有只出现一次的点是一样的。

那么就相当于有一些等价类，如果一个等价类大小大于 2 才会可以翻，因为一定有一个在对面的。那么就相当于 2^{siz-1} 的方案数，所以最终答案就是 2^{n-c}，c 是等价类个数。

那么考虑如何统计这个等价类个数，O(n^2) 的做法是考虑每个点对应一个随机权值，每次修改一条链的权值异或和，处理出等价类个数。

之后考虑优化，相当于每个点有一个在时刻上的 01 串，表示它是否被赋值，把所有点排序后可以尝试计算相邻串的 lcp，之后就能得到每个串在每个时刻有多少个等价类，然后就能算出贡献。

那考虑如何计算这个 lcp，可以把所有点按字典序排序。

那就需要比较两个点的字典序。

首先每个点肯定不能直接维护这个 01 串，于是就可以差分后用主席树来维护这个 01 串。

那在比较两个点时就可以考虑找出 lcp，然后就能比较了。

找 lcp 可以线段树上二分，直接做是双 log 的。

可以单 log，考虑把所有节点拿出来然后统一做，用类似 SA 的过程来排序就是单 log。

day1.5

沈园太热了，变成科技馆和城市馆了。

不过科技馆有机械的小鱼，还有很多神奇机器，很有趣。

城市馆有一个鲁迅，竟然真的认识 dzd。

下午自习写了最近讲的题，好难！但是很有意思！

遇到了小猫，喂它牛奶，可爱。

gzy 哥哥和弗拉米亚哥哥也来了，gzy 哥哥被敲诈了一篇学习笔记，233。

晚上没有人聊天了，很压抑啊。

不太舒服的感觉。

day2

先读题。

A 是数据结构吧，B 计数，C 应该也是数据结构。

玩了一会 A 会了，写完发现被卡常了，卡了卡过了。

感觉 B 没什么思路就去看 C，得到了一个贪心的暴力，先写了。

常数很小于是 O(nq\log n) 过了 40，就去 B 了。

做了一段时间后并没有得到什么有价值的做法，16 分遗憾离场。

感觉这种状压的 DP 还是做少了，>=<。

查分没有挂分，ヽ(✿ﾟ▽ﾟ)ノ

下午进行了散步和寻觅虫子。

捡了好多好多虫子，但是遇到了一只还没有死掉的，然后被吓到了，吓得全部都扔掉了。

但是前几天单独捡到了一只，很漂亮的金色虫子。

晚上有 BNDS 群内聊天活动，见到利乐了，想你了牢乐。

A

找最靠前的 110 和判断有没有 101，线段树维护 lst-i。

只需要 1,2,3,4 即可，用 short 存。

卡常：不维护 lst-i，只关心翻转部分前两个后两个就够了。

B

考虑 P 和 Q 的交集，设其为 X，再对 P,Q 额外的部分容斥，设其分别为 Y,Z，之后对于这个做容斥。

可以改成分别枚举 X\cap Y,X\cap Z，设这两个分别为 S,T，那么对 X 的限制就是 X\in {S\cap T},并且后面的式子和 X 没有关系，X 的方案数就是 2^{|S\cap T|}。

\sum_S\sum_T (-1)^{|S|+|T|}2^{|S\cap T|}\prod {(1+a_i[S\in i]+a_i[T\in i])}

然后 2^{|S\cap T|} 可以拆成 2^{|S|+|T|-|S\cup T|}，这个式子就变成一个：

f_Sf_Tg_{S\cup T}

的形式，f 就是 \prod (a_i+1)，g 是负责把它容斥掉的，就是一个 \prod\frac{2a_i+1}{a_i+1} 的东西。

那在 a_i\ne -1 时，上面的东西就可以直接算。

当 a_i =-1 时，为了正确地把需要去掉的部分去掉，可以记录 S 中 a_i=-1 的数量，计这个值为 c_S，那么相当于再有一个 c_S=c_T=c_{S\cup T} 的限制，这样内部 a_i=-1 的部分就也是对的了。

day3

上午自习，gzy 哥哥来了，学会了如何科学的写一颗珂朵莉树，合理使用指针。

下午闭幕式，见到了 dzd 一个一个发奖牌的盛况，哇塞。

last

早上就收拾东西走了，拜拜绍兴一中。

路上听歌，阳炎好。

诶，其实还有很多内容没有写下来。

但是记不太清了，就一起写到最后了。

感觉龙山书院的天空真的好美啊，白天也是，晚上也是，傍晚和早晨。

但是好热啊，热的令人眩晕，这就是夏天啊，美丽的七月夏日气节。

记得有一天的自习教室外特别好。

有昏暗的天空，昏暗的云，和零散的电线。

天空的蓝色是那种浑浊的蓝色，但是很纯粹，就是有种雨后的感觉。

但是不是那种晶莹剔透的雨，是沉闷阴暗的潮湿感，有种让人喘不过气的压抑感。

晚上也有很多云，一点星星都没有。

啊，感觉冬天一直在期待夏天，却有些令人厌烦了啊。

与其说厌烦，更像是悲伤，非常悲伤。

一种夏日特有的忧愁笼罩着，连甲虫和蝉的泪水都干枯了。

嗯，在三楼有很多死掉的虫子，太热了。

但其实这种情况下，空调房里强劲的冷风反而就更好了，有种满溢的清凉感呐。

对，那天的天空就像漫画里一样，像夏天，炎热的夏天。

不记得哪天的中午了，好像中午躺在操场上，想欣赏一下天空。

但是好热，天空好亮啊，亮的人睁不开眼，亮的人无法直视美丽的天空了啊，实在是太闪耀了。

好奇怪，明明一直最期待的夏天，最喜欢的夏天，却连睁开眼直视天空都做不到，连仰起头都是如此困难。

太阳又是怎样呢，会不会感到孤独呢。

但是太阳的周围是有白云的，耀眼的白云，让天空更美了，也让眼睛更痛了。

闪亮的太阳云朵天空，炎热的夏日，干枯的虫子和空调的劲风，这就是 NOI 嘛，好厉害。

但是天空好遥远啊，越是追逐就越是遥远啊，向着天空伸出的手什么都碰不到。

阳光普照着大地，挥洒其光芒，令人憧憬，令人向往，令人心怀希望。

IA 酱好可爱，好可爱好可爱。

天上有小鸭子，金字塔，还有鸟巢。

是来的时候，坐飞机，飞机飞翔在云层之上，进入了云里面。

好厉害，好期待，云里面，云里面也太厉害了。

窗户都被云包裹了，白茫茫的，什么都看不到。出来之后显现的是碧蓝的深空之眼，与曼妙的云城。

但是飞机要落地的时候下雨了，一直在下雨，顺着窗户向后流去了。

飞的很低，可以看见灰蒙蒙的城市和天空阴暗的乌云。

太阳很亮，把天空照成了金色的，雨时的金色天空。

雨好大，但是没有伞。

即使没有伞，也要前行。

歩き出すのだ、傘がなくとも。

在高中楼的旁边有一个竹林庭院，旁边是一堆灌木丛，再旁边是网球场。

从网球场可以看到对面的公园和河流，之后是茫茫的树，层层的云，天空。

喜欢天空，喜欢云，喜欢夏天。

天空有一种很深很深的吸引力。

白云很美，和蓝色天空很搭，有云的天空总是美丽的。

令人着迷。

天空令人着迷，小水滴总在不停的上升着，朝着天空前进，向往天空，想要成为一朵白云。

无论是寒冷的冬天还是炎热的夏天，水蒸气总在上升，到天空中。

不过中国大多数的水还是在地上流淌。

水太多了，天空就变得拥挤了，就会有雨落下来，回到地面。

即使很多的水升到空中，天空却只有有限的空间，总会有雨落下来。

但还是喜欢天空，最喜欢天空，无论如何都总会向往天空，哪怕有困难、遇到挫折、都会向天空奔去。

炎热的夏风轻轻吹拂着大地，闪耀的云朵漂浮着向远方前行。却是无法追上，伸出双手只感到一阵炎热，看着云朵飘向远方，逐渐消失。

这样美丽的云，不知何时才能再见呢。