【GDKOI2017模拟1.12】與運算

Description

給出一個序列，Fi為前i項進行and運算之後的值。求這個序列的一個排列，使得 ∑Fi 最大。

輸出這個最大值。

n<=10^6

Solution

首先考慮F數組，顯然是單調不升的。

那麼我們考慮Dp，Dp i表示F數組目前最後一位為i的最大和。注意可以不放滿。

那麼我們枚舉一個數轉移，複雜度是O(N^2)的。

轉移的話我們可以預處理cnt[i]表示有多少個數and i等于i的。

這個東西可以用經典分治求出來，把二進制每一位分成0和1，把1的答案加到0上。

然後轉移就顯然了。

然後我們發現如果我們把轉移看做很多次減去一個2的幂，那麼每一次我們隻需要把i的二進制減去一個1就好了。

每次轉移可以拆成很多次轉移嘛~

Code

#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int N=*+,D=;
int cnt[N],mi[D+],n,x;
ll f[N],ans;
void solve(int l,int r) {
    if (l==r) return;
    int mid=(l+r)/;
    solve(l,mid);solve(mid+,r);
    fo(i,mid+,r) cnt[i-mid+l-]+=cnt[i];
}
int main() {
    freopen("and.in","r",stdin);
    freopen("and.out","w",stdout);
    scanf("%d",&n);
    fo(i,,n) scanf("%d",&x),cnt[x]++;
    mi[]=;
    fo(i,,D) mi[i]=mi[i-]*;
    solve(,mi[D]-);
    f[mi[D]-]=cnt[mi[D]-]*(mi[D]-);
    fd(i,mi[D]-,) {
        fo(j,,D) if (i&mi[j]) {
            x=i-mi[j];
            f[x]=max(f[x],f[i]+(ll)x*(cnt[x]-cnt[i]));
        }
        ans=max(ans,f[i]);
    }
    printf("%lld\n",ans);
}