BZOJ2338:[HNOI2011]数矩形 暴力+计算几何
BZOJ2322:[BeiJing2011]梦想封印(&&BZOJ3793) 线性基

BZOJ3569:DZY Loves Chinese II(&&BZOJ3563) 高斯消元+构造

shinbokuow posted @ Feb 03, 2015 03:02:35 PM in BZOJ with tags 高斯消元 构造 , 2374 阅读

思路:

首先构造出原无向图的一棵生成树,然后就有一些非树边以及一些树边了吧.

给非树边随机一个unsignde long long的权值,并令每个树边的权值等于覆盖这条树边的所有非树边权值的异或和.

考虑删去哪些边之后可以使得原图不连通.

如果只删掉非树边显然是没用的.

那么我们必须删掉一条树边,以及覆盖这条树边的所有非树边!注意到这些边权值的异或和正好为0,因此问题转化为存不存在一个异或和为0的子集.于是高斯消元水.

时间复杂度\(O(n+64kq)\).

 

另外I可以拿一个有趣的方法水过...详情见代码.

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdlib>
using namespace std;
 
typedef unsigned long long LLU;
 
inline LLU get(){
    LLU res=1;for(int i=1;i<=4;++i)res*=rand();return res;
}
 
#define N 100010
#define M 500010
int head[N],next[M<<1],end[M<<1];LLU f[M<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
int pa[N];
LLU v[N];
inline void dfs(int x){
    for(int j=head[x];j;j=next[j])if(!pa[end[j]]&&end[j]!=1)pa[end[j]]=x,dfs(end[j]);
}
inline void dfs2(int x){
    for(int j=head[x];j;j=next[j])
        if(pa[end[j]]==x)
            dfs2(end[j]),v[x]^=v[end[j]];
    for(int j=head[x];j;j=next[j])
        if(pa[end[j]]==x)
            f[(j+1)/2*2-1]=f[(j+1)/2*2]=v[end[j]];
}
 
LLU ins[64];
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    int a,b;for(i=1;i<=m;++i)scanf("%d%d",&a,&b),make(a,b);
     
    dfs(1);
    LLU now;
    for(i=1;i<=n;++i)for(j=head[i];j;j=next[j])if(i!=pa[end[j]]&&pa[i]!=end[j]){
        now=get();f[(j+1)/2*2-1]^=now,f[(j+1)/2*2]^=now,v[i]^=now,v[end[j]]^=now;
    }
    dfs2(1);
     
    int lans=0,q,t,x;LLU tmp;scanf("%d",&q);
    while(q--){
        scanf("%d",&t);
        memset(ins,0,sizeof ins);
        bool ok=1;
        for(i=1;i<=t;++i){
            scanf("%d",&x),tmp=f[2*(x^=lans)];
            for(j=63;j>=0;--j)if((tmp>>j)&1){
                if(!ins[j]){ins[j]=tmp;break;}else tmp^=ins[j];
            }
            if(!tmp)ok=0;
        }
        if(ok)puts("Connected"),++lans;else puts("Disconnected");
    }
     
    return 0;
}
#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
#define M 500010
int head[N],next[M<<1],end[M<<1],ban[M<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
char s[10010];
 
int stk[16<<1],top;
 
bool vis[N];
void dfs(int x){
    vis[x]=1;for(int j=head[x];j;j=next[j])if(!ban[j]&&!vis[end[j]])dfs(end[j]);
}
 
int sav[20],num;
inline bool digit(char c){
    return c>='0'&&c<='9';
}
void get(){
    gets(s);int len=strlen(s);
    num=0;
    int tmp,i,j;
    for(i=0;i<len;){
        if(digit(s[i])){
            tmp=s[i]-'0';
            for(j=i+1;j<len&&digit(s[j]);++j)tmp=10*tmp+s[j]-'0';
            sav[++num]=tmp,i=j;
        }else++i;
    }
}
 
int lans[50010];
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j;
    int a,b;for(i=1;i<=m;++i)scanf("%d%d",&a,&b),make(a,b);
     
    int Q;scanf("%d",&Q);gets(s);
     
    for(i=1;i<=Q;++i){
        get();
        lans[i-1]=(num-1)^sav[1];
    }
     
    for(i=1;i<Q;++i)if(lans[i]>lans[i-1])puts("Connected");else puts("Disconnected");
     
    for(i=2;i<=num;++i)sav[i]^=lans[Q-1],ban[2*sav[i]-1]=ban[2*sav[i]]=1;
    int cnt=0;for(i=1;i<=n;++i)if(!vis[i])dfs(i),++cnt;
    if(cnt==1)puts("Connected");else puts("Disconnected");
     
    return 0;
}
Avatar_small
wyfcyx 说:
May 05, 2015 07:46:24 PM

窝的背景消失了QoQ...然而并不知道为什么

蒟蒻 说:
May 05, 2015 07:47:41 PM

@wyfcyx: 没消失啊

Avatar_small
wyfcyx 说:
May 05, 2015 08:18:46 PM

@蒟蒻: 求真人联系...窝现在是win10的IE,于是之前的设定就失效了?

蒟蒻 说:
May 05, 2015 08:20:01 PM

不造啊,我这边能看到啊,怎么联系

Platypus 说:
May 18, 2015 12:01:05 PM

@wyfcyx: 真相是chuantu.biz上面的图片链接挂掉了,我这里显示404,能看到图的也只是缓存,清掉就没了,重新挂一遍吧...

蒟蒻 说:
May 18, 2015 02:22:30 PM

@Platypus: 那为什么现在也没看到

Platypus 说:
May 18, 2015 02:50:53 PM

@蒟蒻: 因为http://chuantu.biz/t/62/1422200215x954497743.jpg 这个链接挂了啊...= = 你用Chrome开发者选项的Network项可以很容易地发现它挂了...

蒟蒻 说:
May 18, 2015 02:52:11 PM

@Platypus: 哦哦,需要博主重挂上去吧


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter