expect： \(100+100+65+25=290\)
真实： \(100+85+0+15=205\) ， rk62
感觉自己考的好烂好烂好烂
T4 这么简单竟然想不出来，感觉如果自己不被 T4 吓到，全做出来其实有望 365+ ？
今年 CSP-S 怎么这么简单吓得我不敢做了
T1
暴力
T2
考场做法：
设 \(lst_i\) 表示 \(a_i = a_{lst_i}\) 并且 \((lst_i, i)\) 中所有数都可以通过若干次操作消除的最大的 \(lst_i\) ，如果没有则为 \(0\) 。
设 \(res_i\) 表示以 \(i\) 结尾的答案
对于一次记录答案，让 \(j = i-1\) ，然后一直让 \(j = lst_j - 1\) 直到 \(a_j = a_i\) 位置或者 \(j \leq 0\) ，然后把 \(res_i = res_{j-1} + 1\) ， \(lst_i = j\)
复杂度 \(O(n \Sigma)\) ，其中 \(\Sigma = 26\)
被卡满的数据： aaaaabbbbbbccccccddddd.....zzzzzz
考试数组 \(2e6 \rightarrow 2e5\) ， \(100 \rightarrow 85\)
T3
傻逼大模拟，暴力就是了
考试时发现大样例没有一个特殊性质 ABC 的什么意思？
T4
考试的时候没想出来非常非常惭愧
考试时想到了二分答案，想到了求出每个点的最早时间，但没有发现从最早的开始做就行，而是以为要按照他们的时间 \(-\) 距离最近标记点的距离排序，然后以为又要什么高级 dp ，遂只写了链 and 菊花，但考试最后貌似也写寄了
我们发现只要每次选最早的做即可，因为我们提前做完它后用剩下的时间再做别的，这等价与先做别的再恰好卡常把这个任务做完
怎么找到最近距离 + 染色？树链剖分？这么想就太 naive 了！
直接暴力染这个点一直走父亲直到遇到标记点即可。每个点最多被染 1 次，复杂度 \(O(n)\)
如果你二分求每个点最晚完成时间，并且对每个点时间排序，复杂度是 \(O(n \log n \log A)\) 的
但我们可以直接用数学方法求出每个点最晚完成时间，记作 \(t_i\) ，发现 \(t_i > n\) 的一定可以完成，因此只需对 \(t_i \leq n\) 的桶排即可，复杂度是 \(O(n \log n)\)
标签：res,题解,复杂度,lst,2023,100,CSP,考试 From： https://www.cnblogs.com/fox-konata/p/17780227.html