【BZOJ5092】【Lydsy1711月赛】分割序列

Author Avatar
q234rty 3月 25, 2018

超集和变换即可。

设si=⨁j=1iajs_i=\bigoplus_{j=1}^ia_j，容易看出原题相当于对于每个ii ，求sj+sj⊕si(1≤j≤i)s_j+s_j \oplus s_i(1 \leq j \leq i)的最大值。

考虑分离出sis_i，注意到异或可以被看成不退位减法:

a⊕b=a−b+2×((¬a)∧b) a\oplus b=a-b+2\times ((\lnot a) \land b)

于是sj+sj⊕si=si+2×((¬si)∧sj)s_j+s_j \oplus s_i=s_i+2\times ((\lnot s_i) \land s_j)，我们只需求出(¬si)∧sj(\lnot s_i) \land s_j的最大值即可。

注意到一个数的超集不会比他本身更劣，可以想到使用超集和变换求出每个数的超集的最小出现时间。

然后直接按位贪心就好了。

时间复杂度O((n+ai)logai)O((n+a_i) \log a_i)。

Code

//x+(sum^x)=sum+2*(x&(~sum))
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXSIZE=10000020;
int bufpos;
char buf[MAXSIZE];
#define NEG 0
void init(){
    #ifdef LOCAL
        freopen("5092.txt","r",stdin);
    #endif
    buf[fread(buf,1,MAXSIZE,stdin)]='\0';
    bufpos=0;
}
#if NEG
int readint(){
    bool isneg;
    int val=0;
    for(;!isdigit(buf[bufpos]) && buf[bufpos]!='-';bufpos++);
    bufpos+=(isneg=buf[bufpos]=='-');
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return isneg?-val:val;
}
#else
int readint(){
    int val=0;
    for(;!isdigit(buf[bufpos]);bufpos++);
    for(;isdigit(buf[bufpos]);bufpos++)
        val=val*10+buf[bufpos]-'0';
    return val;
}
#endif
char readchar(){
    for(;isspace(buf[bufpos]);bufpos++);
    return buf[bufpos++];
}
int readstr(char* s){
    int cur=0;
    for(;isspace(buf[bufpos]);bufpos++);
    for(;!isspace(buf[bufpos]);bufpos++)
        s[cur++]=buf[bufpos];
    s[cur]='\0';
    return cur;
}
int a[300002],f[1<<20];
int query(int x,int t){ //f[]<=t
    int ans=0;
    for(int i=19;i>=0;i--)
        if (x>>i&1){
            int qwq=ans|(1<<i);
            if (f[qwq]<=t)
                ans=qwq;
        }
    return ans;
}
int main(){
    init();
    int n=readint();
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    for(int i=1;i<=n;i++){
        a[i]=readint()^a[i-1];
        f[a[i]]=min(f[a[i]],i);
    }
    for(int i=0;i<20;i++)
        for(int j=0;j<(1<<20);j++)
            if (!(j>>i&1))
                f[j]=min(f[j],f[j^(1<<i)]);
    for(int i=1;i<=n;i++)
        printf("%d\n",a[i]+2*query(~a[i],i));
}

知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。
本文链接：https://www.q234rty.top/2018/03/25/bzoj5092/

隐藏