8.20模拟测试

总述

这场难度差距比较大。T1签到题，可以直接暴力模拟，但是我直接写了个余数，然后是T2，比较简单的数学结论题，其实就是个三角形面积公式。由于搬题人事先没有了解，zzc也没作阻止（也可能是忘了），T3撞了，于是就集体A了。

接下来就是比较难的三个题了。T4其实也是结论题，然后结论题我一窍不通，然后就打了暴力，然后暴力挂了，然后就0分了（悲

T5是个很抽象的题，场上暴力还没写完就结束了（悲*2，这个题讲解的时候说要用bitset优化。

T6考试的时候我都没看，后来看了看，《根号分治》。

T2的结论

好吧好像有点偏题。这就是说在平面直角坐标系上的一个三角形，如果其中一个点是坐标系原点，那么他的面积就是

$\frac{\text{abs}(x_1y_2-x_2y_1)}{2}$

如果不在也没关系，平移过去就行。于是这个题就是个简单枚举。当然了，理论上这个题目可以用海伦公式来做，但是出于 sqrt() 函数的精度问题以及计算机存储 double 类型的精度问题，这个方法不甚可取。我最开始没想到正解，于是就用海伦公式试了试，结果精度问题实在是太烦了，遂放弃，后来推出来了正解。

T4

这个结论也比较经典（虽然我不知道（雾 ，就是对一个区间 $[l,r]$ 求 gcd，从前往后 gcd 最多变化 $\log_2V$ 次，原因是如果发生变化就肯定是至少除以2，除以 $\log$ 次以后就肯定变成1了。这样我们就可以优化暴力：如果 gcd 不变，我们肯定是把区间填满最好，这样我们就只需要遍历所有 gcd 发生变化的点，然后再进行枚举即可。

未完待续（可能就没得续了