【CF763B】Timofey and rectangles 题解

题目大意

  平面上有 $n$ 个矩形，每个矩形的边长都是奇数。并且矩形之间不会相交或者包含。
  现在你要用四种颜色去染这些矩形，使得相邻的矩形不同色。请给出一种染色方案，或者输出无解。
  $n \le 5\times 10^5$。

]

题解

  这个思路也是比较巧。。。

  首先根据四色定理，一定有解。

  现在我们要构造染色方案。关键是给每个矩形分配一种恰当的颜色。我们知道暴力是不行的，那就有一种想法，我根据矩形的参数计算出这个矩形该用什么颜色。由于颜色数只有 4，所以我们要找到一种合适的参数，它的大小也是 4。
  于是我们用这个：矩形右下角的横纵坐标奇偶性，恰好大小为 4。

  下面来证明这是对的。只需证明，若两个矩形相邻，则他们横纵坐标奇偶性不会完全相同。
  设矩形 $a$ 的横长为 $c_a$，纵长为 $r_a$，右下角坐标为 $(x_a,y_a)$
  1、矩形 A 与矩形 B 呈上下相邻，A 在 B 上面：则 $y_A=y_B+r_B$，由于 $r_B$ 为奇数，因此 $y_A$ 与 $y_B$ 奇偶性不同。
  2、矩形 A 与矩形 B 呈左右相邻，A 在 B 左面：则 $x_A+c_B=x_B$，由于$c_B$ 为奇数，因此 $x_A$ 与 $x_B$ 奇偶性不同。
  证毕。