題目鏈接：點擊查看

題目大意：給出 $2^n$ 個數(shù)，編號從 $0$ 開始，現(xiàn)在要求出對于每個 $k\in [0,2^n)$，找到兩個下標(biāo) $(i,j)$，滿足 $i\oplus j<=k$，且 $a_i+a_j$ 最大

題目分析：讀完題后感覺很亂，因為繞了很多次，分析之后需要發(fā)現(xiàn)，$i\oplus j<=k$ 這個條件，可以表示為 $i\oplus j$ 一定是 $k$ 的子集

所以我們就可以用 $SOSdp$ 維護一下每個下標(biāo)最大的兩個數(shù)值，每次相加即可

轉(zhuǎn)移的話，這個題目是需要從子集向超集轉(zhuǎn)移

注意若 $(i,j)$ 滿足 $i\oplus j<=k$，則一定滿足 $i\oplus j<=k+1$，所以答案非嚴(yán)格遞增

代碼：

// Problem: E - Or Plus Max // Contest: AtCoder - AtCoder Regular Contest 100 // URL: https://atcoder.jp/contests/arc100/tasks/arc100_c // Memory Limit: 1024 MB // Time Limit: 2000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; int fi[N],se[N]; void update(int pos,int val) {if(val>fi[pos]) {se[pos]=fi[pos];fi[pos]=val;} else if(val>se[pos]) {se[pos]=val;} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n;read(n);for(int i=0;i<1<<n;i++) {int x;read(x);update(i,x);}for(int j=0;j<n;j++) {for(int i=0;i<1<<n;i++) {if((i>>j)&1) {//i的維度高于i|(1<<j)的維度update(i,fi[i^(1<<j)]);update(i,se[i^(1<<j)]);}}}int ans=0;for(int i=1;i<1<<n;i++) {ans=max(ans,fi[i]+se[i]);printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的AtCoder - arc100_c Or Plus Max(SOSdp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。