他人博客
例题
Luogu P3812【模板】线性基
真的只是模板,上线性基简单写法:
#include<bits/stdc++.h>
using namespace std;
#define int long long
int const MAXN=1000,MAXL=60;
int n;
int p[MAXN];
struct LinearBasis{
long long a[MAXL+1];
void insert(int x){
for(int i=MAXL;i>=0;i--){
if( !(x & (1LL<<i) ) )continue;
if(!a[i])return (void)(a[i]=x);
x ^= a[i];
}
}
int query_max(){
int ans=0;
for(int i=MAXL;i>=0;i--)ans=max(ans,ans^a[i]);
return ans;
}
}LB;
signed main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&p[i]);
LB.insert(p[i]);
}
printf("%lld\n",LB.query_max());
return 0;
}
Nowcoder 2019NOIP暑假7天营Day4 清新题
就比模板加了一个合并操作
#include<bits/stdc++.h>
using namespace std;
int const MAXN=1e5+10,MAXL=20;
int n,tot,m,ans;
int h[MAXN],p[MAXN];
struct LB{
int a[MAXL],sum;
void insert(int x){
for(int i=MAXL;i>=0;i--){
if(x & (1LL<<i)){
if(!a[i]){a[i]=x;return;}
x^=a[i];
}
}
}
void get_max(){
sum=0;
for(int i=MAXL;i>=0;i--)sum=max(sum,sum^a[i]);
}
void merge(const LB &b){
for(int i=0;i<=MAXL;i++)if(b.a[i])insert(b.a[i]);
}
}lb[MAXN];
struct edge{
int to,next;
}e[MAXN<<1+1];
void add(int u,int v){
e[++tot].to=v,e[tot].next=h[u],h[u]=tot;
}
void dfs(int rt,int fa){
lb[rt].insert(p[rt]);
for(int i=h[rt];i;i=e[i].next){
if(e[i].to!=fa){
dfs(e[i].to,rt);
lb[rt].merge(lb[e[i].to]);
}
}
lb[rt].get_max();
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n-1;i++){
int x,y;
scanf("%d%d",&x,&y);
add(x,y);add(y,x);
}
for(int i=1;i<=n;i++)scanf("%d",&p[i]);
dfs(1,-1);
scanf("%d",&m);
for(int i=1;i<=m;i++){
int x;scanf("%d",&x);
printf("%d\n",lb[x].sum);
}
return 0;
}
Luogu 幸运数字
到时候填