ARC100E - Or Plus Max
题目
对于每个 \(k\in (0,2^n)\)，求 \(a_i+a_j(0\leq i<j\leq k)\) 的最大值。
分析
可以发现 \(\max_{i\& k==i}a_i\) 可以通过高维前缀和实现，而另一个相当于是次大值，
因此维护最大值和次大值加起来再进行前缀最大值即可。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=262144;
int n,mx[N],se[N];
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for (int i=0;i<(1<<n);++i) cin>>mx[i],se[i]=0xc0c0c0c0;for (int j=0;j<n;++j)for (int i=1;i<(1<<n);++i)if ((i>>j)&1){if (mx[i]<mx[i^(1<<j)]) se[i]=mx[i],mx[i]=mx[i^(1<<j)];else if (se[i]<mx[i^(1<<j)]) se[i]=mx[i^(1<<j)];if (mx[i]<se[i^(1<<j)]) se[i]=mx[i],mx[i]=se[i^(1<<j)];else if (se[i]<se[i^(1<<j)]) se[i]=se[i^(1<<j)];}mx[0]+=se[0];for (int i=1;i<(1<<n);++i){mx[i]=max(mx[i-1],mx[i]+se[i]);cout<<mx[i]<<'\n';}return 0;
}
CF1208F Bits And Pieces
题目
在 \(1\sim n\) 中，找出三元组 \((i,j,k),i<j<k\)，求 \(a_i|(a_j\&a_k)\) 的最大值。
分析
这个表达式全是位运算，我们可以类似线性基一样贪心，那么当判定答案为 \(ans\) 时，对于每个 \(a_i\)，
检验 \(ans\ xor\ (ans\ \&\ a_i)\) 是否能在下标超过 \(i\) 的两个数所表示，那么相当于是上一题的下标和值调换，做法是类似的，判定次大下标是否超过 \(i\)。
代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N=2097152;
int n,mx[N],se[N],m,MX,a[N],ans;
int main(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cin>>n;for (int i=1;i<=n;++i){cin>>a[i];if (mx[a[i]]) se[a[i]]=mx[a[i]],mx[a[i]]=i;else mx[a[i]]=i;MX=MX<a[i]?a[i]:MX;}for (m=1;(1<<m)<=MX;++m);for (int j=0;j<m;++j)for (int i=0;i<(1<<m);++i)if ((i>>j)&1){if (mx[i^(1<<j)]<mx[i]) se[i^(1<<j)]=mx[i^(1<<j)],mx[i^(1<<j)]=mx[i];else if (se[i^(1<<j)]<mx[i]) se[i^(1<<j)]=mx[i];if (mx[i^(1<<j)]<se[i]) se[i^(1<<j)]=mx[i^(1<<j)],mx[i^(1<<j)]=se[i];else if (se[i^(1<<j)]<se[i]) se[i^(1<<j)]=se[i];}for (int i=m-1;~i;--i){int now=ans|(1<<i);for (int j=1;j<=n;++j)if (se[now^(now&a[j])]>j){ans|=1<<i;break;}}cout<<ans;return 0;
}