某天我觉得一切题目都是那么不可做，于是百度了一下“傻逼题”……
题目大意：对于图中的任意一个点集（可以为空或者全集），所有恰好有一个端点在这个点集中的边组成的集合被称为割。一个割的权值被定义为所有在这个割上的边的异或和。现在有一张一开始只有n个点的图，m次操作，每次加入一条边并询问当前最大的割的权值。（n<=500，m<=1000，边权用二进制表示，二进制数长度L<=1000）
思路：把选割看成把图分成两部分，“脚踏两只船”的边就是割，考虑选每个点的贡献，实际上就是使答案异或上连向这个点的所有边的异或和，这样每条边如果两端点都选或都不选贡献为0，只有一个选贡献就是这个边权。问题转化成n个数，一开始都是0，每次把其中两个异或上一个数，询问当前最大的子集异或和。考虑用线性基解决，由于线性基只支持插入，我们用线段树分治解决。暴力计算二进制数复杂度有点大，用bitset加速即可。总复杂度O(mlogm*L^2/32)。
#include<cstdio> #include<cstring> #include<vector> #include<bitset> using namespace std; inline int read() { int x;char c; while((c=getchar())<'0'||c>'9'); for(x=c-'0';(c=getchar())>='0'&&c<='9';)x=(x<<3)+(x<<1)+c-'0'; return x; } #define MN 500 #define ML 1000 bitset<ML> a[MN+5],w,z[ML+5],ans[ML+5]; struct node{int l,r;vector<bitset<ML> > v;}t[ML*4+5]; char s[ML+5]; int l[MN+5]; vector<int> v[ML*4+5]; void build(int k,int l,int r) { if((t[k].l=l)==(t[k].r=r))return; int mid=l+r>>1; build(k<<1,l,mid);build(k<<1|1,mid+1,r); } void ins(int k,int l,int r,bitset<ML>&x) { if(t[k].l==l&&t[k].r==r){t[k].v.push_back(x);return;} int mid=t[k].l+t[k].r>>1; if(r<=mid)ins(k<<1,l,r,x); else if(l>mid)ins(k<<1|1,l,r,x); else ins(k<<1,l,mid,x),ins(k<<1|1,mid+1,r,x); } void dfs(int x) { int i,j; for(i=0;i<t[x].v.size();++i) for(j=ML;j--;)if(t[x].v[i][j]) if(z[j][j])t[x].v[i]^=z[j]; else{z[j]=t[x].v[i];v[x].push_back(j);break;} if(t[x].l<t[x].r)dfs(x<<1),dfs(x<<1|1); else for(j=ML;j--;)if(!ans[t[x].l][j]&&z[j][j])ans[t[x].l]^=z[j]; for(i=0;i<v[x].size();++i)z[v[x][i]].reset(); } int main() { int n,m,i,j,k,x,y; read();n=read();m=read(); build(1,1,m); for(i=1;i<=m;++i) { x=read();y=read();scanf("%s",s);k=strlen(s)-1; for(j=0;j<=k;++j)w[k-j]=s[j]-'0';for(;j<ML;++j)w[j]=0; if(l[x]+1<i)ins(1,l[x]+1,i-1,a[x]);a[x]^=w;l[x]=i-1; if(l[y]+1<i)ins(1,l[y]+1,i-1,a[y]);a[y]^=w;l[y]=i-1; } for(i=1;i<=n;++i)if(l[i]<m)ins(1,l[i]+1,m,a[i]); dfs(1); for(i=1;i<=m;++i) { for(j=ML;--j;)if(ans[i][j])break; for(;j>=0;--j)x=ans[i][j],printf("%d",x);puts(""); } }