CF763B Timofey and rectangles 做题记录

平面上有 nn 个与坐标轴平行的矩形。矩形的所有边的长度都是奇数。矩形不能相交,但它们可以互相接触。

你要让每两个接触的矩形有不同的颜色。如果可以则输出 YES,并给出每个矩形图上的颜色([1,4]\in[1,4];如果不行输出NO

根据四色定理,所以一定可以染色。

由于长方形的边长都是奇数,所以可以按照长方形左下角两个坐标的奇偶性分类,分别叫做奇奇、奇偶、偶奇、偶偶。与某种类型的长方形相邻的长方形一定是另外三种类型之一,所以可以给奇奇涂 11、奇偶涂 22、偶奇涂 33、偶偶涂 44