[vp]ARC063

https://atcoder.jp/contests/arc063/

\(A\):统计颜色段数

\(B\):统计最大差有多少对

\(C\):

所有点的奇偶性可根据给定点确定(邻节点权值奇偶性不同),
每个点的取值范围很显然可以通过树形\(dp\)求出来。
通过上述信息判掉无解后,直接满足以上条件构造即可。

还有一种比较奇怪的构造,每次选出权值最小的点,
然后确定它周围的点等于它的权值\(+1\)
最后再判无解。不知道怎么证正确性。。

\(D\):

题意转化成:求一个周长最大的矩形使得不包含任意一个点。
我们发现矩形周长的下界是\(max(w+1,h+1) \times 2\)
如果超过这个下界很显然是要越过\(x=w/2\)\(y=h/2\)两条直线之一,也就是两条对称轴。
简单证明:如果不越的话就是某个\(1/4\)部分的矩形。周长为:
\(2*(w/2+h/2)=w+h < max(w+1,h+1) \times 2\).
根据上述性质,我们先求出矩形过\(y=h/2\)的答案,\(x=w/2\)是一样的。
我们枚举矩形右边的直线\(x=x_1\)
然后求出\(x=x_1\)\(x=x_2\)之间位于中线上的第一个点\(u\),位于下面的第一个点\(v\)
通过这个求出的最大的答案。
就是左边直线\(x=x_2\)
复杂度有点高,考虑用线段树优化。
我们需要查询\(dis_{up}+dis_{down}+(x_1-x_2)\)最大的点。
我们设\(x_0\)\(x_1\)的前面一个点
我们把\((x_1-x_0)\)化成\((w-x_0)-(w-x_1)\)即可,用线段树直接累加。
\(dis_{up}\)\(dis_{down}\)可以用单调栈维护,每次出栈的时候用线段树修改。
查询就是求一个前缀\(max\)了。

时间复杂度\(O(nlogn)\)

[vp]ARC063

上一篇:如何能够清除aud脚本?


下一篇:【设计模式】命令模式