S1
90 pts。
S2
\(14:30\)
全机房都打不开题,然后用 U 盘拷的题,乐。全机房补了 \(20 \operatorname{min}\)。
\(14:50\)
这是 T1?这是 T1?这是 T1?这是 T1?这是 T1?
一眼爆搜,\(10 \operatorname{min}\) 写完过了。
\(15:00\)
开 T2。一眼感觉枚举 \(r\),然后 DS 维护。
推了一下感觉不好做,于是想了想 dp。
然后发现会了一个时空 \(O(n\sum)\) 做法,码完过了。
\(??:??\)
开 T3。光速写了代码,发现题看错了,但是过了小样例。/qd/qd
重新写了一遍,调了一下过了样例。
\(17:10\)
开 T4。
想了想感觉可以二分。然后容易求出每个点被种的最晚时间。
然后发现是 ABC304H 的弱化版,就做完了……?
写完调了不久,大概 \(18:20\) 左右过了样例,但是本机 \(1.1s\)。后来尝试卡常,还是卡不进 \(1s\)。/qd/qd
赛后
在这上面交了一发,\(?+100+100+100\)。
赛时做法
T1
直接搜。
T2
\(f_i\) 表示以 \(i\) 结尾的合法串的数量。\(g_{i,j}\) 表示长为 \(i\) 的前缀,\(S_{i+1}=j\),最大的 \(x\) 满足子串 \(S(x,i+1)\) 合法。\(S(l,r)\) 表示 \(S\) 从 \(l\) 到 \(r\) 子串。
转移是容易的。
T3
按题意模拟。
T4
二分天数 \(D\)。
目前只需求出 \(t_i\) 表示 \(i\) 最晚什么时候被种。这个可以二分求出。
然后就是 ABC304H 的弱化版。
总时间复杂度 \(O(n\log^2 V)\)。