题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4644
一条边的两个端点只能选其中之一，如果两个都选，这条边就没有贡献了。
这不就是异或么？
所以我们把每条边的权值异或到点上，然后用线段树维护时间，把每条边所影响的时间都找出来，在线段树中标记出来，然后在线段树上进行dfs，由于线性基不能回溯，所以我们每次下传的时候带着线性基一起下传（就相当于复制一个），因为是对时间维护的线段树，所以扫到叶子节点时就可以输出了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
#include<bits/stdc++.h> #define maxn 1010 #define pb push_back #define bit bitset<1010> using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(!isdigit(c)){if(c=='-')y=-y;c=getchar();} while(isdigit(c))x=x*10+c-'0',c=getchar(); return x*y; } char s[maxn]; inline void read(bit &b){ scanf("%s",s); int len=strlen(s); b.reset(); reverse(s,s+len); for(int i=0; i<len; i++)b[i]=s[i]-'0'; } struct LB{ bit a[1010]; LB(){memset(a,0,sizeof(a));} void add(bit x){ for(int i=1000; i>=0; i--){ if(x[i]){ if(a[i].count()){x^=a[i];continue;} a[i]=x; for(int j=i-1; j>=0; j--)if(a[i][j])a[i]^=a[j]; for(int j=i+1; j<=1000; j++)if(a[j][i])a[j]^=a[i]; break; } } } bit cal(){ bit ret; ret.reset(); for(int i=0; i<=1000; i++)ret^=a[i]; return ret; } void print(){ bit b=cal(); int i; for(i=1000; i>=0; i--)if(b[i])break; if(i<0)printf("0"); for(; i>=0; i--)putchar(b[i]?'1':'0'); puts(""); } }; struct node{ int l,r; vector<bit>v; }t[maxn*4]; int n,m,tot; int a[maxn],b[maxn],ti[maxn]; bit now[maxn],tmp; void build(int x,int l,int r){ t[x].l=l; t[x].r=r; if(l==r)return; int mid=(l+r)/2; build(x*2,l,mid); build(x*2+1,mid+1,r); } void add(int x,int l,int r,bit val){ if(t[x].l==l && t[x].r==r){t[x].v.pb(val);return;} int mid=(t[x].l+t[x].r)/2; if(r<=mid)add(x*2,l,r,val); else if(l>mid)add(x*2+1,l,r,val); else add(x*2,l,mid,val),add(x*2+1,mid+1,r,val); } inline void init(){ rd(),n=rd(),m=rd(); build(1,1,m); for(int i=1; i<=m; i++){ int x=rd(),y=rd(); read(tmp); if(x==y)continue; if(ti[x])add(1,ti[x],i-1,now[x]); ti[x]=i;now[x]^=tmp; if(ti[y])add(1,ti[y],i-1,now[y]); ti[y]=i;now[y]^=tmp; } for(int i=1; i<=n; i++){ if(ti[i]<=m && ti[i])add(1,ti[i],m,now[i]); } } void solve(int x,LB now){ for(int i=0; i<t[x].v.size(); i++)now.add(t[x].v[i]); if(t[x].l==t[x].r){now.print();return;} solve(x*2,now); solve(x*2+1,now); } int main(){ init(); LB now; solve(1,now); return 0; } |