首页 > 技术文章 > 记 NOIP2021

int-2147483648 2021-12-20 19:06 原文

Day 0

没印象了

Day 1

好像一大早(六七点的样子)就往南门走了。天还没全亮,好久没有那么早起过床了。
以为自己要迟到了 所以扫了个车子rush出去,然后在超市飞速的买了个士力架+一瓶饮料。
结果大巴来晚了,和何了等车等了好久。
饮料路上喝完了。

路上发现没带准考证,王士诚也不在学校,给他发了电子版让他路上遇到打印店帮忙打印一下。
后来周杰沟通了一下,说电子版也可以。
最后总之是正常进考场了。

T1看了看,暴力预处理一下大概就能过。复杂度不会证 但是是低于 \(O(n\ln n)\) 的, \(n\leq 10^7\) , 1秒, O2。
感觉能过 写了写 极限数据1.9s,研究了一下 手动开个O2,1.2秒。感觉可以了 下一题。
T2感觉题意不好理解,想了想暴力发现复杂度起飞,一分没有。回忆起CSP的经历,果断下一题。
T3题意好理解,忘了刚开始什么思路了,大概想了30min。后来发现差分一下,操作就变成交换差分数组相邻两项了,于是题意变为“重排差分数组使得原数组方差最小”(差分数组各项非负)。然后感性理解了一下,差分数组应该在某个位置前单调不升,之后单调不降。试图证明,最后没证出来,但一看没时间了,只能硬着头皮写了。写完以后不过样例,发现输出比答案小所以调了好久,最后发现输出比答案大了 就不确定是代码问题还是算法问题了,又调了调调不出来 一看没时间了 就敢不调了。
T4一看题面巨长,简单读了读 感觉不可做,又回去想T2。
时间问题T2直接去想了部分分,没想正解(后来发现可能正解反而更简单)。然后部分分也没搞出来。
觉得T3算法不靠谱,跑去打了个T3的20分暴力。
然后觉得没事干了 趴着睡了十几分钟。
醒了以后又检查了一下T1,加了个小判断,极限数据直接0.7s。
静下心来仔细读了读T4,读完以后发现脑子里的第一想法“离线 倒序 然后并查集”就有36分,然后还有个特殊性质白给12分。看了看时间 不太够写带并查集的48分算法,决定写24+12=36的。结果由于把三种方式的答案算重复了,加上最后5分钟过于紧张,没调出来。

最后期望得分:100+0+20+0=120,但考虑到ccf数据水,期望得分:100+0+50+5

出考场发现T3算法是正解,看来是代码有小瑕疵。不过至今没去看那份代码bug在哪。

实际得分:100+0+64+0=164,应该是省一了。


哈哈,但唯一算数的省一可能就要没了。

推荐阅读