题解 AT4168 【[ARC100C] Or Plus Max】

皎月半洒花 · 2020-03-09 11:11:18 · 题解

发现似乎是在做一个FMT状物，但是直接转移最大值需要 k ^2 甚至更高的代价，不能直接转移。

考虑对于每个集合 s 记一下这个集合中的最最大数和次大数，不难发现这样转移是方便的。复杂度 2^kk 。

ll ans ;
int m, n ;
pint f[N] ;
ll base[N] ;

bool comp(int x, int y){
    return base[x] > base[y] ;
}
int main(){
    cin >> m ; n = (1 << m) - 1 ;
    for (int i = 0 ; i <= n ; ++ i){
        cin >> base[i] ;
        f[i] = make_pair(i, n + 1) ;
    }
    base[n + 1] = -1 ;
    for (int i = 0 ; i <= n ; ++ i)
        for (int j = 0 ; j < m ; ++ j)
            if (!((1 << j) & i)){
                int k = (1 << j) | i ;
                int t[4] = {fr(i), sc(i), fr(k), sc(k)} ;
                sort(t, t + 4, comp) ; unique(t, t + 4) ;
                f[k] = make_pair(t[0], t[1]) ;
            }
    for (int i = 1 ; i <= n ; ++ i){
        ans = max(ans, base[fr(i)] + base[sc(i)]) ;
        cout << ans << endl ;
    }
}