首页 > 代码库 > Matrix

Matrix

                          Matrix

 

题目:

   查看武森路文。

算法:

  用二维数状水过。模板题。

 

/*

   浅谈信息学竞赛中的  “0”  和“1” 二进制思想在信息学竞赛中的应用


*/

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

#define lowbit(x)(x&-x)
const int MAXN = 1000 + 10;
int n,c[MAXN][MAXN];

void add(int x,int y,int val){
    while(x <= n){
        int i = y;
        while(i <= n){
            c[x][i] += val;
            i += lowbit(i);
        }
        x += lowbit(x);
    }
}

int sum(int x,int y){
    int res = 0;
    while(x > 0){
        int i = y;
        while(i > 0){
            res += c[x][i];
            i -= lowbit(i);
        }
        x -= lowbit(x);
    }
    return res;
}

int main()
{
    int T,Q;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&Q);
        memset(c,0,sizeof(c));
        char ask[3];
        int x1,y1,x2,y2;
        while(Q--){
            scanf("%s",ask);
            if(ask[0] == 'C'){
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                add(x1,y1,1);
                add(x1,y2 + 1,1);
                add(x2 + 1,y1,1);
                add(x2 + 1,y2 + 1,1);
            } else {
                scanf("%d%d",&x1,&y1);
                int ans = sum(x1,y1);
                printf("%d\n",ans % 2);
            }
        }
    }
    return 0;
}













/*

   浅谈信息学竞赛中的  “0”  和“1” 二进制思想在信息学竞赛中的应用


*/

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

#define lowbit(x)(x&-x)
const int MAXN = 1000 + 10;
int n,c[MAXN][MAXN];

void add(int x,int y,int val){
    while(x <= n){
        int i = y;
        while(i <= n){
            c[x][i] += val;
            i += lowbit(i);
        }
        x += lowbit(x);
    }
}

int sum(int x,int y){
    int res = 0;
    while(x > 0){
        int i = y;
        while(i > 0){
            res += c[x][i];
            i -= lowbit(i);
        }
        x -= lowbit(x);
    }
    return res;
}

int main()
{
    int T,Q;
    scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&Q);
        memset(c,0,sizeof(c));
        char ask[3];
        int x1,y1,x2,y2;
        while(Q--){
            scanf("%s",ask);
            if(ask[0] == 'C'){
                scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                add(x1,y1,1);
                add(x1,y2 + 1,1);
                add(x2 + 1,y1,1);
                add(x2 + 1,y2 + 1,1);
            } else {
                scanf("%d%d",&x1,&y1);
                int ans = sum(x1,y1);
                printf("%d\n",ans % 2);
            }
        }
    }
    return 0;
}


 

Matrix