ZJOI2020 游记

初测出来了,貌似退役失败了,鸽子续命两个月。

前排提醒下文有 15 个 “然后”,15 个 “看”,11 个 “感觉”,18 个 ”发现“。

Day0

在机房颓了一个早上,然后坐大车车来到了杭州。

Day1

翻车现场。

看到题目感觉 T1 可能暴力很好打,T2 很套路,T3 要推一下,于是开始开题。

看了看 T1 部分分,先写了一个 (O(n^2Qlog n)) 的暴力准备对拍。

中途脑子抽了不会数本质不同个数了,然后直接枚举长度,SAM暴力。

然后发现貌似 (O(n(Q+n) log n)) 常数不大可以写写,感觉 5000 随便跑。

于是码出来拍上了,发现还有 (20) 是个优秀的拆分,(Q = 1) 不太会做,感觉太难写,先跳过。

看到 T2 发现只需要一个矩阵快速幂即可,优化一下乘法,发现 4s 本地跑了 2.4s,感觉不用特判叶子以获得一半的常数就能过了,于是不管了。

看到 T3 发现只要暴力 DP前缀和优化就能 50,感觉 70 不太好写,甚至可能会推不出,所以回去搞优秀的拆分。

看到部分分,“保证 T 中所有的优美的串的个数不超过 (10^6),这里位置不同的串被视为不同的”。想了想,我不太会构造这样的数据啊,对于所有出现的 AA,都互不相同。

出题人是万能的,一定会构造。那么我就改改暴力假装数据是对的拍吧!

调了一下真拍上了,就不管了。

然后最后检查了一个小时,arbiter 怎么测都测不出 T1……

然后看看,发现 MLE 了,改了改能测了,避免了 T1 爆零的行为。/cy

出来估分 (60 + 100 + 50 = 210)

然后出榜才知道炸没了,(0 + 80 + 50 = 130)

问了一下机房的人,有人 T2 本地 3s 都过了……什么鬼啊…………………我这tm是怎么被卡常的???

然后发现 T1 题面是没读错,但是部分分竟然全部读错了……

原来,只限制了 (n leq 5000),没限制 (Q)……

同时问了一下机房的人,他们都认为 (20) 的部分分的“视为不同”,是指统计这个 1e6 的时候是视为不同的,而不是在原串中就被视为不同的………………

早这么说,我也不会写出这么奇怪的复杂度啊…………说到底还是自己菜……

到头来,以为挽救回来的 T1 还是炸了……

结果考完还不知道自己挂的那么彻底。

Day2

看了题,发现今天貌似很瘤。晚上睡的不是很好,代码打着都感觉脑子缺氧……

感觉 T2 最好做,先开。发现就是一个简单的 minmax 容斥,于是写完了 50 并过了大样例,想想 70 挺好写,但是貌似 100 是个分治 ntt,可能可以做,先推推。

然后用 n^2 dp 的递推推生成函数,发现推不出来,于是去搞容斥。发现算完之后还要一个不可名状的操作。(说到底是多项式学的不好)

搞了好久一直推不出,一直没想到直接生成函数解方程来规避这个 n^2 dp 的问题………………(后来听说推出这个可以直接 (frac{n^2}{k^2}) 甚至 (frac{n^2}{k})

算了,去打一下 70 分,然后发现过了 2h 了。

感觉 T1 有点瘤子,先给 T3 1h 试试。

然后发现自己不会类欧了…… 所以先写了一个随机化,发现挂了,以为是自己的随机化错了。

看看 10分 貌似挺好打,就是找两个方程,化成类似 (l_1 < y < r_1, l_2 < ay < r_2) 的形式。因为数据随机,同时满足这两个的解不多,每个 check 一遍就好了。

感觉不太好写,先去 T1。

然后先花了好长时间打了总点数,然后过了带样例符合条件的点。

然后同时写了链和环,拍过去了。

arbiter测一下,分应该拿到了。

看看还有 20 min,马上补了一个 T3 暴力,发现之前的代码不止写挂了一处……

好吧,补随机化无望了,调完 (O(err + ?)) 就剩几分钟了,发现 arbiter 测不过,原来输出了多余的信息……

然后注释一下就过了样例的两个点。

出来估分 (20 + 70 + 10 = 100)。三位数还好看一点,估计标准分 140 左右。

然后发现自己 (110) 了,原来样例第二个点是 1e8 的,出来前看错了。

然后出分了,day1 标准分 250,day2 标准分 135,感觉人要没了。拉一下榜,发现还行。

day1 莫名其妙地挂了,day2 又莫名其妙地翻了…… 这次真的暴力都没打满……

这几天都不知道发生了什么,云里雾里的。考试时智商已经炸没了,原先会的东西一到考场上全部不会了……所以感觉还是运气好了点啊……


UPD 6-29

下午重测了,挂分退役预定


UPD 6-30
继续退役失败

挂了十分,运气太好,没掉出去

原文地址:https://www.cnblogs.com/daklqw/p/13175335.html