2015 湘潭大学程序设计比赛（Internet）--E题--烦人的异或

浏览数：35 / 时间：2015年06月09日

烦人的异或
Accepted : 27		Submit : 102
Time Limit : 5000 MS		Memory Limit : 65536 KB

题目描述

如下图，有一N*M的表格，每个格子有一个数字。我们定义主矩形为给出的一对坐标所确定的矩形(该对坐标总是某个矩形的对顶点坐标对)。它最多可产生4个副矩形, 均由主矩形的顶点和表格边界确定。我们需要的是所有阴影部分的数的异或值。

技术分享

上图的x1=3,y1=3,x2=4,y2=4,所以答案就是a11^a12^a21^a22^a15^a16^a25^a26^a33^a34^a43^a44^a51^a52^a61^a62^a55^a56^a65^a66。其中 ‘^‘ 代表异或符号，aij代表第i行第j列的方格中的数字。

输入

第一行是一个整数T(T≤10),表示测试数据组数。每组数据第一行三个整数N,M,Q(0<N,M≤1000,Q≤500000),Q表示有Q组询问。接着输入N行，每行有M个数字，表示表格里的数字(非负整数，且不大于10⁹)。最后有Q行，表示Q个询问，每行包含4个正整数x1,y1,x2,y2(1≤x1≤x2≤N,1≤y1≤y2≤M)。

输出

对于每个查询，输出一行，表示异或结果。

样例输入

样例输出

0
0
0

提示

大量的输入输出，请使用C风格的输入输出；

技术分享

1=2^3^4^整体；

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1050
using namespace std;

int maps[N][N],a[N][N];

int main()
{
    int n,T,m,k,i,j,A,B,C,D,E;
    int x,y,x0,y0,x1,y1,x2,y2;
    scanf("%d",&T);
    while(T--)
    {
        memset(a,0,sizeof(a));
        memset(maps,0,sizeof(maps));
        scanf("%d%d%d",&n,&m,&k);
        for(i=1;i<=n;i++)
        {
            for(j=1;j<=m;j++)
            {
                scanf("%d",&maps[i][j]);
                a[i][j]=a[i-1][j]^a[i][j-1]^a[i-1][j-1]^maps[i][j];
            }
        }
        for(i=0;i<k;i++)
        {
            scanf("%d %d %d %d",&x,&y,&x0,&y0);
            x1=min(x,x0);
            y1=min(y,y0);
            x2=max(x,x0);
            y2=max(y,y0);

            A=a[x1-1][y1-1];
            B=a[x1-1][m]^a[x1-1][y2];
            C=a[n][y1-1]^a[x2][y1-1];
            D=a[n][m]^a[x2][m]^a[n][y2]^a[x2][y2];
            E=a[x2][y2]^a[x1-1][y2]^a[x2][y1-1]^a[x1-1][y1-1];
            printf("%d\n",A^B^C^D^E);
        }
    }

    return 0;
}