本文共 4062 字，大约阅读时间需要 13 分钟。
今天第二次做BC，不习惯hdu的oj，CE过2次。。。
1002 Clarke and problem
和思路差不多，
将a[i]对p取余数，最后得到0的方案总数即使答案，dp转移，一个状态方案总数等于能转移过来的状态方案数之和
#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define PB push_back#define MP make_pair#define fi first#define se second#define cer(x) cout<<#x<<'='<
1003 Clarke and puzzle
熟悉NIM游戏的结论和SG函数思路上并不难。
卡时间卡的太紧了，按照官方题解做法980ms过。。。把memset换成for，890ms
自信地写了个二维线段树被卡。写BIT还遇到一些奇怪的错误。
#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define PB push_back#define MP make_pair#define fi first#define se second#define cer(x) cout<<#x<<'='< 0;i-=lb(i)) //for(; x>0; x-=lb(x)) 奇怪的错误，写成这样T了 for(int j=y;j>0;j-=lb(j)) r ^= C[i][j]; return r;}void add(int x,int y,int val){ for(int i=x;i<=n;i+=lb(i)) for(int j=y;j<=m;j+=lb(j)) C[i][j] ^= val;}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif int T; scanf("%d",&T); while(T--){ int q; scanf("%d%d%d",&n,&m,&q); //memset(C,0,sizeof(C)); for(int i = 1; i <= n; i++){ //fill(C[i]+1,C[i]+1+m,0); for(int j = 1; j <= m; j++) C[i][j] = 0; } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ scanf("%d",c[i]+j); add(i,j,c[i][j]); } } for(int i = 0; i < q; i++){ int op; scanf("%d",&op); if(op == 1){ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); puts(sum(x2,y2)^sum(x2,y1-1)^sum(x1-1,y2)^sum(x1-1,y1-1)?"Yes":"No"); }else { int x,y,v; scanf("%d%d%d",&x,&y,&v); add(x,y,c[x][y]^v); c[x][y] = v; } } } return 0;}
重新改了时限后二维线段树过了
#include #include #include #include #include #include #include #include #include #include #include using namespace std;#define PB push_back#define MP make_pair#define fi first#define se second#define cer(x) cout<<#x<<'='< >1; if(y1 <= mid) query1D(lid,l,mid); if(mid < y2) query1D(rid,mid+1,r); }}void query2D(int id = 1,int l = 1,int r = n){ if(x1 <= l && r <= x2) { xo = id; query1D(); } else { int mid = (l+r)>>1; if(x1 <= mid) query2D(lid,l,mid); if(mid < x2) query2D(rid,mid+1,r); }}void modify1D(int id = 1, int l = 1, int r = m){ if(l == r){ if(xleaf) { sx[xo][id] = v; return; } sx[xo][id] = sx[xo<<1][id]^sx[xo<<1|1][id]; }else { int mid = (l+r)>>1; if(y <= mid) modify1D(lid,l,mid); else modify1D(rid,mid+1,r); sx[xo][id] = sx[xo][lid]^sx[xo][rid]; }}void modify2D(int id = 1, int l = 1, int r = n){ if(l==r) { xo = id; xleaf = 1; modify1D(); } else { int mid = (l+r)>>1; if(x<=mid) modify2D(lid,l,mid); else modify2D(rid,mid+1,r); xo = id; xleaf = 0; modify1D(); }}void build1D(int id = 1,int l = 1,int r = m){ if(l == r) { if(xleaf) { sx[xo][id] = c[x][l]; return; } sx[xo][id] = sx[xo<<1][id]^sx[xo<<1|1][id]; } else { int mid = (l+r)>>1,lc = lid,rc = rid; build1D(lc,l,mid); build1D(rc,mid+1,r); sx[xo][id] = sx[xo][lc]^sx[xo][rc]; }}void build2D(int id = 1, int l = 1, int r = n){ if(l == r){ xo = id; xleaf = 1; x = l; build1D(); } else { int mid = (l+r)>>1; build2D(lid,l,mid); build2D(rid,mid+1,r); xo = id; xleaf = 0; build1D(); }}inline int read(){ char c; while((c=getchar())<'0'||c>'9'); int ret=c-'0'; while((c = getchar())>='0'&&c<='9') ret = ret*10+(c-'0'); return ret;}//#define LOCALint main(){#ifdef LOCAL freopen("in.txt","r",stdin);#endif int T; scanf("%d",&T); while(T--){ n = read(); m = read(); int q = read(); for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ c[i][j] = read(); } } build2D(); while(q--){ if(read() == 1){ x1 = read(); y1= read(); x2 = read(); y2 = read(); vsx = 0; query2D(); puts(vsx?"Yes":"No"); }else { x = read(); y = read(); v = read(); modify2D(); } } } return 0;}
转载于:https://www.cnblogs.com/jerryRey/p/4822542.html
