Time limit : 2sec / Memory limit : 256MB
Score : 500 points
Problem Statement
AtCoDeer is thinking of painting an infinite two-dimensional grid in a checked pattern of side K. Here, a checked pattern of side K is a pattern where each square is painted black or white so that each connected component of each color is a K × K square. Below is an example of a checked pattern of side 3:
AtCoDeer has N desires. The i-th desire is represented by xi, yi and ci. If ci is B, it means that he wants to paint the square (xi,yi) black; if ci is W, he wants to paint the square (xi,yi) white. At most how many desires can he satisfy at the same time?
Constraints
- 1 ≤ N ≤ 105
- 1 ≤ K ≤ 1000
- 0 ≤ xi ≤ 109
- 0 ≤ yi ≤ 109
- If i ≠ j, then (xi,yi) ≠ (xj,yj).
- ci is
BorW. - N, K, xi and yi are integers.
Input
Input is given from Standard Input in the following format:
N K x1 y1 c1 x2 y2 c2 : xN yN cN
Output
Print the maximum number of desires that can be satisfied at the same time.
Sample Input 1
4 3 0 1 W 1 2 W 5 3 B 5 4 B
Sample Output 1
4
He can satisfy all his desires by painting as shown in the example above.
Sample Input 2
2 1000 0 0 B 0 1 W
Sample Output 2
2
Sample Input 3
6 2 1 2 B 2 1 W 2 2 B 1 0 B 0 6 W 4 5 W
Sample Output 3
4
这道题数据挺大的，首先是移动到2k*2k的框框里，不影响坐标（也就是横纵坐标都移动2k的整数倍,如果只移动k的整数倍不能保证颜色不变）。
最初先默认数黑色或者白色都可以，这里先默认数黑色，白色的通过变色移动（横或纵坐标+k）映射到黑色的位置，然后整个图里只剩下黑色的。
最后求出结果，只需要取sum 和 n - sum中大的那个就行了，因为默认是黑色，黑白可以互换。
然后是移动k宫格在不同位置，一共有k*k种情况，直接在2k*2k的框框里操作，需要计算二维前缀和，之前是一个一个点去判断超时了，想想也不能一味的暴力啊，肯定得用点妙招，然后移动x轴，计算一维前缀和时间勉强没超。
k宫格是从左下角开始移动就是从（0,0）开始，需要记录的是k宫格里黑色的个数，以及斜对角的矩形里黑色的个数，因为斜对角的颜色相同，横竖相邻的区域颜色相异。
计算二维前缀和需要用离散学的容斥定理，最后求单独区域需要前缀和相减，也要用到容斥定理。
代码：
#include <iostream> #include <algorithm> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <iomanip> using namespace std; int v[2001][2001]; int n,k; int num(int x1,int y1,int x2,int y2){ return v[x2][y2] - v[x2][y1] - v[x1][y2] + v[x1][y1];///前缀和 减去左边 下边和左下边的k宫格前缀和 容斥定理：左边和下边都包含了左下边 需要加上一个左下边 } int main() { int x,y,ans = 0,sum; char ch; scanf("%d%d",&n,&k); for(int i = 1;i <= n;i ++){ scanf("%d%d %c",&x,&y,&ch); x %= 2 * k;///把所有点都移动到 2k * 2k 的区域 y %= 2 * k; x += k * (ch == 'W');///x可以变成y W 也可以变成 B 这里白色都变成黑色的 如果转换后的黑色是满足的那么原来的白色也一定是满足的 v[x % (2 * k) + 1][y % (2 * k) + 1] ++;///求前缀和要求从（1,1）开始 } for(int i = 1;i <= 2 * k;i ++)///求前缀和 for(int j = 1;j <= 2 * k;j ++) v[i][j] += v[i - 1][j] + v[i][j - 1] - v[i - 1][j - 1];///加上左边下边和左下角的和 容斥定理：左边和下边的都包含了左下边的 要减去一个左下边的for(int i = 1;i <= k;i++)///k * k个格子依次做为起点构成新的k宫格 也就是移动k宫格 看看有几个黑色点包含在内 （默认黑色 可互换） for(int j = 1;j <= k;j++) { ///斜对角的k宫格是相同颜色 2k * 2k区域最多有五个这样的区域 sum = num(0,0,i,j) + num(i,j,k + i,k + j) + num(k + i,k + j,2 * k,2 * k) + num(k + i,0,2 * k,j) + num(0,k + j,i,2 * k); ans = max(ans,max(sum,n - sum));///黑白色可以互换 } printf("%d ",ans); }