首页 > 代码库 > 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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。