NOI2021 真·爆炸记

· · 个人记录

(标题一开始打错了,悲)

Day 1

九点开始考,然后开始后好几分钟才知道解压密码。

先看一遍题。

T1:卧槽不会是LCT吧,不是说不考吗,我完全不会啊

T2:阴间题(一开始题面还出锅了)

T3:看起来挺阳间

然后T1是真的不会,既然不是LCT那肯定要树剖(来维护链),然而没想出来

然后开始分析T2。

首先想到一个显然过不了的状压,然后分析了一下发现答案相当于每一层(偶-奇)乘起来,于是搞了一个可以做40pts的状压,然后继续分析,得到一个显然没用的结论(完全二分图一定答案为0)

然后上厕所,顺便思考一下T3

回来之后推了一下T3的条件

若x=>z且y=>z 则x=>y或y=>x

我发现能到达z的点中,肯定有一个点能到达其他所有点,进一步,整个图中有一个点可以到达所有点(缩点后),然后删去这个点后剩下的几个连通块也是这样,最终可以形成一个外向树,那么后面的部分就和树一样了。那么k=1可以稍微讨论一下,k=2好像是大讨论。

(然后我还想了一下怎么实现,发现问题不大)

此时过去了两个多小时,我一B的代码都没写,于是开始写T1暴力。

然后就崩了

T1先写30pts暴力,发现键盘特别阴间(我按delete的时候全按到printscreen上,然后delete的位置特别奇怪)。写完了暴力发现样例2过不了,有一些数比答案小1,调了一个多小时(心态逐渐爆炸),发现还是不知道挂哪了,于是换一种方法写了暴力,过了样例。

此时还剩一个半小时左右,开始写其他两题暴力,T3暴力挺好写。

然后考虑写什么:T1链部分分(线段树我肯定不想写,容易写挂),T2状压,T2网络流,T3树,T3 后面部分(需要Tarjan,显然写不完)

然后先写T2状压,写完之后就一直调到13:55,(13:40时心跳逐渐加速)终于过了样例2。

然后试图写T3 树 k=0的部分,然而没写完。

最后如果没挂的话就是30+40+28=98 显然烂爆了,比我能想出来的分少了20+15+40(马上要出分了,危,不会挂分吧)

更新:出分了,40+40+28=108 /kk

(显然就我没想到行列式,我是傻逼)

Day 2

没啥会的

T1有想到要分成16段,不过当时陷入trie树的思维定势所以没想到正解

T2我看到斐波那契感觉是要矩阵但是没想到矩阵要维护什么(后来发现维护分子和分母就行了)

然后写暴力,T3调了半天后两个样例过不去,最后T2 15pts部分分也没写。

最后 36+20+16=72,出来之后lhx (@FunnyCreatress)跟我说他T1会80分的做法,我一看和我做法几乎一样,然后我告诉他你这复杂度不对,然后果然他只比我高4分。

\color{white} 考完估分 180,结果被神 FunnyCreatress fAKe了,出分的时候发现他只比Ag线少两分艹。我直接膜爆 SH 副队长 \%\%\%

不算笔试180pts 成功获得Cu /kk

后续计划

高二大概要摸文化课,然后要留些时间做有趣的事\color{white}拍手游戏等等

OI的话,有空打打CF,然后做些难题。暂时没什么完整的计划。