赛前
从学校坐校车去考点，发现qyb穿的衣服上面有个“璃月”，原来那次THUSC看到的是他啊，原批真可怕。
老师搞错了解压密码，搞了二十分钟用u盘在每个人电脑上拷了一份题目，延时20min。
t1
开场一眼秒。简单题，枚举，依据题意判合法性即可。
t2
看了遍所有题后，感觉t2最简单。
赛时前半小时推断错情况了，还好第一时间反应了过来。最初推的是合法区间是回文串或者由若干个回文串拼起来，后来3:30发现假了，还好发现得早，hack数据：
cabbabbc
马上想到 \(n^2\) 做法，枚举起点，将位置放入栈顶，如果栈顶位置的字母和当前字母相同则弹出栈顶，否则将当前位置加入栈中。
想了大概半个小时，想到了优化，感谢开始的错误想法引导了我。合法串与合法串相连肯定是合法串，因此维护一个 \(p_i\) 表示在前面栈的操作中弹出 \(i\) 的位置是哪个，如果没有位置弹出 \(i\)，则 \(p_i=-1\)。令 \(f_i\) 表示 \(i\) 开头的方案数，可以得到转移 \(f_{p_i+1}+1\rightarrow f_i\)。但是从 \(p_i=0\) 的点开始暴力维护栈是不可行的，注意到一件事，如果入栈的点 \(x\) 满足 \(p_x>0\)，那么 \([x,p_x]\) 一定都会被弹出，所以这段可以直接跳过；如果 \(p_x=-1\)，那么连 \(x\) 都无法弹出，前面的更无法弹出了。注意到这个地方复杂度仍然玄学，但如果那个跳的地方使用路径压缩，可以保证 \(/log\)，可惜我没写。
t3
写完t2，还剩2.5h左右，看了下t4，感觉像个神秘的连通块dp，于是决定开始写t3大模拟，写了2h，中间发现看错了题，还好不要改多少，没酿成大祸。
t4
最后半小时，对于 \(n\le 500\) 想了一个dp状态，令 \(f_{u,i}\) 表示 \(u\) 第 \(i\) 个选的最小天数，但是不会转移，放弃了。看到链，想到二分答案，再判断可行性，虽然只有一种选法，但依然没什么问题。其实这里就已经靠近正解了，但时间不够我继续想下去了。
出场后群友告诉我二分答案后，一个位置可以删除的时间是一段前缀，一个位置对应一个时间，是一个二分图完美匹配问题。好像可以hall定理维护，不管了，大概口胡完成了。
后记
这波洛谷网红graphcity没有做出t2，我做出来了，赢麻。
qyb还是太社恐了，真可怕。
标签：二分,t4,位置,t2,合法,S2023,CSP,dp From： https://www.cnblogs.com/luoshen0/p/17779669.html