赛前心态挺平和的.
主要是觉得去年像联赛那样自己吓自己挺不值的(现在还是觉得自我惊吓导致Day2在不会T2证明的情况下优先选择补证明而不去卡常太愚蠢了,到手的AK就这么没了…).
就考两天试也没啥必要把自己折腾得死去活来,不如吃好睡好.
虽然最后也没吃好,因为9:00~14:00的考试时间太反人类了.
心态平和的另外一个原因是,听说我手上的NOI2019 Ag好像在强基计划里还是有用的.

Day1

开场看到个string,莫名兴奋.
按照传统先看T2,发现T2名字叫传统艺能,又是个线段树上搞一搞的题.
回忆了一下之前几年的线段树题的做法,顿时有种出题组没题出了的错觉.
一看部分分,好像比去年常数一卡就是60分的垃圾出题组高明多了(悲伤的事情是听说还是有人因为这题的常数原因退队了).
之后看T1,是个字符串+DS,80分暴力似乎挺一眼的.
接着看T3,一股浓浓的ATC风格扑面而来,稍微想了想好像30分好像挺显然的.
之后回去想了想T1,感觉可以将所有runs建trie然后区间本质不同子串计数,ZJOI就这难度? 不过有点难写(而且实际上这是个假算法).
于是先去写T2了.写完发现大样例要跑7s,回想了一下去年的卡常经历,把矩乘全部展开就只用2s多了.
还真就传统艺能(指出矩乘题必定配合完全展开)?.
把T1的runs部分写完后,觉得可以利用等差数列去掉LCT.
写完调了调发现过不了样例,搭了个拍发现算法假了了了…
好像直接原地修锅的话,可以把问题转成求每个本原串最大重复次数的的奇偶性.
主要是贡献里面有个除二下取整,直接求和的话应该还是好弄的.
抢救到11:30还是没成功,心态有点崩了,因为手上还是只有一个T2.
冷静了一下觉得应该先想一下T3的50.
看着题面突然想到noip2018D1T1的三行做法—答案等于相邻两数差的绝对值之和的一半(虽然那题我场上写的是笛卡尔树做法).
然后想到一个 $O(\prod a_i)$ 的做法,就是枚举每个位置有多少的值是由策略1干掉的,然后可以用noip2018D1T1的做法计算代价.
稍微前缀和优化一下就可以得到三方做法了,这时大概是11:50.
然后回去补了T2的 $O(n\sqrt n \log n)$ 做法,就是利用每个位置的本原平方串数量只有 $\log n$ 个的特点,然后直接莫队维护每个本原平方串的最大重复次数.
感觉这个做法挺蠢的,按照去年的经验也不太能有分.但是不写这个的话我还得写一堆暴力.
写完发现随机数据要2s,噫我稳了.然后发现斐波那契串要12s,草.
好像去掉莫队也要3s(时限也是3s),md那q=1的分都不一定有,突然想问候出题人.但我自己出题有时候也是这个风格,这叫罪有应得?
回去把T3的50写了,回来补了个T1的q=1,这时是13:12,我应该60+100+50=210还是有的,估计能进队了.
但是毕竟还剩40多分钟,挣扎着卡了卡T1的常,想把vector换成离线基排,还想嵌个完美串数量不超过1e6的暴力进去,写到一点三十几觉得写不完就弃疗回去检查了.
出来听说有人看到"传统艺能"以为是反语就没开T2(悲伤的故事…).
还听说真有人搞出了T3大于50,感觉非常厉害.

Day2

早上听说Day1标准分250,所以我的根号log跑过去了???
开场因为试题分发问题咕到9:10.
打开题先看T2,看到最小时间的期望下意识的min-max容斥,然后以为 $a_i$ 不是两两不同的,死活不会做.
再仔细看了眼题发现保证 $a_i$ 两两不同,但还是不会做.
看了眼T1和T3,感觉T1应该先写个暴搜找规律,T3是个CTF?
回去接着刚T2,中途推出来个多项式复合(那写个m^2复合就能有70?)
再想了想发现题意可以转成求出,染黑i个球,且没有连续k个球被染黑的方案数.
显然可以 $O(m^2)$,稍微推了推式子发现还可以 $O(\frac{m^2}{k})$,那我能有80?
然后还想推100,发现不会.写完 $O(m^2)$ 就10:50了.
然后去搞T3,想到已知 $a_1,c_1,a_2,c_2$ 的情况下,枚举 $b_1$ 可以直接算出 $b_2$,然后检查一下 $b_2$ 的值是否在合法范围内.那再写个BSGS就可以根号log了?
写完随了组数据发现1e11要4s,再随了几组数据发现1e11要1.5s,1e12要10s+.
那我又常数杀没分了?
T2对拍关掉1e11就能跑进1s了.
输出了一下快速乘次数发现比预想的多得多,冷静了一下我的复杂度好像还要加上 $O(\frac{err^2}{p})$.
那它放几个 $p=1e15,err=1e11$ 的点我就没了?这时快12:00了,赶紧跑路看T1.
瞪了半天还是不会暴力,自闭到13:00写了个链(由于某些原因考试13:25结束…).
回去看T2,发现会了个 $nk^3\log n$的算法,大概就是每个元素是多项式的矩乘,但感觉没分.
把 $O(\frac{n^2}{k})$ 补完后觉得可以直接倍增就能把log不乘在k^3上.
但由于时间已经所剩无几了,就回去补了个T1的环,还剩3min的时候发现S包含1号点的情况写挂了(但改完后好像T1还是爆零了嘤嘤嘤).
出来听说$E自称没上200(一副切了T3的样子,我直接吓傻了),supy 130.
感觉省队应该还是有的.
出分后本博客可能还会继续更新.