题目链接： http://codeforces.com/contest/764/problem/D
主要题意： 一个无限大的平面被分为无数个小正方形格子，一些相连的格子们可以组成矩形。给出左下角和右上角的坐标来表示该矩形（比如给出 0 0 5 3 即代表坐标为（0,0）开始到（5,3）之间的所有格子组成的矩形）。矩形的长和宽只能是奇数，给出一些矩形的坐标表示，要求写程序为所有的矩形染色，相邻的矩形不可染同种颜色（题中已经给出所有的矩形没有两两相交的情况出现，且相邻的条件为存在大于0长度的公共边），如果存在染色方案则输出YES并且输出N个矩形的每种染色情况（如果存在多种情况输出任意一种即可），如果不存在染色方案则输出NO结束。
思路描述： 由于我们已知任意一个地图都4可着色，因此第一行一定永远是"YES"。关于着色方案，我们重点关注所有的边均为奇数的条件。
由于所有的边均为奇数，那么对于两个相邻的矩形，我们考虑其左下角的坐标：设其为A (x1,y1)和B (x2,y2);
当A与B水平相邻时，即如下图所示（黄色为A，蓝绿色为B，其中(x1,y1)以及(x2,y2)分别表示红色的点和蓝色的点）：
我们可以看出对于任意两个相邻的矩形，其必有(x1与x2)或(y1与y2)的奇偶性不一致（因为所有矩形边长均为奇数），由于我们有4种染色方案（设为1 2 3 4），因此我们可以构造其染色情况为
[(x%2+2*(y%2))+4]%4+1（其中x和y表示该矩形左下角坐标），即可保证相邻的矩形中没有同色的情况（因为该染色情况下同色当且仅当x与y的奇偶性一致）。
代码样例：
1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <string> 5 #include <map> 6 #include <stack> 7 #include <queue> 8 #include <algorithm> 9 #include <vector> 10 #include <functional> 11 12 using namespace std; 13 14 #define LL long long int 15 #define INF 0x3f3f3f3f3f3f3f3f 16 #define MOD 1000000007 17 const int MAXN = 1e05 + 7; 18 #define ALPHA 26 19 20 int main() 21 { 22 int n; 23 cin >> n; 24 cout << "YES" << endl; 25 for (int i = 0; i < n; i++) 26 { 27 int a, b, c, d; 28 cin >> a >> b >> c >> d; 29 int tmp = ((a % 2 + 2 * (b % 2)) + 4) % 4; 30 cout << tmp + 1 << endl; 31 } 32 return 0; 33 } View Code2017-02-14 00:18:36
转载于:https://www.cnblogs.com/witchingfox/p/6395955.html
