首页 > 代码库 > poj 2155 Matrix

poj 2155 Matrix

2024-07-24 03:04:23   218人阅读

http://poj.org/problem?id=2155

题意：提供一个M*N的矩阵，其中每一个格子中的数不是1就是0，初始时每一个格子的值为0，我们可以修改这个矩阵中的数字，每次给出矩阵的左上角坐标(x1,y1)，以及右下角的坐标(x2,y2)，并且将矩阵中的数字全部取反（原来是1现在变成0，原来是0现在变成1）,还可以每次查询第x行第y列的格子中的数字是什么。

思路：用树状数组，每次插入，在(x1,y1),(x1,y2+1),(x2+1,y1),(x2+1,y2+1)格子内加1，查询的时候求出sum(x,y)就可以。证明参考 <<浅谈信息学竞赛中的““0”和“1”>>这篇论文，作者：武森。

 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 20000 5 using namespace std; 6  7 int x; 8 int n,t; 9 int x1,y1,x2,y2;10 int c[1001][1001];11 12 int low_bit(int x)13 {14     return x&(-x);15 }16 17 void update(int x,int y,int m)18 {19     while(x<=n)20     {21         int yy=y;22         while(yy<=n)23         {24             c[x][yy]+=m;25             yy+=low_bit(yy);26         }27         x+=low_bit(x);28     }29 }30 31 int sum(int x,int y)32 {33     int sum1=0;34     while(x>=1)35     {36         int yy=y;37         while(yy>=1)38         {39             sum1+=c[x][yy];40             yy-=low_bit(yy);41         }42         x-=low_bit(x);43     }44     return sum1;45 }46 47 int main()48 {49     scanf("%d",&x);50     while(x--)51     {52         memset(c,0,sizeof(c));53         scanf("%d%d",&n,&t);54         getchar();55         for(int i=1; i<=t; i++)56         {57             char ch;58             scanf("%c",&ch);59             if(ch==‘C‘)60             {61                 scanf("%d%d%d%d",&x1,&y1,&x2,&y2);62                 update(x1,y1,1);63                 update(x1,y2+1,1);64                 update(x2+1,y1,1);65                 update(x2+1,y2+1,1);66             }67             else  if(ch==‘Q‘)68             {69                 scanf("%d%d",&x1,&y1);70                 printf("%d\n",sum(x1,y1)%2);71             }72             getchar();73         }74         if(x>0) printf("\n");75     }76     return 0;77 }
View Code

 

poj 2155 Matrix


联系
我们