NOIP2021 游记

退役了啊!

Posted by ShanLunjiaJian's Blog on April 1, 2021

打完Day 1,晚上睡不太着,先写一下。

Day 0

跟sdfz的同志们坐高铁到了日照。

这是高二的学长们参加的最后一届NOIP了,他们几个都在切神仙题(NOIP前做静态Top tree+法法塔真的有帮助吗,zsy?),我呢在和小朋友们聊天。

发现kdw这一年进步好快啊!感觉已经吊打初三的我了,我被单调队列了/cy。码神kdw!

ljc在调他的Simplex来放松(这也叫放松?),我记得他从三月就开始调了,已经交了近两百发,还是97……好惨(

zhn说要我讲那个17年集训队论文里讲的SMAWK,结果我也不会(

21年联合省选前看过代替决策单调性分治的部分,还是很妙的!但是后面的部分符号太过恐怖看不懂了,然后就和小朋友们一起学了一下,拿来做了个诗人小G,感觉算是学会了?

做完了就到站了。然后去吃饭,吃完饭去宾馆,我和zkw分到了一间宿舍/jk

zkw初三就说上了高中要和我住在一间宿舍,幸而学校分配的比较随机。这次我算是难逃一劫♂了!然后zkw缠着我讲了几个分块题,说实话我也不会……一起学完之后就九点了,大家都洗洗睡了。

明天rp++!

Day 1

入场。感觉房间很熟悉,仔细想想发现跟去年是同一间。

先开……奥利奥!此时是8:30。

T1是个签到题,直接算就行了。最后15pts需要高精度,用了30min打完。此时是9:00。

T2怎么又是字符串?发现80pts就是一个SAM,最后20pts想了20min也没有想到。然后就用了30min去码。此时是10:00。

T3好像是数据结构,仔细看了看发现有一个显然的结论是从小到大放最优,然后要对于前面一段进行线段树二分,后面的可以ddp维护。可能有更简单的做法?也没多想,1h写完了并过了大样例。此时是11:00。(每题1h还挺准时)

然后就比较无聊了。T1造了几个大数据测试高精度,完全没问题。T3造了几个大数据试图卡自己,成功卡到了1.2s,不过时限是2s并且算法比较满,并不慌。

期望得分100+80+100=280pts,最差挂到85+50+80=215pts,SAM常数小可以拿到100+90+100=290pts。感觉Day2要出防AK题了!

upd: zsy说T2最后20pts,只要把SAM换成SA就可以卡过了,他当场写了SA-IS。zsy真是什么都会!他的估分是300pts。

kdw说有简单做法,他用了hash+BiT,完全可以跑过啊!那个BiT真是绝了。可惜他没想到T3的ddp,写了个根号重构,期望得分大概是100+100+80=280pts。被单调队列了啊!

感觉明天会被毒瘤至死。不管了,rp++!

Day 2

好家伙,真就是防AK场!

T1是个树上dp,不过1e7跑起来略显吃力,需要把树的dfn预处理出来进行转移,我造了几组数据都在1s以内。时限1.5s并不慌。不过这时候已经10:00了,只有两个小时开后面了?

T2看起来有个神仙结论!不过我没看出来。瞎猜了40pts部分分爬了。此时是10:40。

T3有点像一个做过的题?看了半天完全不会,打了20pts部分分。此时是11:20。

回去看T2,又想了半个小时还是没有结果。爆炸了。

期望得分100+40+20=160pts,那么期望总分是280+160=440pts。还可以啊?

zsy秒了T3!他说打个表可以发现对于一个$x$,只有$x\space\mathrm{xor}\space k$和$(x+m)\space\mathrm{xor}\space k$的值$\mathrm{popcnt}$都是奇数的时候才有贡献,然后这个贡献是一个关于$\mathrm{popcnt}$和$x$的二元$2n-1$次多项式,所以爆搜一些,高消插出来然后拆开各项数位dp就好了。码王zsy只写了120lines。这样看来他的期望得分是100+40+100=240pts,总分540pts。zsy yyds!

T2我们好像都不是很会。睡觉了。

upd: zrz打的T2随机调整,被我们证明了得分期望80pts!zrz的总分大概是100+100+60+100+80+60=500pts,好强啊!

Day 5

ccf神速?大家好像都挂了点分。

我 : 100+65+100+95+40+20=420

zsy : 100+90+100+90+40+95=515

zrz : 100+95+60+85+70+60=470

ljc : 100+80+85+95+45+20=425

kdw : 100+100+80+90+40+60=470

感觉退役了……sd rk114……不过压线1=了(

免责声明

这是愚人节玩笑,请不要当真。谢谢朋友们!!1

(这场得分好像有点高……主要是因为需要瞎编这些题的算法,就需要有人打很高的分,但是又不能大家都阿克……