题意:对于一个N*N的矩阵(2 <= N <= 1000),其中的元素初始为0,执行2种操作,一:C x1 y1 x2 y2——>对矩阵(x1, y1, x2, y)的所有元素求反(0——>1, 1——>0),二:Q x y——>问元素(x, y)的值。
题目链接:http://poj.org/problem?id=2155
——>>好题,好题。。。一般我们都能想到,只要知道位置(x, y)被翻的次数就行。。。对于一个二维区间的修改,我们可以只修改其左闭右开区间的端点。
原理:若其中修改为区间[x1, x2],其左闭右开区间为[x1, x2+1),只在x1和x2+1的位置执行翻转,那么,如果询问x1之前的,本来就没什么修改;如果询问[x1, x2]的,修改了一次,正确;如果询问[x2+1, +oo)的,修改为2次,偶数次修改值不变,正确。
——>>所以,这里只要修改4个点的值,(x1, y1)(修改), (x1, y2+1)(把值变回去), (x2+1, y1)(把值变回去), (x2+1, y2+1)(把值变回去)。。。#^_^。。。
。。。一不小心,让那个空行要求。。。PE了一次。。。T_T~
#include <cstdio> #include <cstring> using namespace std; const int maxn = 1000 + 10; int N; int c[maxn][maxn]; int lowerbit(int x) { return x & (-x); } void add(int x1, int y1, int x2, int y2) { for(int i = x1; i <= N; i += lowerbit(i)) for(int j = y1; j <= N; j += lowerbit(j)) c[i][j]++; for(int i = x1; i <= N; i += lowerbit(i)) for(int j = y2+1; j <= N; j += lowerbit(j)) c[i][j]++; for(int i = x2+1; i <= N; i += lowerbit(i)) for(int j = y1; j <= N; j += lowerbit(j)) c[i][j]++; for(int i = x2+1; i <= N; i += lowerbit(i)) for(int j = y2+1; j <= N; j += lowerbit(j)) c[i][j]++; } int query(int x, int y) { int ret = 0; for(int i = x; i > 0; i -= lowerbit(i)) for(int j = y; j > 0; j -= lowerbit(j)) ret += c[i][j]; return ret % 2; } int main() { int X, T, x1, y1, x2, y2; char op; scanf("%d", &X); while(X--) { scanf("%d%d", &N, &T); memset(c, 0, sizeof(c)); while(T--) { getchar(); op = getchar(); if(op == ‘C‘) { scanf("%d%d%d%d", &x1, &y1, &x2, &y2); add(x1, y1, x2, y2); } else { scanf("%d%d", &x1, &y1); printf("%d\n", query(x1, y1)); } } if(X) puts(""); } return 0; }