2024.9.2-CSP模拟赛1
考试：
大约在 9:40 左右发了题。
9:45
把所有的题目都快速看了一遍，T1 感觉模拟可能会 T，T2 最小生成树的板子，T3 又是追及问题感觉要挂，T4 感觉像是区间 DP。
9:50
开始做 T1，先是手搓了一个 gcd 又手动模拟了取模（想起了 xqy 因为取模导致的 TLE），样例输出得都挺快的。
- 但是看了一眼数据范围：\(1\le a,b \le 10^{12}\)。
这……感觉会 TLE，尝试推一下公式，看一看有什么规律，结果推了一半，后面的没有推完。
当时差不多推到了这里：
还是没有写出 \(g\) 和 \(a\) 之间的关系。
打表找规律！但好像也没有什么特殊的地方，导致 TLE（当然还有一些特殊优化）。
10:00
模拟写得很快，想着等一会在回去优化。
T2 最小生成树的板子题，由于忘记提前将 \(m\) 条边连接的点先放入一个集合中，导致调了 5 分多钟，期间一直输出的 6.25。
发现了在进行长度计算时，长度会爆 int，于是就先定义了一个 long long 型的 \(Dis\)，然后再进行开根（其实在 \(ans\) 计算时在开也可以）。
- 十年 OI 一场空，不开 long long 一场空。
虽然在计算时开了 long long 但是在其他的地方也有会爆 int 的。
挂 40 分。
10:20
先看了一眼 T4，发现在边界的计算有点难办，选择做了自己不太擅长的 T3（有 double 的题经常由于精读问题做错）。
不管什么，先把基础的输入打进去。
果老师说过，先把求出的问题表示出来，然后再考虑进行优化。
以下是当时思考的过程：
先表示时间：
求解答案：
而对于每个速度我想得是都要进行一遍求值，所以对于每个 \(i\)，求出它能超过的奶牛就是：
接着就很兴奋，直接用前缀和优化了一波，但是输出的答案是 6。
找了 10 分钟，把所有的过程全部都输出了一遍，结果发现在 \(i=4\) 的时候出了错。
又推了几遍公式结果就发现了巨大的错误：
正确答案（对于 \(i\)）：
当时已经过了很久，想着要把 T3 过了，但最后还是没有很好的方法，于是就只能乱写了一个做法，样例也没有过。
11:20
时间花得有点久了，但是样例没有过。
如果现在就去做 T4，那 T3 完全就保龄了。
当时其实有点小慌，那就先把 \(n\le 5000\) 的暴力打了再说吧。
double 的精度问题又调了一会。
11:35
要没有时间了，赶紧写了一遍区间DP 的板子，结果发现在 \(i,j\) 处有 5 中情况。想了一下写完了。
11:55
测样例第 2 个没有过，是有初始化吗？不知道。
怎么办，只能写个骗分的代码交上去，死马当活马医。
总结：
- 在第一题的处理没有做好，平时学的数论知识没有全部用上，对于数论的运用还不够熟练。
- 如果有可能会爆 int 的情况下就一定要开 long long！
- 第三题耗时间太多了，导致第四题应该可以多得分。
- 对于以前学的区间DP 的掌握程度还不够，应该要多练习和思考。
- 对于像 T3 最后化出来了式子可以用逆序对的方式解决。
题解：
T1：
- 如果直接暴力的话，当 \((a,b)=1\) 出现多次时，就会导致下降的速度变慢，所以有可能会 TLE。
- 那么考虑将连续 \((a,b)=1\) 的次数求出来，及当 \((a,b)=1\) 时，求出 \((a-x,b-x)\neq 1\)（\(x\) 最小），这样就可以快速合并。
假设 \((a-x,b-x)=d\)，则有：
所以只用枚举找到 \(a-b\) 的因子找到 \(d\)，并求出 \(x\) 即可。
又因为：
这样便可以通过 \(d\) 进而快速求出 \(x\)，其余的就模拟即可。
特殊情况：
- \(a=b\) 步数为 1。
- \(a=1\) 或 \(b=1\) 则步数也为 1。
- \(\left| a-b \right| = 1\)，则步数为 \(\min(a,b)\)。
T2：
最小生成树板子题。
T3：
其实也可以考虑每头牛对于答案的贡献是多少。
发现如果多算了 1，则 \(l_i\) 的小数部分一定小于 \(l_j\) 的小数部分。
\(l_i=\frac{v_i\times(L\times C)\div v_n}{C},d_i=(v_i\times L) \mod{v_n} +1\)
将 \(d\) 数组求一遍逆序对即可。
注意：\(d\) 数组 +1 是因为怕出现有 0 的情况。
T4：
\(f_{i,j}\) 表示从 \(i\) 到 \(j\) 这一段合法的最小代价。
那么可以从小区间推广到大区间，求出最小值：
考虑端点情况。
如果 \(s_i\) 和 \(s_j\) 匹配，直接转移。
否则就会有：
- 若尾端点为前括号，首端点为后括号，则首尾端点一定都要修改。
- 若尾端点为前括号，首端点也为前括号，则尾端点一定修改。
- 若尾端点为后括号，但首端点为后括号，则首端点一定要修改。
- 若尾端点为后括号，但首端点为前括号，则首尾修改一个即可，取最小值。