2020-2021 Winter Petrozavodsk Camp, Belarusian SU Contest (XXI Open Cup, Grand Prix of Belarus) D Bank Security Unification

题目描述

http://codeforces.com/gym/102956/problem/D

Solution

能够发现如果对于 $f_i$ 最优的情况是 $j_1,j_2,\cdots j_k,i$

那么一定不存在 $j_k<i’<i$，其中 $a[j_k]\&a[i’]$ 和 $a[i’]\&a[i]$ 的二进制最高位相同

否则将 $i’$ 加入会使答案更大，所以我们在转移时只需要对于每个二进制位记录最近的存在这位的位置即可

时间复杂度 $O(n\log a_i)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define maxn 1000010
#define maxm 61
using namespace std;

int n, p[maxm]; 

ll a[maxn], f[maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n; ll ans = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i - 1];
        for (int j = 0; j <= 60; ++j)
            if (p[j]) f[i] = max(f[i], f[p[j]] + (a[p[j]] & a[i]));
        for (int j = 0; j <= 60; ++j)
            if (a[i] >> j & 1) p[j] = i;
        ans = max(ans, f[i]); 
    } cout << ans << "\n"; 
    return 0;
}