惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

Engineering at Meta
Engineering at Meta
奇客Solidot–传递最新科技情报
奇客Solidot–传递最新科技情报
腾讯CDC
宝玉的分享
宝玉的分享
量子位
Recent Announcements
Recent Announcements
Martin Fowler
Martin Fowler
J
Java Code Geeks
V
Visual Studio Blog
阮一峰的网络日志
阮一峰的网络日志
Blog — PlanetScale
Blog — PlanetScale
大猫的无限游戏
大猫的无限游戏
博客园 - 叶小钗
S
SegmentFault 最新的问题
B
Blog
freeCodeCamp Programming Tutorials: Python, JavaScript, Git & More
博客园 - 【当耐特】
小众软件
小众软件
The Cloudflare Blog
Y
Y Combinator Blog
I
InfoQ
OSCHINA 社区最新新闻
OSCHINA 社区最新新闻
GbyAI
GbyAI
IT之家
IT之家

博客园 - nealchen

无需 Path Measure,也能轻松推出 Diffusion ELBO 🌊 LangFlow: 连续扩散语言模型,首次匹敌离散 CTMC ELBO 的另一个证明 【Remix】拆解 DDIM 论文【扩散模型加速采样】 CCSP2021游记 二元多项式求逆中的小坑 [ZJOI2020]字符串 Ubuntu 20.04 工作区小记 2020省选犯傻记 AtCoder tokiomarine2020 题解 [CF1336E]Chiori and Doll Picking [JOISC2020]遗迹 积性函数求和:构造狄利克雷卷积将值域限定于powerful number [UR19B]通用测评号 另解 积性函数求和:筛法DP、洲阁筛、Min_25筛 最大权完美匹配:KM算法的优化 代数余子式和伴随矩阵 生成树计数:矩阵树定理 [AGC024F]Simple Subsequence Problem 区间最值问题(RMQ):压位分块稀疏表
NOI2020乱搞记
nealchen · 2020-09-01 · via 博客园 - nealchen

比赛

笔试和试机

试机发现本机开O2优化每秒可以跑40亿计算量。

第一试

入场开T1,觉得是个矩阵模型。怀疑过不去,打算打表找规律。发现即使没有开O2,随机数据打表只用了0.5s。想起来了,这可是40亿神机!于是直接写上去,稍微调一调就过了。然后写了点儿对拍。此时时间过去了两小时。

接着开T2,容斥一下是个线段树合并优化DP的模型。后来听说不用容斥地做法跑得更快。写了下,有个技术难点是怎么合并叶子和非叶子节点,想了想感觉挺对就蒙上去了。稍微调一调就过了。然后写了点儿对拍。此时时间过去了四小时。

最后看到T3,尼玛,这一场里两道DS是人干的事情啊?!这题还不弱于区间逆序对?!果断弃疗写平方log暴力+A档莫队+C档数点,预计得分52分。在比赛的最后一个小时,我感觉到的竟然不是紧张。困倦铺天盖地袭来,每写一个模块就得趴桌休息一分钟。

下午出成绩,进去查收了一下,没挂分。Lagoon的T3写了个1.75方的四维莫队,由于B档数据太水,连过76分,总分276,太强了。

第二试

入场开T1,发现不会做。看T2,发现看不懂。于是先分析出T1的配对关系构成一棵树,然后对着T1的样例2找一下规律,发现是最小的和最大的相配。对着样例3发现好像树的情况一定有解,证一下发现确实。然后就是常规的压位背包了。此时时间已经过半。不过我们教练给我们打了预防针,说D2很可能会难,于是我感觉自己节奏勉强能撑住。

然后看T2,分析了一下感觉像是,如果有单点一定行,不然以两层高的情况为模板的三类树,一定是能够几乎被全部表示的。然后想了想不断往下分的做法,发现情况多得根本讨论不完,隐隐约约感觉它还漏掉了情况。冷静一下,发现确实漏情况了!做法改改改,一看,居然还变简单了!做法好像是m*maxh的,预计得分56分。此时比赛最后剩余半小时。

然后看T3,绕到完美消除序列上兜了一大圈,发现自己不懂得怎么求完美消除序列!于是只好看到B档部分分,看上去就是个轮廓线,写太急假了,无解都忘记输出。

出场后我直呼失误。结果Lagoon的预计得分比我还低。问了一圈发现都比我低?!Lagoon说他最后一小时发现自己T2做法假了。于是我怀疑我T2做法也是假的,跟他讲了讲我的做法。他挑不出毛病,顺便帮我一分析,这个做法复杂度是 $O(n)$ 的,直接就A了。

下午出成绩,无限拖延……最后紧张感都消失了。进场一开成绩单,看到T2,A了,总分两百。当场拍桌起立,感觉自己分数挺高的。

赛后

大家都奶我前十,于是毒奶了。最终排行第13,应该是个人最佳成绩。后来就是找THU填保送协议什么的。

颁奖的时候大概在倒数第二批,和两位国家队员,还有EricHuang2003, peehs_moorhsum,zx2003等大佬同框领奖了。

交友

为了放松心情,我参照了之前IOI的一篇报道,说CCF让我们的国家队出去带点儿礼物,别聊谁的分数高,比谁交的朋友多。于是从赛前到赛后就疯狂找OI圈子名人面基。

16日一入住,就去敲了jiangly宿舍的门。一开门,他直接就和我打招呼,我连自我介绍都忘了说,只说,“久仰久仰”,就告辞了,场面十分尴尬。他个子高,相当英俊。

17日开幕式认识了EntropyIncreaser,他个子不高,披散着头发,是高冷数学家的外貌。不过EI是很热心的,经常会为粉丝解答问题。

18日考完碰见了djq_cpp和little_waxberry,跟他们稍微聊了聊做法。

19日考场座位左边是peehs_moorhsum。大家都散了,就他第一时间通知了出成绩的消息。这么有耐心,可能这就是IMO大神的境界吧?他还提出来帮我查分,受宠若惊。

总结

NOI2020的题目是比较反常的,好些选手给折腾翻车了。得益于我们学校这种稳扎稳打的风格,即使是让教练最头疼的我,也保住了绝大部分分数,感觉再能提的,也就是D2T3的B档部分分了。

貌似保送THU好像已经把高中的流程刷到尾声了。但是好像也还是刚刚开始,还打算打一打MO,也要准备OI的后续赛事,更别提还得学一点儿大学的内容……能做的事儿多了去了。