BestCoder Round #56 1002 Clarke and problem 1003 Clarke and puzzle （dp，二维bit或线段树）

今天第二次做BC，不习惯hdu的oj，CE过2次。。。

1002 Clarke and problem

和Codeforces Round #319 (Div. 2) B Modulo Sum思路差不多，

将a[i]对p取余数，最后得到0的方案总数即使答案，dp转移，一个状态方案总数等于能转移过来的状态方案数之和

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

using namespace std;

#define PB push_back

#define MP make_pair

#define fi first

#define se second

#define cer(x) cout<<#x<<'='<<endl

typedef long long ll;

const int maxn = ;

int dp[][maxn];

//#define LOCAL

const int MOD = 1e9+;

int main()

{

#ifdef LOCAL

    freopen("in.txt","r",stdin);

#endif

    int T; scanf("%d",&T);

    while(T--){

        int n,p; scanf("%d%d",&n,&p);

        //fill(dp[0],dp[0]+p,0);

        memset(dp[],,sizeof(dp[]));

        dp[][] = ;

        for(int i = ; i < n; i++){

            int c = i&,nx = (i&)^;

            //fill(dp[nx],dp[nx]+p,0);

            memcpy(dp[nx],dp[c],sizeof(dp[nx]));

            int a; scanf("%d",&a);

            a %= p; if(a<) a += p; //G++编译器负数取模还是负数，在这里RE了几次

            for(int j = ; j < p; j++){

                if(dp[c][j]){

                    int t = (j+a)%p;

                    dp[nx][t] = (dp[nx][t]+ dp[c][j])%MOD;

                }

            }

        }

        printf("%d\n",dp[n&][]);

    }

    return ;

}

1003 Clarke and puzzle

熟悉NIM游戏的结论和SG函数思路上并不难。

卡时间卡的太紧了，按照官方题解做法980ms过。。。把memset换成for，890ms

自信地写了个二维线段树被卡。写BIT还遇到一些奇怪的错误。

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

using namespace std;

#define PB push_back

#define MP make_pair

#define fi first

#define se second

#define cer(x) cout<<#x<<'='<<endl

typedef long long ll;

const int maxn = ;

int C[maxn][maxn],n,m,c[maxn][maxn];

#define lb(x) ((x)&-(x))

int sum(int x,int y){

    int r = ;

    for(int i=x;i>;i-=lb(i)) //for(; x>0; x-=lb(x)) 奇怪的错误，写成这样T了

        for(int j=y;j>;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 LOCAL

int 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 = ; i <= n; i++){

            //fill(C[i]+1,C[i]+1+m,0);

            for(int j = ; j <= m; j++) C[i][j] = ;

        }

        for(int i = ; i <= n; i++){

            for(int j = ; j <= m; j++){

                scanf("%d",c[i]+j);

                add(i,j,c[i][j]);

            }

        }

        for(int i = ; i < q; i++){

            int op; scanf("%d",&op);

            if(op == ){

                int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2);

                puts(sum(x2,y2)^sum(x2,y1-)^sum(x1-,y2)^sum(x1-,y1-)?"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 ;

}

重新改了时限后二维线段树过了

#include<cstdio>

#include<iostream>

#include<string>

#include<cstring>

#include<queue>

#include<vector>

#include<stack>

#include<vector>

#include<map>

#include<set>

#include<algorithm>

using namespace std;

#define PB push_back

#define MP make_pair

#define fi first

#define se second

#define cer(x) cout<<#x<<'='<<endl

typedef long long ll;

const int maxn = <<,N = ;

int sx[maxn][maxn],n,m;

int c[N][N];

int xo,xleaf,x1,y1,x2,y2,x,y,v,vsx;

#define lid (id<<1)

#define rid (id<<1|1)

void query1D(int id = ,int l = ,int r = m)

{

    if(y1 <= l && r <= y2){

        vsx ^= sx[xo][id];

    }else {

        int mid = (l+r)>>;

        if(y1 <= mid) query1D(lid,l,mid);

        if(mid < y2) query1D(rid,mid+,r);

    }

}

void query2D(int id = ,int l = ,int r = n)

{

    if(x1 <= l && r <= x2) { xo = id; query1D(); }

    else {

        int mid = (l+r)>>;

        if(x1 <= mid) query2D(lid,l,mid);

        if(mid < x2) query2D(rid,mid+,r);

    }

}

void modify1D(int id = , int l = , int r = m)

{

    if(l == r){

        if(xleaf) { sx[xo][id] = v; return; }

        sx[xo][id] = sx[xo<<][id]^sx[xo<<|][id];

    }else {

        int mid = (l+r)>>;

        if(y <= mid) modify1D(lid,l,mid);

        else modify1D(rid,mid+,r);

        sx[xo][id] = sx[xo][lid]^sx[xo][rid];

    }

}

void modify2D(int id = , int l = , int r = n)

{

    if(l==r) { xo = id; xleaf = ; modify1D(); }

    else {

        int mid = (l+r)>>;

        if(x<=mid) modify2D(lid,l,mid);

        else modify2D(rid,mid+,r);

        xo = id; xleaf = ; modify1D();

    }

}

void build1D(int id = ,int l = ,int r = m)

{

    if(l == r) {

        if(xleaf) { sx[xo][id] = c[x][l]; return; }

        sx[xo][id] = sx[xo<<][id]^sx[xo<<|][id];

    }

    else {

        int mid = (l+r)>>,lc = lid,rc = rid;

        build1D(lc,l,mid);

        build1D(rc,mid+,r);

        sx[xo][id] = sx[xo][lc]^sx[xo][rc];

    }

}

void build2D(int id = , int l = , int r = n)

{

    if(l == r){ xo = id; xleaf = ; x = l; build1D(); }

    else {

        int mid = (l+r)>>;

        build2D(lid,l,mid);

        build2D(rid,mid+,r);

        xo = id; xleaf = ; build1D();

    }

}

inline int read()

{

    char c;

    while((c=getchar())<''||c>'');

    int ret=c-'';

    while((c = getchar())>=''&&c<='')  ret = ret*+(c-'');

    return ret;

}

//#define LOCAL

int 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 = ; i <= n; i++){

            for(int j = ; j <= m; j++){

                c[i][j] = read();

            }

        }

        build2D();

        while(q--){

            if(read() == ){

                x1 = read(); y1= read(); x2 = read(); y2 = read();

                vsx = ;

                query2D();

                puts(vsx?"Yes":"No");

            }else {

                x = read(); y = read(); v = read();

                modify2D();

            }

        }

    }

    return ;

}

巴特西

BestCoder Round #56 1002 Clarke and problem 1003 Clarke and puzzle （dp，二维bit或线段树）

最新文章

热门文章