大家都知道,熊爱鱼。但是迈克是一只奇怪的熊,他讨厌鱼!更奇怪的是,他有无数的蓝色和红色的鱼。 他在平面上标出了 $n$ 个不同的点。第 $i$ 个是点 $(x_i,y_i)$ 。他想在每一点都放一条鱼,使得每一条水平线或垂直线上的红鱼和蓝鱼的数量相差最多1。 他不能找到一种方式来执行,所以请你帮助他。 输入的第一行包含整数 $n(1 \le n \le 2 \times 10^{5})$ 。 接下来的 $n$ 行包含的每个点的信息,第 $i$ 行包含两个整数 $x_i$ 和 $y_i$ ,( $1 \le x_i,y_i \le 2 \times 10^{5}$ ),表示第 $i$ 个点的坐标。 保证至少有一个符合题意的答案。 将答案输出为n个字符r(红色)或b(蓝色)的序列,其中第 $i$ 个字符表示 $i$ 点中的“鱼”的颜色。

我们考虑把每一排每一列分别看成一个点 然后我们每个点就是勾连起这样两个点的一个桥梁

要求给这些点染色 使得一行一列内不同颜色的差的绝对值小于等于1

把不同颜色看成针对这个点不同的出边或者入边

那么欧拉图的性质就是入度和出度是相等的 但是有可能出现度数是奇数的情况 不妨我们两两给他们配对起来这样跑一遍欧拉图 最后把那些多余的边删除即可 强行钦定 边的方向为什么颜色即可

这题如果不加“类似当前弧优化” 是tle的

 

分类: 欧拉图

elijahqi

退役了 现在在商院 偶尔打CF,有时有ACM regional也去玩一下

发表评论