线性基

2023年3月9日源码参考

P3857 [TJOI2008]彩灯

题意：给定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

P4570 [BJWC2011]元素

题意：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

P4151 [WC2011]最大XOR和路径

题意: 给定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

P4301 [CQOI2013]新Nim游戏

题意：第一轮为自定义游戏，取走若干堆石子，第二轮开始为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

P3292 [SCOI2016]幸运数字

题意：给定一棵点权树和m个询问x y 问路径x y 上任选几个点所能构成的最大异或和

题解：

线性基是支持合并的 $log^2$ 的复杂度

如果用线段树来合并的话总的复杂度为 $ O((n+Q)*(log^4))$

如果用st表的话查询只要 $O(1)$ 即可而线性基显然是满足st表的性质的

代码较长注意一下细节即可

#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\n",Qmax(a,b));
    }
    return 0;
}

View Code

【LOJ#6060】Set

题意：给出 n 个非负整数，将数划分成两个集合x1，x2 记为一号集合和二号集合。 x1为一号集合中所有数的异或和， x2为二号集合中所有数的异或和。在最大化x1+x2 的前提下，x1最小化，输出x1.

题解：首先 x1⊕x2=s 是定值。而 s 中假设某一位上是 1 ，则 x1,x2 上必定有一个是 1 ，另一个是 0 ，所以对答案没有影响。反过来，如果 s 上某一位为 0 ，则要么都是 0 ，要么都是 1 。
所以我们在考虑构造线性基的时候，优先考虑$0$的位，再考虑$1$的位。
那么现在只需要令 x2 在原本在 s 是 0 的位置上取到尽可能多的 1 的情况下最大，这样子异或一下就是 x1 了

#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=2e6+10;
ll p[100],x,s,s1,s2,a[N];
int n,b[N],cnt;
void upnode(ll x)
{
    rep(i,1,cnt)if(x>>b[i]&1)
    {
        if(!p[i]){p[i]=x;return ;}
        x^=p[i];
    }
}
int main()
{
    cin>>n;
    rep(i,1,n)scanf("%lld",&a[i]),s^=a[i];
    repp(i,62,0)if(!(s>>i&1))b[++cnt]=i;
    repp(i,62,0)if(s>>i&1)b[++cnt]=i;
    rep(i,1,n)upnode(a[i]);
    rep(i,1,cnt)if(!(s1>>b[i]&1))
    s1^=p[i];
    cout<<(s^s1);
    return 0;
}

View Code

转载于:https://www.cnblogs.com/bxd123/p/11587598.html

上一篇文章
手写spring-boot-start 下一篇文章
MyBatis学习：高级查询（一对一映射）