PKUSC游记

Day 0

上午直接和gjz,szq大佬们去了机场,平平无奇的上了飞机,平平无奇的到了余姚。在酒店gjz和szq住在一起(希望人没事),我独自一个屋/cy。下午大家一起去吃了火锅,平平无奇。

一下午没打开房间空调也是没谁了/kk。

Day 1

早起指7点 ,去酒店餐厅吃早饭(人真多),并没有感觉多好。步行前往余姚中学,签到,然后去四楼机房熟悉环境。两道题,只看了第一道。想出了一个subtask跟gjz说了,然后他写出来了过了我没调出来(哭泣)。这算不算两个小时爆零了哇~

出来之后面基到了 zjb 神仙,他把那道题切了……竟恐怖如斯!

已经准备好下午直接自闭了呢。

比赛前 szq 奶出斗地主ovo。

先开T1,不错 (n^2t) 的做法非常好想也非常好写,写了之后交了一发,过了第一个 subtask ,然而连 20pts 也没给。部分分也太少了吧!看眼T2,写了个 (nq) 的暴力,得了 7pts ,简直魔鬼。一看T3,神tm德州扑克,我动都不动好吧。

去看 T1 01矩阵的分,完全不会,想不到性质。随便手写了几组数据发现在不超过两次变换后就不变了,随便写了一个让他最多进行30次变换然后交上去,居然过了……

再看 T2 关于全局修改的部分,想能不能怎么根号平衡一下,发现并不能做到,想的什么维护上升链或下降链全都假了。随便想了一个倍增的做法乱搞一下,写出来测了下样例居然过了,交上去居然也没错可还行。于是这题拿了46pts,暴力全写也没有一半的分数太草了。

想我是写大模拟的暴力还是想 T1 的正解呢,自然是写暴力,正解是不可能正解的。然而 T3 暴力也想不出来自闭了。

滚去自闭随便想 T1 正解,T2T3 是没法搞了。

弄了个全 1 矩阵跑了一下,发现各个点都是一样的,好吧没啥用。弄了个只有一个 1 的矩阵跑了一下出现了奇怪的特点。整个矩阵只有 3 种数字。发现可以把这三个数字设出来弄一个递推式,然后无脑矩乘优化一下就行了。这就能过了,写了一发就切了……太草了。

最后 146pts 滚了,盲猜这套题我能拿 146 别人估计得 230+。wtcl。

出来之后发现 gjz 也146,他肯定放水了好吧……

Day 2

早上差点睡过了呜呜呜。

去参观了 noi 的场地,关于进女生宿舍参观那些事(雾)。键盘似乎感觉不错。另外还有在车上的王者快乐训练营hhh。

下午已经准备好了持续自闭呢!希望不要太惨。

开题发现 T1 我可以 (n^4) 耶!可以过 100 耶,拿了 22pts,非常开心(雾)。看了一下 (k=0) 的情况,直接换根就可以了,板子题。去看 T2,想写一个 (nq) 的贪心。各种乱搞后终于可以过了样例,觉得没有问题,交上去拿了 40pts,还不错。看一眼 T3 ,又不可做,随便口胡一个 &n leq 3& 的做法,交上去果然挂了,但是有固输的 5pts ,美滋滋(不是)。

回去看 T1 ,想一下链的情况,感觉可以枚举断边然后处理两边内以及跨越两段的贡献分别统计,调了相当长一段时间也是过了。然后再想把这种做法扩展到树上,枚举断边然后分别统计贡献,可以做到 (n^2) 。 至此,60pts 拿到。

想了一下两个连通块的贡献应该可以推出来,想到了 (O(n)) 的换根 dp做法,但是时间不够没调出来哭泣。

最后拿了60+40+5=105pts,也还行吧qwq。

Day 3

听说面试线310+,我还是太菜了哭泣

原文地址:https://www.cnblogs.com/nao-nao/p/14779596.html