【JZOJ 4937】 與運算

Description

Analysis

因為是與運算，是以很容易想到的套路就是用二進制

可以設f[i]表示目前每一位二進制狀态為i，然後狀壓DP

枚舉每個數轉移，設cnt[i]表示有多少個數滿足and i=i（即i中若某一位為1則數中該位也為1）

那麼 f[i]=f[j]+i∗(cnt[i]−cnt[j])(i∈j)

cnt怎麼求，我們可以分治，比如：

000 001 010 011 | 100 101 110 111

左邊的第i個數 ∈ 右邊的第i個數，是以cnt[000]+=cnt[100],cnt[001]+=cnt[101]等等

這樣cnt求出來是nlogn的，但是轉移是n^2的

考慮優化，貪心想，每次隻把一個1變成0

這樣顯然是對的

複雜度nlogn

Code

#include<cstdio>
#include<cmath>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,b,a) for(int i=b;i>=a;i--)
using namespace std;
typedef long long ll;
const int N=;
int n,m,_2[],a[N];
ll f[N],cnt[N];
void dfs(int l,int r)
{
    if(l==r) return;
    int mid=(l+r)>>;
    fo(i,,mid-l) cnt[l+i]+=cnt[mid++i];
    dfs(l,mid);dfs(mid+,r);
}
int main()
{
    freopen("and.in","r",stdin);
    freopen("and.out","w",stdout);
    _2[]=;
    fo(i,,) _2[i]=_2[i-]*;
    scanf("%d",&n);
    int mx=;
    fo(i,,n)
    {
        scanf("%d",&a[i]);
        cnt[a[i]]++;
        mx=max(mx,a[i]);
    }
    int s=a[];
    fo(i,,n) s&=a[i];
    m=log2(mx)+;
    dfs(,_2[m]-);
    fd(i,_2[m]-,)
    {
        fo(j,,m-)
            if(i&_2[j])
            {
                int i1=i-_2[j];
                f[i1]=max(f[i1],f[i]+i1*(cnt[i1]-cnt[i]));
            }
    }
    printf("%lld",f[s]);
    return ;
}