线性基
分类:
IT文章
•
2025-01-31 23:06:37
题意：给定n个数字 问最多能异或出多少个数字
题解: 只需要计算出线性基能插入多少个基底即可 基底选与不选 所以答案为 2^基底数量
![]()
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v) memset(A,v,sizeof A)
/////////////////////////////////////
const int N=1e5+10;
char s[N];
ll n,m,p[N],cnt;
void upnode(ll x)
{
repp(i,50,0)if((x>>i&1))
{
if(!p[i])
{
p[i]=x;cnt++;
break;
}
x^=p[i];
}
}
int main()
{
cin>>n>>m;
rep(i,1,m)
{
scanf("%s",s+1);
ll x=0;
rep(i,1,n)
x=(x<<1ll)+(s[i]=='O');
upnode(x);
}
cout<<(1ll<<cnt)%(1ll*2008);
return 0;
}
View Code
题意：n个魔法师 每个魔法师有两个元素 a b 问最大的集合 使得集合中b的总和最大 且该集合不存在非零子集异或和为0 输出最大b
题解: 排序一下即可 居然是一道紫题 我傻了
![]()
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v) memset(A,v,sizeof A)
/////////////////////////////////////
const int N=1e5+10;
int n,m;
ll p[N],ans;
struct node{ll a,b;}s[N];
bool upnode(ll x)
{
repp(i,62,0)if(x>>i&1)
{
if(!p[i])
{
p[i]=x;
return true;
}
x^=p[i];
}
return false;
}
int main()
{
scanf("%d",&n);
rep(i,1,n)scanf("%lld%lld",&s[i].a,&s[i].b);
sort(s+1,s+1+n,[](node x,node y){return x.b>y.b;});
rep(i,1,n)if(upnode(s[i].a))ans+=s[i].b;
cout<<ans;
return 0;
}
View Code
题意: 给定n个点m条无向边（有边权） 问从1-n的一条路径的最大异或值 可以走重复点和边
题解: 用环来增广链即可
![]()
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v) memset(A,v,sizeof A)
/////////////////////////////////////
const int N=1e5+10;
int n,m,vis[N],pos,head[N];
ll p[N],ans,dis[N];
void upnode(ll x)
{
repp(i,63,0)if((x>>i)&1)
{
if(!p[i]){p[i]=x;return ;}
x^=p[i];
}
}
ll qmax(ll x){repp(i,63,0)x=max(x,x^p[i]);return x;}
struct Edge{int to,nex;ll v;}edge[N<<1];
void add(int a,int b,ll c){edge[++pos]=(Edge){b,head[a],c};head[a]=pos;}
void dfs(int x,ll val)
{
vis[x]=1;dis[x]=val;
for(int i=head[x];i;i=edge[i].nex)
{
int v=edge[i].to;
if(!vis[v])dfs(v,val^edge[i].v);
else upnode(val^dis[v]^edge[i].v);
}
}
int main()
{
cin>>n>>m;
int a,b;ll c;
rep(i,1,m)scanf("%d%d%lld",&a,&b,&c),add(a,b,c),add(b,a,c);
dfs(1,0);
cout<<qmax(dis[n]);
return 0;
}
View Code
题意：第一轮为自定义游戏，取走若干堆石子，第二轮开始为Nim的游戏 问先手最少第一回合拿多少颗石头 保证必赢
题解: 先考虑nim游戏 如果异或和不为0 那么先手必胜 所以可以用线性基排除异或和为零的情况 从大到小插入 不能插入的石堆一开始取掉即可 然后剩下t的石堆一定能组成t个线性基 不可能异或出0的情况
![]()
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v) memset(A,v,sizeof A)
/////////////////////////////////////
const int N=1e5+10;
int n,m;
int p[N];
bool upnode(int x)
{
repp(i,30,0)if((x>>i)&1)
{
if(!p[i]){p[i]=x;return true;}
x^=p[i];
}
return false;
}
int a[N];
ll ans;
int main()
{
int n;cin>>n;
rep(i,1,n)scanf("%d",&a[i]);sort(a+1,a+1+n);
repp(i,n,1)
if(!upnode(a[i]))ans+=a[i];
cout<<ans;
return 0;
}
View Code
![]()
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define repp(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
#define inf 0x3f3f3f3f
#define CLR(A,v) memset(A,v,sizeof A)
//////////////////////////////////
const int N=1e5+10;
struct xxj
{
ll p[65];
void clear(){memset(p,0,sizeof p);}
void upnode(ll x)
{
repp(i,63,0)if(x>>i&1)
{
if(!p[i]){p[i]=x;return;}
x^=p[i];
}
}
ll qmax(){ll ans=0;repp(i,63,0)ans=max(ans,ans^p[i]);return ans;}
}s[N][17],ans;
xxj union1(xxj a,xxj b)
{
rep(i,0,63)if(b.p[i])a.upnode(b.p[i]);
return a;
}
/////////////////////////////////////////////
int pos,head[N],id[N],fa[N],top[N],son[N],siz[N],dep[N],ncnt,n,m,lg[N];
ll node[N];
struct Edge{int to,nex;}edge[N<<1];
void add(int a,int b){edge[++pos]=(Edge){b,head[a]};head[a]=pos;}
xxj getans(int L,int R)
{
int len=lg[R-L+1];
return union1(s[L][len],s[R-(1<<len)+1][len]);
}
void dfs1(int x,int f)
{
fa[x]=f;dep[x]=dep[f]+1;son[x]=0;siz[x]=1;
for(int i=head[x];i;i=edge[i].nex)
{
int v=edge[i].to;
if(v==f)continue;
dfs1(v,x);siz[x]+=siz[v];
if(siz[son[x]]<siz[v])son[x]=v;
}
}
void dfs2(int x,int topf)
{
top[x]=topf;id[x]=++ncnt;s[ncnt][0].upnode(node[x]);
if(son[x])dfs2(son[x],topf);
for(int i=head[x];i;i=edge[i].nex)
{
int v=edge[i].to;
if(v==fa[x]||v==son[x])continue;
dfs2(v,v);
}
}
ll Qmax(int x,int y)
{
ans.clear();
while(top[x]!=top[y])
{
if(dep[top[x]]<dep[top[y]])swap(x,y);
ans=union1(getans(id[top[x]],id[x]),ans);
x=fa[top[x]];
}
if(dep[x]>dep[y])swap(x,y);
ans=union1(getans(id[x],id[y]),ans);
return ans.qmax();
}
////////////////////////////////
int main()
{
cin>>n>>m;int a,b;
rep(i,1,n)scanf("%lld",&node[i]);
rep(i,2,n)lg[i]=lg[i/2]+1;
rep(i,1,n-1)scanf("%d%d",&a,&b),add(a,b),add(b,a);
dfs1(1,0);dfs2(1,1);
rep(i,1,lg[n])rep(j,1,n)s[j][i]=union1(s[j][i-1],s[j+(1<<(i-1))][i-1]);
while(m--)
{
scanf("%d%d",&a,&b);
printf("%lld
",Qmax(a,b));
}
return 0;
}
