每日归档： 2018年10月19日

一道简单双指针题。
首先猜结论：\(x\ xor\ y==x+y\)当且仅当\(x\&y==x+y\)
那么，令函数\(f_l\)表示，以\(l\)为左端点最远能拓展到的右端点。
我们可以发现，\(f_{l+1}\)也一定至少能拓展到这个点。
这时候我们则可以在固定左端点的同时移动右端点。每一次移动，从这个右端点到这个左端点之间所有的左端点构成的区间都是合法的。
统计即可得解。

#include<iostream>
#include<cstdio>
using namespace std;

int n,a[200005];
void init(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&a[i]);
    }
    long long ans=0,nw=0;
    int l=1,r=1;
    while(r<=n){
        while((!(nw&a[r]))&&r<=n){
            nw|=a[r++];
            ans+=(r-l);
        }
        nw^=a[l++];
    }
    printf("%lld",ans);
}
int main(){
    init();
    return 0;
} 

 

其中，\(f[k]\)表示递推到第i位的最大值。
那么，\(f[k]\)显然是可以从\(f[k-1]\)递推来的。
这时候只要考虑\(i|j==k\)的值。
枚举k的子集，求最大值。
这样做是\(O(松松松)\)的。
考虑优化。
我们可以发现，对于k的每一个子集，它的子集的最大值是已经求过的。
那么我们只需要考虑枚举每一个k子集的一部分，可以考虑每一次把它反与上一个\(2^l\)，并求Max和次Max。
这样有解，复杂度\(O(n*2^n)\)。

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define Max(_A,_B) ((_A)>(_B)?(_A):(_B))
#define Swap(_A,_B) ((_A)^=(_B)^=(_A)^=(_B))
using namespace std;
//mx[i][0]表示最大值，mx[i][1]表示次大值。 
int f[1<<18],n,a[1<<18];
int nw,mxx,lmxx,sa,sb,st;
struct data{
    int v;
    int nm;
    bool operator ==(const data &x)const{
        return this->v==x.v&&this->nm==x.nm;
    }
}lst[40],mx[1<<18][2];
inline bool cmp(const data &x,const data &y){
    return x.v>y.v;
}
//处理第k个数，它的最大值和次大值。 
int wrk(int k){
    nw=0,mxx=0,lmxx=0,sa=-1,sb=-1,st=0;
    lst[++st]=(data){a[k],k};
    for(int i=0;(1<<i)<=k;++i){
        if((k>>i)&1){
            nw=k^(1<<i);
        }else{
            continue;
        }
        lst[++st]=mx[nw][0];
        lst[++st]=mx[nw][1];
    }
    sort(lst+1,lst+1+st,cmp);
    unique(lst+1,lst+1+st);
    mx[k][0]=lst[1],mx[k][1]=lst[2];
    return mx[k][0].v+mx[k][1].v;
}
void init(){
    scanf("%d",&n);
    const int MAX=1<<n;
    for(int i=0;i<MAX;++i){
        scanf("%d",&a[i]);
    }
    f[0]=0,mx[0][0].v=a[0],mx[0][1].v=0,mx[0][0].nm=0,mx[0][1].nm=-1;
    for(int k=1;k<MAX;++k){
        f[k]=wrk(k);
        f[k]=Max(f[k],f[k-1]);
        printf("%d\n",f[k]);
    }
}
int main(){
    init();
    return 0;
}