2024.9.4-CSP模拟赛3
考试：
9:00~9:25
怎么还不发卷啊，等得有点慌了，这是在考验心态吗？
原来是极域出了点问题
9:25~9:35
发卷了，先看题。
- T1：相对距离，这不是原题吗，这题能做。
- T2：平衡队列，数据有点大，要不要离散化？好像不用，先等会在仔细看看。
- T3：第一眼数据范围：\(1\le N\le 100\)，直接弗洛伊德呀。
- T4：是并查集吗？第一眼以为是用差分约束做的那道说谎的奶牛。但是 \(3\le n\le 10^5\) 那就没事了。
9:35~9:50
T1 以前做过，但还是很久以前了，对于正解也忘得七七八八了。
本来想着先看 \(s,t\) 中有多少个不同的位置，但看了一下好像对于答案没有什么贡献。
于是想了一下，先将 \(ans\) 数组全部赋值为 \(0\)。先求出在此情况下 \(s,t\) 和 \(ans\) 的汉明距离是多少，然后在进行模拟即可。
注意：由于是求出字典序最小的 \(ans\)，所以可以从后往前进行模拟，这样就保证了答案字典序是最小的。
9:50~10:25
一看就是要用前缀和优化的，推下式子。
\[sum_r-sum_{l-1}=\frac{r-l+1}{2}\Rightarrow Dis_{max}
\]
但这样时间复杂度还是太高了，注意到 \(1\le n\le 50000\)，怎么做？
用 \(O(nlog_n)\) ？但是答案好像没有单调性，但这个式子好像又无法优化，那就直接写吧。
写完了，测了几组也没有什么错误，希望分得多一点吧。
10:25~11:25
做 T3，正解不就摆在眼前吗？可是不知道为什么考试的时候脑子就是不灵光，弗洛伊德写了，取模也写了，但还是 WA 了，样例过不去，弗洛伊德不知道为什么写挂了（赛后发现 \(x_i\rightarrow x_i\) 的这条边不要删，自作多情地赋值为了 0）。
写特判吧。
赛后秒过……
11:25~12:00
没有发现确定了前 2 个数就可以确定整个序列的性质。
只能写暴搜，写挂了 2 次，还有 2 分钟的时候才写对。
总结：
- 在竞赛上用数学推导非常重要，要多训练这一块的能力。
- 对于时间的把控要到位。
- 模版必须随手写出。
- 性质可以多去猜，就像数学归纳法一样。