over 3 years ago

BUG:为什么((k>>64-i)&1)) 与if (1<<(64-i)&x)的结果不一样?

在花了将近一个下午的时间看题解,一个晚上的时间写+调之后....终于过了【有一个bug不知道为什么TAT】

类似bzoj2115的思路。

首先,逆向思维,删边变加边

在这里gauss得到了线性基【最好去看看系统论述……】,如果是环就转为基底,树边就留着到时一起判

还要注意每个数组的范围……

再想想那个bug吧……

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<set>
using namespace std;
const int maxn=5005,maxm=40005,maxq=20005;
int next[maxm]={0},point[maxn]={0},v[maxm]={0},query[maxq]={0};
long long w[maxm]={0},ans[maxq]={0},tree[maxn]={0},c[66]={0},d[maxn]={0};
struct wide{int x,y;long long z;} p[maxm];
bool color[maxm]={0},can[maxn]={0};
set<long long> ck;
int n,m,widen=0,q,addc=0,addt=0,cn=0,tn=0;
int readln()
{
char c=getchar();int bj=1,result=0;
while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
if (c=='-') bj=-1,c=getchar();
while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
return result*bj;
}
long long readlong(){
char c=getchar();int bj=1;long long result=0;
while (c!='-'&&!(c<='9'&&c>='0')) c=getchar();
if (c=='-') bj=-1,c=getchar();
while (c<='9'&&c>='0') result=result*10+c-'0',c=getchar();
return result*bj;
}
void addedge(int x,int y,long long z)
{
widen++;next[widen]=point[x];point[x]=widen;v[widen]=y;w[widen]=z;
widen++;next[widen]=point[y];point[y]=widen;v[widen]=x;w[widen]=z;
}
void addtree(long long x) {tree[++tn]=x;addt++;}
void addcircle(long long x)
{
for (int i=1;i<=64;i++)
if ((x>>(64-i)&1)&&c[i]) x^=c[i];
for (int i=1;i<=64;i++)
if (x>>(64-i)&1) {c[i]=x;cn++;addc++;break;}
}
void dfs(int x,long long value)
{
can[x]=true;d[x]=value;
for (int k=point[x];k!=0;k=next[k])
if (can[v[k]]) {addcircle(d[x]^d[v[k]]^w[k]);}
else {addtree(value^w[k]);dfs(v[k],value^w[k]); }
}
bool check(long long k)
{
for (int i=1;i<=64;i++)
if(c[i]&&((k>>64-i)&1)) k=k^c[i];//if (1<<(64-i)&x)?
if(k&&ck.find(k)==ck.end()) {ck.insert(k);return 1;}
return 0;
}
long long ask()
{ int i,temp,start;
if (!addc)//这里算是一个小优化,如果上次判断到这次之间没有加基底,那么上次的set可以重复使用,只需要加入新的树边就可以了
{
start=temp=tn-addt;
for (i=tn-addt+1;i<=tn;i++)
if (check(tree[i])) tree[++temp]=tree[i];
tn=temp;addt=0;
ans[q]=ans[q+1]+(tn-start)*(1ll<<cn);
}
else
{
addc=addt=0;
ck.clear();temp=0;
for (i=1;i<=tn;i++)
if (check(tree[i])) tree[++temp]=tree[i];
tn=temp;
ans[q]=(temp+1)*(1ll<<cn)-1;//+1是因为空的树边也可以用,只需要沿着d[i],d[j],w[i,j]就可以走一个外环
}
}
int main()
{
int i,j,k,l,x,y;
memset(color,true,sizeof(color));
n=readln();m=readln();l=q=readln();
for (i=1;i<=m;i++){p[i].x=readln();p[i].y=readln();p[i].z=readlong();}
for (i=1;i<=q;i++){query[i]=readln();color[query[i]]=false;}
for (i=1;i<=m;i++)
if (color[i]) addedge(p[i].x,p[i].y,p[i].z);
dfs(1,0);
ask();
while (q--)
{
x=p[query[q+1]].x;y=p[query[q+1]].y;
addedge(x,y,p[query[q+1]].z);
if (can[x]||can[y])
{
if (can[x]&&can[y]) addcircle(d[x]^d[y]^p[query[q+1]].z);
else
{
if (can[x]) dfs(x,d[x]);else dfs(y,d[y]);
}
}
ask();
}
for (i=0;i<=l;i++) printf("%lld\n",ans[i]);
}
← 【bzoj3203】【凸包】【三分】【dp】保护出题人 【bzoj3578】【thinking】【set】GTY的人类基因组计划2 →
 
comments powered by Disqus