题解 AT4168 【[ARC100C] Or Plus Max】
皎月半洒花
2020-03-09 11:11:18
发现似乎是在做一个FMT状物，但是直接转移最大值需要 $k ^2$ 甚至更高的代价，不能直接转移。
考虑对于每个集合 $s$ 记一下这个集合中的最最大数和次大数，不难发现这样转移是方便的。复杂度 $2^kk$ 。
```cpp
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 ;
}
}
```