NOI2021打铁记

本文主要是介绍NOI2021打铁记，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

由于我太菜了，没能去现场，打的是网络同步赛。

Day 1

从8:30等到10:00，不得不说还是很焦心啊。到了时间后，又有浏览器上不了网站，题面下载莫名其妙要下20分钟之类的奇怪问题，等我真正开始做可能已经过了20多分钟了吧。

开始看题。首先把题目同看了一遍，没什么思路，不过感觉T1最可做，T2,T3都有些神仙。

然后仔细想象T1，过了10分钟左右想到了树链剖分+线段树的做法，令人热血沸腾。不过吸取了之前的教训，又思考了一下这个做法的正确性以及实现细节，然后就开始码了。稍微调了一下（好像是因为多测没清空），在11:40左右通过了大样例，也懒得卡常了。

开始看T2。考虑到不相交路径我联想到了LGV引理，不过我似乎学了个假的LGV引理，以为它不能解决这类问题，就把这个想法放下了。然后考虑k=2的部分分，容易发现此时交点个数就是逆序对数，于是可以糊出一个状压dp，稍微拓展一下就可以得到40分。感觉会比较好写，就先去想最后一道题了。

T3的话原图有一个神仙的性质：\(x\Rightarrow y且z\Rightarrow y\Leftrightarrow x\Rightarrow z或y\Rightarrow z\) 。不知道该怎么用，纠结了好一会。后来放弃，开始想部分分。首先感觉\(\mathcal O(n^2)\) 的做法十分trivial，然后\(m=n-1\) 相当于外向树，感觉也会比较好做。至于一般图，可以想到先缩点，然后就。。。

这个时候已经是13:30了，便开始码了。T2的dp非常好写，写了30min没有调就可以通过部分分了。之后写了T3的部分分，不过到最后的时候没有调出来外向树\(k=1,2\) 的部分。

预估分：100+40+36=176.下来测了一下一分都没有挂，非常好！

Day 1感觉状态不错，估计是在家里心态比较放松，没有之前考试那么紧张，把自己应有的水平发挥出来了吧。同时吸取之前的教训通读题目，想好了再写代码，不过分纠结于一道题，合理分配时间这些要素应该也是原因吧。不过这次考试也暴露出一些问题，例如对知识点掌握不牢（不过LGV引理这种东西也没怎么考过嘛），思考的条理性不足（主要体现在T3中\(k=1,2\) 的讨论上）。希望之后能改善。

这篇关于NOI2021打铁记的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！