这次发挥很好啊,rank1,300pts,比rank2高了70pts
T1
发现操作二的影响是不可避免的,就尽可能让操作1没影响,每次就删连续的相同的数字,然后统计一下即可
T2
感觉思路很自然,首先只需要保留近k次操作
如果有一个横的和一个竖的覆盖两个点,就可以直接走曼哈顿距离
如果两点之间被横或竖的填满就走曼哈顿距离
如果两个横行或竖行,就找一个代价最小的另一种操作,如果都没有就-1,用线段树维护上面的操作,每一次可以直接二分或线段树二分,由于开了3s,所以稳过(也不稳,要不是我卡了常就挂了)
T3
找到y坐标最小的点,然后把这个点左边的所有点设为不可走,然后从起点开始跑最短路然后枚举合并上下部分的答案
如果起点在y坐标最小的点左边,就换成找y坐标最大的点,把这个点的右边设为不可走,然后一样做即可
这样做的合法性其实就是y坐标最小的点的左侧一定会被经过,其他的不一定
T4
首先,我们还是考虑推一下式子
设\(k0=power_1-power_2,k1=point_1-point_2\)
\(point'=2\times sig(k0)\times (\sqrt{|k0|+1}-1)-A\times sig(k1)\times (\sqrt{|k1|+1}-1)\)
我们设函数\(f(x)=\dfrac{x}{|x|}\sqrt{|x|+1}-1\),特别的,x=0时为0,\(g(x)=x-f(x)\)
首先,f是单调递增的,这个是显然的
然后,g也是单调递增的,这是由于f的增长速率是小于1的,就是说x每增大1,f增大小于等于1
然后我们就可以化简式子,先看A=0
\(point'=point_1+2\times f(k0)\),显然单调
A=1:
\(point'=point_1+2\times f(k0)-sig(k1)\times (\sqrt{|k1|+1}-1)=point_1+2\times f(k0)-k1-sig(k1)\times (\sqrt{|k1|+1}-1)+k1=point_2+2\times f(k0)+g(k1)\),也单调
于是得到结论:point1越大越优,power越大越优
所以二分power,先以1为根做一遍,算出子树中叶子到当前点的最优的point,然后换根,每次就相应的更新即可,有许多细节和玄学精度问题,需要调参(?)