NOI 2025 游记

· · 生活·游记

UNR 之前

都在摆烂，感觉没怎么做题……

UOJ 笔试

忘记打了。

UOJ Day 1

T1 没太敢想，开始写的时候已经来不及了，T2 也只会平方，没有进一步简化结构。

UOJ Day 2

T1 推了好久还是不会，寄了。

感觉虽然两个 T1 都比去年难不少，但是一题不会是不是烂完了？但好像我还是保持很无所谓的心态，相信就完事了。

提前一天到绍兴，得知考场竟然不在校内（CSP 300pts 没去 WC），感觉无敌了。

报道日

换徽章，欸我怎么只带了十个徽章，欸我怎么忘记免费额度了。

尝试写 2.48sOI Round 1 T4 的根号的做法，感觉在线会被卡空间，然后摆了。

Day 0

很好的开幕式！节目和 dzd 演讲都很有意思。

打扮一下吧（笑声）。 尊敬的顾建主席、孙军市长、各位导师、专家、孩子们： 我们又见面了。我到绍兴不知道有多少次了，其中有一个原因就是和奥赛有关。昨天有人问我：“杜主席啊，为什么绍兴一中第三次获得了承办权？”我说，原因很多。除了他们学校具有完全适合竞赛的场地和设备之外，还有一个重要的原因，就像刚才丁书记所讲的，他们在30多年、将近40年的时间里一直不停地在普及计算机科学技术，有很好的基础。所以呢，培养了许多优秀的学生，获奖也是一个证明。另外呢，他们的老师也坚持在第一线，不但自己做得好，还在额外的社区做贡献，也帮助别的学校的发展。 其实还有一个原因是别的学校不具备的，是因为绍兴一中原来的名称叫“绍兴府学堂”，是蔡元培和鲁迅两位执教的地方。这个对他们学校非常重要，对我们也非常重要，对我也非常重要。 我认识鲁迅比较早了（笑声、掌声）。在文$ $革期间，我念初中，一不小心在图书馆里发现了一本书叫《鲁迅传》，我看了以后感觉挺好。后来就攒钱，每攒到两三毛钱，就到县里的新华书店买一本翻新的。那会儿的书比较便宜，从《呐喊》开始，后来到了高中也陆续买，比如《野草》《朝花夕拾》《且介亭杂文》《二心集》等等。到了大学我还继续买，后来一直把鲁迅的《两地书》都买完了。到我工作的时候，研究生毕业第一个月，我就拿工资买了一套《鲁迅全集》精装本，50块钱。当然，这时候我已经把鲁迅的书基本都看完了。这些书籍的价值并不是当装饰，而是用来看。就前几天，我还在看鲁迅的《故乡》《藤野先生》《祝福》《狂人日记》。因为几十年过去了，我觉得鲁迅就没有离开我，他的精神在我心里，还影响着我。 鲁迅的文字是骏跃的、俏皮的，甚至有点儿带讽刺挖苦，但他所揭示的道理是很深刻的。他揭示了我们中国国民性里头卑劣的一面、可怜的一面。你看看祥林嫂、华老栓、孔乙己，当然还有阿Q。100多年过去了，我们想想身边还有没有阿Q？我认为是有的，而且大有人在。 鲁迅最初是学工的，从学矿到学水师，后来到了日本学医。但他发现中国人被绑去砍头时，旁边看热闹的中国人却无动于衷。他觉得，中国人的身体无论如何康健，如果没有精神的觉醒，那也没用。于是他毅然决然弃医从文，用文字来影响国民。这也是我从他的文字里感受到的。 但是光有国民的觉悟，我觉得还不够，况且也很难。当然，鲁迅是影响了一批人。我认为制度也很重要，制度是一群先人构建的，制度会塑造人。美国成立到现在也就200多年，1787年，那时候清朝已经有了100多年。可是美国就这么厉害，不管他多么恶霸、多么不讲道理，但他就是厉害。为什么？是制度好。所以制度也非常……（被打断，掌声） 蔡元培是在清朝时考取了进士，后来是翰林编修，但他没去当$ $官。他参加戊戌变$ $法，跟孙中山一起投身中国革$ $命。失败后，他到德国和法国留$ $学，前后共有7年时间。回国后，他在北$ $洋政$ $府任教育总长，后来任北京大学校长。他在北京大学开启了现代教育的先河，建立了一个非常好的制度。他说：“大学是做学问的地方，而不是培养那些只想做$ $官和想挣大钱的人的地方。”所以蔡元培的影响力还在。我们绍兴也有元培学校，北京大学也有元培学院。这两位是非常了不起的。蔡元培的自述、他的论述我也看过好几本。今年《蔡元培全集》出版了，但我现在还没买到。所以呢，我想这两位曾经影响过绍兴一中——也就是绍兴府中学堂。 我刚才说的制度，制度非常重要。我们不光是每个人要好，还要尽力改变一些不合理的制度。想想我们NOI在2001年时没人愿意办，我要到处求人家办，给人家钱。为什么？制度不好。每年每个省只有三个学生的名额。现在你看看我们有多少学生？我们除了每个省市有基本的公平的5个选手之外，像浙江这种优秀的省是可以获得多达12名的奖励学生，但这些优秀的学生不会抢占那5名选手的奖项机会。这是我们制度设计得好，所以我们在国际竞赛中屡屡获奖。即使CCF从来不培训学生，都是我们中学的老师在培训。为什么能到现在这样？就是制度好。 当然，鲁迅的精神也在影响我们：人要有骨气，不能像阿Q那样。当北京女子师范大学的刘和珍等6个人被北洋政$ $府枪杀后，鲁迅写了一篇《记念刘和珍君》。他去纪念这6个被枪杀的学生，而他自己也可能被杀，所以他把钥匙留在邻居家里，说：“我今天可能就回不来了。”应该有这样的胆识和勇气。我不像鲁迅先生那样，但我作为你们的主$ $席，也应该行得正。 2021年疫情期间，NOI在浙江省余姚中学举办，正赶上台风。上面打电话来说：“子德，别办了，为了孩子们的安全。”我说：“我知道。”当地的市长也让余姚中学别办，说：“出了问题谁负责？”我说：“我负责。”余姚中学的赵校长也不干，说：“你把我校长免了可以，但必须办。”我们不是蛮干，提前一天让学生到校。我相信台风也不是刚发明的，过去几千年、几万年都有，而且宁波也不是刚有的。如果台风就把宁波灭了，那它早就绝种了（笑声）。如果台风不会把房顶吹倒，那它也不会把我们的学生推倒。结果整个竞赛非常成功，但校长可能要冒被撤职的危险，我杜子德主席也有当不成的危险。可是，我们要敢于担当。 孩子们，你们知道吗？我们现在上面给了50个保送名额，但其实原来只有40个。其他四项竞赛是50个，只有我们40个。为什么？因为我们课堂上没有计算机科学的课程，所以给我们少。我们参加的人数也比不上数理化。我在中国科协和他们争辩，我说：“你们这是歧视，你们对计算机科学教育不重视。况且我们在课堂上没有，应该加强才对。如果你们这样做，我明天开新闻发布会，让全国人民知道你们干的臭事儿（笑声、鼓掌声）。”当时领导说：“子德，别发火，咱们好商量。”过了一个月后，他们回复：“一个学科50名，咱们和他们一样。”我不是嫌少，我是嫌不公平。五个学科，五五二百五，说‘二百五’太难听了，那260吧。那10个给谁了？咱们商量商量，说数学人多，给数学吧。”我妥协了一点。所以到现在，数学60个，我们其他四项都是50个。 还有很多例子，我今天时间有限，不能都给你们举。我说，人要有骨气，没有骨气就枉为人了。中国人也要有骨气。所以同学们，你们看到我们每次举办竞赛挺喜气洋洋的，我们是希望你们喜气洋洋，但背后有许多艰难的事你们都不知道。我们让你来，是看你的智力怎么样、解决问题的能力怎么样，就看你的程序。但我们对学生的品行也非常关心。 最近有一个浙江的学生，因为没进省队，第二试没提交好，得了0分，非常沮丧，给我写了很多信，说：“杜主席，能不能给我个名额？”但我不能说：“你少来这一套，没有。”我给他写了一封长信。我不认识这个学生。过了几天他又写来，说：“我觉得这一生就完了，前途就黑暗了。”又写了很长一封，我又回了一封长信。过了一个多礼拜，他回复说：“杜老师，我想通了，我继续好好学习。”一个不认识的学生，我花了这么多时间。我非常关心我们每一个学生的成长。 还有，我们要守约。你们也知道，去年我们在埃及有个学生栽了，没遵守规则，把手机带去了（笑声）。所以同学们一定要守契约、守规则，不要因为警察不在就闯红灯，一定要按规则来办。还要讲礼仪，见了面假装不认识，我觉得不对。我们还有要求：吃饭一定要把盘子吃得光光的，盘子里有剩的就扣1分，我们有人在值班检查。你没有权利浪费，吃多少都没关系。我不是想折磨你们，是希望习惯从小养起。我就是这么被培养起来的——如果我妈妈看到我剩饭，耳光就过来了，所以变成了习惯。 所以孩子们，我愿意和你们在一起，希望你们放松竞赛，把所有的能力都展示出来。刚才董事长跟我说：“你看那孩子不能放松。”你们要放松，不要紧张。 愿你们考得好！谢谢！

试机，因为学校键盘比较平，不是这种比较凹进去的样子，所以赶紧多打一打，在笔试之前敲完了 NOIPT2T4，键盘终于趁手了。

考号是 SH-29。

笔试过了。

突然想到可以测测速度：

const int N=1e8;
int a=1,p=114514,q=1919810,r=998244353;
for(int i=0;i<N;i++) a=((LL)a*p+q)%r;

konyakest 将 int 之前还得加了个单词，导致不会被 -O2 优化掉。。。然后你告诉我这玩意要跑 0.8s？

事后还有一个人和我说，4e6 的 bit，4e6 次修改和查询要跑 1s，真慢完了。

虽然 r 不是常量，但是这是不是也太慢了，感觉和去年完全不在一个水平。（flag）

进行了一些 MC，感觉不是很好玩，就不写了。

Day 1

睡得不算很好也不算很差，和省选一样靠着某饮料打起精神。

座位号是 A006，感觉无敌了。

开题，你告诉我这啥？

好像一上来状态不大对头，正好靠这个题起起状态，我感觉我大概出了五六个错，半小时才过。

感觉 T2T3 都不会，先开 T2，首先会一个高次 poly 复杂度的算最大值的区间 dp 算法。

区间 dp 一般没有前途，还是得老老实实分析操作的结构，发现如果去掉 a_j=0 的无效操作，然后连边 j\leftarrow i，发现一个弱连通块的结构一定是 j_1\leftarrow j_2\leftarrow\dots j_J\leftarrow i\rightarrow k_1\rightarrow k_2\rightarrow\dots k_K。那么就可以一段一段序列 dp 了，先不考虑计数部分会算重的情况，那么就能 \mathcal{O}(n^3)。二分+排序的话是 \mathcal{O}(n^2\log n)。

然后发现优化到 \mathcal{O}(n^2) 只要动态维护有序序列就可以了，每次的流程是：

合并的时候双指针即可，这样就过了最大值。

然后发现只会在 a_i=0 的段计算重复，类似 CSP 消消乐平方做法，发现所有这样的段不然能由几个极小的段求不交并得出，那么只转移极小的这样的段即可。

过题是 2h，考虑到

你应该做好你需要拿到当天比赛几乎满分的心理准备（NOI 2014，NOI 2015，NOI 2021）。

所以开始严肃对待 T3。我从始至终没想过并查集，而是把它当作一个数学题，慢慢推，慢慢证明，最终修对了结论，然后获得一个依赖集合哈希的 nH 做法，获得 80pts。这个时候时间其实已经只有一小时不到了。

然后发现可以转化为：

可以整体二分做到 2log，最后半小时开冲，获得了一个 2e5 log 2e5 log 8e5 的实现，其中 log 8e5 是排序/树状数组，然后这玩意只能跑 88 pts，真的是慢疯了，也来不及卡常了，就这样了。

出来感觉无敌了，结果发现一堆 280，都是并查集，所以

为什么这玩意要跑 20s？ 为什么这玩意要跑 20s？ 为什么这玩意要跑 20s？ 为什么这玩意要跑 20s？ 为什么这玩意要跑 20s？ 为什么这玩意要跑 20s？ 为什么这玩意要跑 20s？ 为什么这玩意要跑 20s？ 为什么这玩意要跑 20s？ 为什么这玩意要跑 20s？

为什么 2 log 只给 8 pts？为什么 2 log 只给 8 pts？为什么 2 log 只给 8 pts？为什么 2 log 只给 8 pts？为什么 2 log 只给 8 pts？为什么 2 log 只给 8 pts？为什么 2 log 只给 8 pts？为什么 2 log 只给 8 pts？为什么 2 log 只给 8 pts？为什么 2 log 只给 8 pts？

为什么 \mathcal{O}(nH) 给 80 pts？为什么 \mathcal{O}(nH) 给 80 pts？为什么 \mathcal{O}(nH) 给 80 pts？为什么 \mathcal{O}(nH) 给 80 pts？为什么 \mathcal{O}(nH) 给 80 pts？为什么 \mathcal{O}(nH) 给 80 pts？为什么 \mathcal{O}(nH) 给 80 pts？为什么 \mathcal{O}(nH) 给 80 pts？为什么 \mathcal{O}(nH) 给 80 pts？为什么 \mathcal{O}(nH) 给 80 pts？

不知道在玩什么原神。

讲题还忘听了，在打 MC。

晚上有小龙虾！但是好像没反应过来所以第一时间没拿。吃饭看到帆队吃了一大盘小龙虾，才想起来能这么完，最后就拿了两勺吃吃看，感觉很不错。

Day 1.5

dzd 说要在室内，就参加了科技馆和一个忘了什么馆，科技馆有很多好玩的，很不错，忘了什么馆没有讲解，纯逛街，时间不剩多少了所以部队走得很快，啥也没看进去。

下午看电影，然后莫名其妙放不了，还操作了一些莫名其妙的文件，什么数学竞赛/高一物理竞赛/三角函数啥的，然后还放默剧没声音，然后放了好一会儿了灯才关……

《人生大事》，我和 lhc 查了一下评分，感觉还挺靠谱……吗？

离了个大谱，你告诉我这啥？槽点太多就不说了，这能豆瓣 7.3 的，无敌了。

不过整个过程还是很趣味的，和 lhc 一起吐槽，场馆内也没什么人走，都看完了。

Day 2

状态比第一天还差，还是靠饮料。

座位号是类似于 A003 一样的东西，感觉更无敌了。

开题，发现 T1 是模拟赛喜欢放的狗屎型 T1，有点慌，这种题就是随机硬控你相当长一段时间，你知道足够多的时间你一定能过，但就是不知道会耗你多久。

先读了个看 T2，发现是 \mathcal{\widetilde{O}}(2^n)，说实话这种题做了很多，但是自己能做出来的其实不多，不知道该不该慌。

T3 太长先不看。

然后开始大战 T1，先写了个暴力，一通推导猜出了结论，然后平方过了，接下来就是改线段树了，状态不是很好错了一点地方，1h40min过了，还行，SelfEval 说我最后一个点要跑 1.5s，我测了下极限数据（每次翻转区间 [2,n-1]），发现要 2.1~2.2s，真的是慢疯了，但是感觉时间不是很多就先没管这个没底的5pts，而且感觉应该也不可能故意卡我时间。

做 T2，感觉状态很好，做起来也很果断，直接弄了两层容斥，然后推出来了个 B 性质的式子，写了个 \mathcal{O}(5^n) 直接计算，改了一会儿中间还唐了好多下，然后改 \mathcal{O}(n2^n)，过了 B 性质。

然后尝试将数扩域成 x\times 0^y 的形式，但是发现直接合并取 y 最小值的时候可能会吃掉 y 较大的部分，你把 1\times 0^1+2\times 0^2 合并成 (1+0\times 2)\times 0^1=1\times 0^1，那如果除以一个 0^2 你不是那个 2 直接被吞掉了吗？

但是一想发现不对啊，它不可能除以零的，只要保留 y 最小的那些就可以了，只有那些可能除完 0 因子，如果这些东西都除不完 0 因子，那其他也不可能除完 0 因子。

那不是完事了？改了一会儿中间还唐了好多下，总算是过了，最慢点 < 0.9s，终于不卡常了！

然后发现又用了 1h40min，就相当于我三个题各用了 1h40min，还挺巧。

然后 T3，本来以为直接贪心得用 1 就行了结果假了一发，然后老实了写了个 \mathcal{O}(Qn^2\log n)。

感觉 dp 值是 1 的是一段区间，打了个表发现还真是，\mathcal{O}(Qnlog n)。

然后不会了，愣了一会儿，单点修改，这不是感觉答案变化量是 \mathcal{O}(1) 的吗，简单看了下大样例发现挺对，\mathcal{O}(Qn)。

40pts，最后 20min 尝试编特殊性质做法未遂。

T1 果然没被卡，还是 1.5s 左右。

听讲题发现是数据结构优化狗屎贪心（贪心我也没咋听懂），特殊性质只是有些数据结构能换成暴力，那不是感觉会了也来不及拿更多分了，那还行。

wmh 还发表了好写的复杂度不带 3 的高妙做法，也没听懂。

100+100+100+88+100+100+40

篝火晚会还是很有意思的，气氛很好，还有一些我似乎完全不会的大众歌曲，蚌蚌。

疏散日

午饭又有小龙虾！不过这次由于一些原因（好像是去太晚了，怕赶不上闭幕式）好像来不及吃很多，不过也吃了相当一大盘，爽！

今年徽章带少了，还忘订了免费额度，所以没有换到很多徽章，还有一些只拿了别人的没给人家（）。