[线性基] 线性基两例

线性基两例

例 [BJWC2011]元素

贪心，往线性基里插 插得进去有贡献

#include<bits/stdc++.h> using namespace std; #define in Read() typedef long long ll; ll in{ ll i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int N=1e3+5; int n,ans; ll d[100]; struct node{ ll ele; int val; friend inline bool operator < (const node &a,const node &b){ return a.val>b.val; } }a[N]; bool insert(ll x){ for(int i=62;i>=0;--i) if((x>>i)&1){ if(d[i]) x^=d[i]; else{ d[i]=x; return true; } } return false; } int main(){ n=in; for(int i=1;i<=n;++i) a[i].ele=in,a[i].val=in; sort(a+1,a+n+1); for(int i=1;i<=n;++i){ if(insert(a[i].ele)) ans+=a[i].val; } printf("%d\n",ans); return 0; }

例 [TJOI2008]彩灯

显然开关灯是异或运算 整成数，套线性基板子 最后有$ans$基就有$2^{ans}$方案 但是不知道为什么我线性基memset之后d[60]位置上总是有一个两万多的数

#include<bits/stdc++.h> using namespace std; #define in Read() typedef long long ll; ll in{ ll i=0,f=1;char ch=0; while(!isdigit(ch)&&ch!='-') ch=getchar(); if(ch=='-') ch=getchar(),f=-1; while(isdigit(ch)) i=(i<<1)+(i<<3)+ch-48,ch=getchar(); return i*f; } const int mod=2008; int n,m,ans; ll d[60]; char opt[60]; void insert(ll x){ for(int i=55;i>=0;--i){ if((x>>i)&1){ if(d[i]) x^=d[i]; else{ d[i]=x; break; } } } } int main(){ n=in,m=in; for(int i=1;i<=m;++i){ scanf("%s",opt); ll x=0; for(int j=0;j<n;++j){ if(opt[j]=='O') x^=(1ll<<j); } insert(x); } for(int i=55;i>=0;--i) if(d[i]) ++ans; printf("%lld\n",(1ll<<ans)%mod); return 0; }

另外有一道四川的题 可以参考我的博客 写得挺详细的，线性基小白可以看一下