2017-07-05

【bzoj4644】经典傻逼题

线性基重学系列第二题

AC通道

将边权异或到点上，这样问题就转化成了选择若干点使得他们的异或和最大

至于每次添边时询问，线段树分治即可

写这道题练习bitset的用法，岂不美哉

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 1050
using namespace std;
typedef bitset<MAXN> Int;
int Case,n,m,L,last[MAXN];
Int value[MAXN],Mat[MAXN];
vector<Int>data[MAXN<<1];
inline int read(){
	int x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
inline Int Read(){
	Int ret;  ret.reset();
	char ch[MAXN]; scanf("%s",ch+1); int len=strlen(ch+1);
	for(int i=1;i<=len;++i) ret[len-i]=ch[i]-'0';
	return ret;
}
inline void output(Int ans){
	char vout[MAXN];  int cur=0;
	if(ans.none()) puts("0");
	else{
		for(int i=L;i>=0;--i)if(ans[i]){
			for(int j=i;j>=0;--j) vout[cur++]=ans[j]+'0';
			break;
		}
		vout[cur++]='\0'; puts(vout);
	}
}
void updata(int p,int l,int r,int x,int y,Int v){
	if(x<=l&&y>=r){
		data[p].push_back(v);
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) updata(p<<1,l,mid,x,y,v);
	if(y>mid)  updata(p<<1|1,mid+1,r,x,y,v);
}
void dfs(int p,int l,int r,Int *Mat){
	Int Lmat[MAXN],Rmat[MAXN],temp[MAXN];
	memcpy(temp,Mat,sizeof(temp));
	for(int i=0;i<data[p].size();++i)for(int j=L;j>=0;--j)if(data[p][i][j]){
		if(!temp[j].none()) data[p][i]^=temp[j];
		else{
			temp[j]=data[p][i];
			for(int k=j-1;k>=0;--k)if(!temp[k].none()&&temp[j][k])temp[j]^=temp[k];
			for(int k=j+1;k<=L;++k)if(!temp[k].none()&&temp[j][k])temp[k]^=temp[j];
			break;
		}
	}
	memcpy(Lmat,temp,sizeof(Lmat));
	memcpy(Rmat,temp,sizeof(Rmat));
	if(l==r){
		Int ans; ans.reset();
		for(int i=L;i>=0;--i)if(!ans[i])ans^=temp[i];
		output(ans);
		return;
	}
	int mid=(l+r)>>1;
	dfs(p<<1,l,mid,Lmat);
	dfs(p<<1|1,mid+1,r,Rmat);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	Case=read();  n=read();  m=read();  L=1000;
	for(int i=1;i<=m;++i){
		int x=read(),y=read();Int v=Read();
		if(x==y) continue;
		if(last[x]) updata(1,1,m,last[x],i-1,value[x]);
		if(last[y]) updata(1,1,m,last[y],i-1,value[y]);
		last[x]=i; value[x]^=v;
		last[y]=i; value[y]^=v;
	}
	for(int i=1;i<=n;++i)updata(1,1,m,last[i],m,value[i]);
	dfs(1,1,m,Mat);
	return 0;
}

本文标题:【bzoj4644】经典傻逼题

文章作者:chty

发布时间:2017年07月05日 - 19时21分

最后更新:2017年07月05日 - 19时27分

许可协议:本文为博主原创，未经许可不得转载。