考试:
大约在 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 的题经常由于精读问题做错)。
不管什么,先把基础的输入打进去。
果老师说过,先把求出的问题表示出来,然后再考虑进行优化。
以下是当时思考的过程:
先表示时间:
\[maxt=\frac{L\times C}{Vmax} \]求解答案:
\[\sum_{i=1}^{n}\sum_{k=1}^{i-1}\frac{maxt}{\frac{C}{v_i-v_k}}=\sum_{i=1}^{n}\sum_{k=1}^{i-1}\frac{\frac{L\times C}{Vmax}}{{\frac{C}{v_i-v_k}}}=\sum_{i=1}^{n}\sum_{k=1}^{i-1}\frac{L\times(v_i-v_k)}{Vmax} \]而对于每个速度我想得是都要进行一遍求值,所以对于每个 \(i\),求出它能超过的奶牛就是:
\[\sum_{k=1}^{i-1}\frac{L\times(v_i-v_k)}{Vmax} \]接着就很兴奋,直接用前缀和优化了一波,但是输出的答案是 6。
找了 10 分钟,把所有的过程全部都输出了一遍,结果发现在 \(i=4\) 的时候出了错。
又推了几遍公式结果就发现了巨大的错误:
正确答案(对于 \(i\)):
\[L\times(\lfloor v_i-v_1 \rfloor+\lfloor v_i-v_2 \rfloor+\lfloor v_i+v_3 \rfloor)+...+\lfloor v_i+v_{i-1} \rfloor \neq L\times [v_i\times (i-1)-\sum_{k=1}^{i-1}v_k] \]当时已经过了很久,想着要把 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-x \equiv b-x( \mod{d} )\Rightarrow a \equiv b (\mod{d}) \Rightarrow d \mid a-b \]所以只用枚举找到 \(a-b\) 的因子找到 \(d\),并求出 \(x\) 即可。
又因为:
\[a-x \equiv 0(\mod{d}) \Rightarrow x \equiv a(\mod{d}) \]这样便可以通过 \(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\) 这一段合法的最小代价。
那么可以从小区间推广到大区间,求出最小值:
\[f_{i,j}=\min(f_{i,j},f_{i,k}+f_{k+1,j}) \]考虑端点情况。
如果 \(s_i\) 和 \(s_j\) 匹配,直接转移。
否则就会有:
- 若尾端点为前括号,首端点为后括号,则首尾端点一定都要修改。
- 若尾端点为前括号,首端点也为前括号,则尾端点一定修改。
- 若尾端点为后括号,但首端点为后括号,则首端点一定要修改。
- 若尾端点为后括号,但首端点为前括号,则首尾修改一个即可,取最小值。