[HAOI2018]反色游戏

LOJ有数据就是好

对于每一个联通块(n个点),其他的边一开始随便选,只需要n-1条边就可以确定最终结果.

所以设\(cnt\)为联通块数 , 答案为 \(2^{m-n+cnt}\)

还有就是有解的情况必须是黑点个数为偶数,还要注意有删掉这个点可能使无解变有解,这比从有解变无解更难想

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#define debug(...) fprintf(stderr,__VA_ARGS__)

#define Debug(x) cout<<#x<<"="<<x<<endl

using namespace std;

typedef long long LL;

const int INF=1e9+7;

inline LL read(){

    register LL x=0,f=1;register char c=getchar();

    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}

    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();

    return f*x;

}

const int MAXN=100005;

const int MAXM=200005;

const int mod=1e9+7;

struct Edge{

    int v,w,c,next;

}e[MAXM];

int first[MAXN],Ecnt=1;

inline void Add_edge(int u,int v,int w=0,int c=0){

    e[++Ecnt]=(Edge){v,w,c,first[u]};

    first[u]=Ecnt;

}

int ctg[MAXN],size[MAXN],sub[MAXN],low[MAXN],dfn[MAXN],deg[MAXN],cut[MAXN],pow2[MAXN];

bool flag[MAXN];

char S[MAXN];

int n,m,T,ans,odd,dft,cnt,rt;

inline void clear(){

    memset(size,0,sizeof size);

    memset(deg,0,sizeof deg);

    memset(sub,0,sizeof sub);

    memset(cut,0,sizeof cut);

    memset(low,0,sizeof low);

    memset(dfn,0,sizeof dfn);dft=0;

    memset(first,0,sizeof first);Ecnt=0;

    cnt=0,odd=0;

}

inline void tarjan(int u,int pre=0){

    low[u]=dfn[u]=++dft;

    flag[u]=1;

    size[u]=(S[u]=='1');//算黑点数量

    ctg[u]=rt;//这种情况下方便后面调用

    for(int i=first[u];i;i=e[i].next){

        int v=e[i].v;

        if(!dfn[v]){

            tarjan(v,u);

            size[u]+=size[v];

            if(low[v]>=dfn[u]){

                cut[u]++;

                flag[u]&=((size[v]&1)==0);//子树不合法可以直接标记

                sub[u]+=size[v];

            }

            else low[u]=min(low[u],low[v]);

        }

        else if (v!=pre) low[u]=min(low[u],dfn[v]);

    }

    if(!pre) cut[u]--;//删掉u以后能增加几个连通分量

}

int main(){

    pow2[0]=1;

    for(int i=1;i<MAXN;i++) pow2[i]=(pow2[i-1]<<1)%mod;

    T=read();

    while(T--){

        n=read(),m=read();

        clear();

        for(int i=1;i<=m;i++){

            int x=read(),y=read();

            Add_edge(x,y);

            Add_edge(y,x);

            deg[x]++,deg[y]++;

        }

        scanf("%s",S+1);

        for(int i=1;i<=n;i++) if(!dfn[i]){

            //ctgn++;//这里不适合这样用

            rt=i,cnt++;

            tarjan(i);

            odd+=size[i]&1;

        }

        ans=m-n+cnt;

        printf("%d",odd?0:pow2[ans]);//只要有偶数个黑点就是无解的

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

            if(!deg[i]) printf(" %d",odd-size[i]==0?pow2[ans]:0);//以后复杂题目估计都得写成这样

            else{

                //子树合法              父亲那一块合法                         也许不合法变为合法

                if((flag[i]) && (((size[ctg[i]]-(S[i]=='1')-sub[i])&1)==0) && (odd-(size[ctg[i]]&1)==0))

                    printf(" %d",pow2[ans-deg[i]+1+cut[i]]);

                else printf(" 0");

            }

        }

        printf("\n");

    }

}

巴特西

[HAOI2018]反色游戏

LOJ有数据就是好

最新文章

热门文章