多校一 1002 Operation &元素

2019.7.26 多校一 1002 Operation（线性基+二维动态规划） [BJWC2011]元素(线性基+贪心)

推荐模板题
线性基模板
这题的题解写的挺好的大家可以康康

线性基呢
就是从几个数里
选出任意个数
使得它们异或起来得到的数最大

反正那个题解写的真挺好。。
我就不多讲具体原理

operation

这题讲的是一个在线的修改求线性基
里面还要decode一下。。。

那我们就用动态规划的思想
二维dp
线性基尽量取右边的数
然后运用pos数组检查是否在l到r之间
二维dp维护线性基
很巧妙

题解叫这个是上三角形态/线性基前缀和

#include
using namespace std;
const int MAXN=500000+10;
int T,n,m,op,l,r,tmp,ans,a[MAXN],f[MAXN][32],pos[MAXN][32];
inline int Read() 
{
    int x=0,f=1; char ch=getchar(); 
    while (ch'9') {if (ch=='-') f=-f; ch=getchar();}
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
char s[30];
inline void writeln(int x)
{
    if (x<0) putchar('-'),x=-x; 
    if (!x) putchar('0'); else 
    {
        int len=0;  
        while (x) s[++len]=x%10+'0',x/=10;
          while (len) putchar(s[len--]);
    } 
    putchar('\n');
}
inline void Add(int i,int x)
{
    int k=i;
    for (int j=30;j>=0;--j) f[i][j]=f[i-1][j],pos[i][j]=pos[i-1][j];
    for (int j=30;j>=0;--j) if (x>>j)
    { 
        if (!f[i][j]) 
        {
            f[i][j]=x;
            pos[i][j]=k;
            break; 
        }
        else 
        {
            if (k>pos[i][j]) 
            {
                tmp=k,k=pos[i][j],pos[i][j]=tmp;
                tmp=x,x=f[i][j],f[i][j]=tmp;
            }
            x^=f[i][j];
        }
    }
}
int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    T=Read();
    while (T--)
    {
        n=Read(),m=Read();
        for (int i=1;i<=n;++i) a[i]=Read(),Add(i,a[i]);
        ans=0;
        while (m--)
        {
            op=Read();
            if (op) a[++n]=Read()^ans,Add(n,a[n]);
            else
            {
                l=Read(),r=Read();
                l=(l^ans)%n+1,r=(r^ans)%n+1;
                if (l>r) swap(l,r);
                ans=0;
                for (int j=30;j>=0;--j) if((ans^f[r][j])>ans&&pos[r][j]>=l) ans^=f[r][j];
                writeln(ans);
            }
        }
        for (int i=1;i<=n;++i)
          for (int j=30;j>=0;--j) f[i][j]=pos[i][j]=0;
    }
    return 0;
}

拓展练习
洛谷p4570
里面的题解里的线性基博客写的挺好的
线性基的性质概括了一下

这一题使用的线性基和本题类似
更简单一些
建议自己背一下写一下

注意long long位次最高到62
到63会很有意思
大家可以试试

#include
#define ll long long
using namespace std;

ll ji[100];
int m[1005],pos[1005];
void add(int p,ll t){
    int k=p;
    for(int i=63;i>=0;i--){
        if(t>>(ll)i){
            if(!ji[i]){
                ji[i]=t;
                pos[i]=k;
                break;
            }else {
                if(m[k]>m[pos[i]]){
                    swap(ji[i],t);
                    swap(k,pos[i]);
                }
                t^=ji[i];
            }

        }
    }
}

int main(){
    int n,ans=0;
    ll t;
    scanf("%d",&n);
    memset(pos,-1,sizeof(pos));
    for(int i=0;i<n;i++){
        scanf("%lld%d",&t,&m[i]);
        add(i,t);
    }
    for(int i=0;i<=63;i++){
        if(pos[i]!=-1){
            ans+=m[pos[i]];
        }

    }
    printf("%d",ans);
    return 0;
}