0%

2024 Nowcoder Round 5 Replay

对,但是不对,但是

wdy

这把应该算顺场,虽然犯了大大小小的病但是n+2了,爽

上来看M糊了个结论,后来被锤为假,爆笑,,然后这时候榜开始有动作了,迅速先跟着签到一波,[deleted]H题捣腾半天tm是个爆搜证明复杂度,出题人肯定认为自己很聪明吧。差不多同时蒋老师开始了和幽默A题旷日持久的世纪大战,最终在若干次您的提交未通过所有测试样例后光荣retreattttt,事后发现这吊题暗藏玄鸡,行吧我认为你这出题的有点水平,,骗了一场的人hh。再看,蒋老师挑了个G,我挑了个J,董老师搞FK,历经苦难GJ都过了,J因为cin>>n>>d>>k写成cin>>n>>k>>d被硬控盯着ac代码看了1h+,或成今日最大笑料,,,,。然后FK都看起来很有说法,我力挺搞F若至K题没搞头队友表示赞同,董老师说现在最大困难是构造无平方串的串,写了个暴力能搜出来个10000的,但是看不出规律。我在一边胡思乱想,蒋老师尝试理性构造。我突然觉得,100000多搜一会,跑个十分钟半小时应该能搜出来一个,然后压三位大概33k应该能放进代码里面,这不就解决最大困难了hh。跟队友说了他俩说可以试试,没想到100000搜了一两分钟就搜出来了还真有搞头,赶紧跟之前的做法拼起来结果压哨过了hh,奇技淫巧高光时刻,,爆笑/////

完事后发现kfc老爷爷他们队过了k,研究发现我们的四维dp状态可以少一个压成三维的,然后根据决策单调性就能均摊O(1)转移了,也是差点就出来了。。说不定我J不下饭省下来时间去跟董老师一起搞一会儿能再把这题搞出来的

dhj

4h 59m 47s 极限过题,n+2了,爽。

这场就是三个集训队4题的那一场,果然很难,中间卡题纯纯折磨。

刚开始的时候跟榜签到,我把L过了,jby写了一个少一种情况的B,wdy把E过了,我和jby在下面把B补完了,然后B也过了。之后我和wdy开始看H,jby说会了A,他就上机写,我和wdy想了各种meet in middle啥的做法,最后感觉还是爆搜比较靠谱,等jby写完A测了测发现WA了之后我就上去写了个爆搜,写完后写了一下gen,测了测时间感觉很健康。

然后就开始卡题时间,先是jby想了几个A的修,但是都没通过,然后由于A题0/200,就先战略性放弃A。我上机把wdy推出来的M的式子实现了一下,然后发现样例过不去,我口了一下做法的问题,就扔给wdy了。我先是看了J,我瞎写了点东西,wdy也写了点东西,然后wdy说他会了,看着也挺合理的,就让他上机写,写了很久。我在下面看题,看了看M写了点式子,问了队友说没机会,看了看F盲猜了一点结论,然后后面拼一个暴力看着挺有希望的,看了看G之后把这题扔给比较会这类题的jby,他很快也想懂了,wdy还在机上的时候把实现思路整理了一下,等wdy开始调了就上机写,最后用lct实现了一个,挂了一次之后就也过了。jby写的时候我和wdy讨论了一下K,我写了一个dp转移式子,感觉非常正确,但是状态空间是 \(O(n^2\log^2n)\) 的,虽然转移可以大概做到 \(O(1)\),但是还是很危。

jby下机后我写了个F的暴力,写了个暴力手动对了一下拍然后发现前面构造要上个背包,写好背包后交了一下,先是MLE,然后WA,发现末尾的结论有问题,然后和队友讲了一声后开始修。wdy和jby在看J,看了半天读入顺序搞错了,改了后就过了,第一版代码就是对的,因为读入顺序虚空调试卡了一年,长个教训,下次记得检查读入。然后我们在KF中选了F all in,想了正经方法没用后,最后打了一个表,然后加密解密,调完在最后13s的时候交上去一发过了,非常欢乐。

赛后发现K的状态空间可以很简单地少个 \(\log\),场上除了这个都想到了,感觉或许再给点时间能想出来。

感觉这场最大的问题就是J的输入顺序虚空debug了半场,浪费了很多时间,导致没多少时间想K了,算是有点可惜。