pkusc2023

发布时间 2023-05-06 18:43:51作者: Legitimity

没想到吧,诈尸几天。

day0

坐高铁到了北京,社恐没面到几个人。

晚上看了看去年 pkusc 的题,不好评价。

day1

8:00 就到了,但依然没有面到几个人。

开营仪式没啥好说的。

电脑挺好用的(甚至是 i7-12xxx),键盘比傻逼 nfls 和华山的键盘好用多了。

试机题没啥好说的,写完之后敲了个 ntt 和 sam 然后就润了。(埋下伏笔)

食堂麻辣香锅好评。

吃完饭去未名湖转了转,鸭子很可爱。

12:40 回到机房,然后发现没有还原???(早知道上午对着 blog 把 sublime 配好了)

然后发题,T1 串串,T2 数数,T3 怕怕。

串串题是简单的,border 和周期对应,对着周期做就行了。只需要一个 z-box 和哈希就可以 \(O(n)\)

然后开始卡题。

觉得 T3 可能可做!猜是链分治后搞搞,但是胡半天发现自己不会菊花。然后看到上午写的 ntt 没被删,于是直接拉过来用,交上去只过了一个包。改成每次只更新祖先仍然只有一个包。(此时还没有意识到这样比回撤背包多一个 \((\log\log n)^2\)

然后这个人也没想想第二个包是什么意思,就觉得 T3 没有更多分了!半退役选手感觉是写不动这种题了。

T2 的 \(O(n^22^n)\) 是送的,但是只写 \(O(n^22^n)\) 肯定是寄的。瞪了半天发现可以 min-max 容斥,然后由于省选后一直没训已经有点没脑子了,首先想了一会 min-max 容斥正确的式子,然后发现只会一个 \(O(n^6)\) 的 dp,交上去两个包。

然后发现这玩意卡卡常能在 3s 跑出 \(n=130,m=65\),10s 跑出 \(n=150,m=75\),于是最后 40min 就把这个东西挂在那里打表,但是最后都没打完。

然后 100+53+12 遗憾离场。

出考场发现人均 T3 有 32,同时在杨爹的指点下会了 T2 的 \(O(n^4)\),然后明白了自己比大众分低了 67 分。

属实是文化课把脑子学没了。