題目鏈接：點擊查看

題目大意：給出一個長度為 $n$ 的序列，求出貢獻最大的三元對：$(i,j,k)$，滿足 $i<j<k$，其貢獻為 $a_i|(a_j\&a_k)$

題目分析：因為 $a_j$ 和 $a_k$ 被綁定了，所以我們可以直接枚舉 $a_i$ 貪心從高位去尋找是否存在后面 $a_j\&a_k$

現在問題轉換為了如何快速找到對于某個數值 $x$ 來說，位置 $i$ 后面是否存在著兩個數滿足 $a_j\&a_k=x$

到此為止就變成 $SOSdp$ 的裸題了，只需要記錄一下每個數字最后一次出現的位置，記為 $fi$，和每個數字倒數第二次出現的位置，記為 $se$ 就好了，轉移的話，是由超集向子集轉移，那么針對于上一段的問題，我們只需要判斷一下 $s{e}_x$ 是否大于 $i$ 即可

代碼：

// Problem: F. Bits And Pieces // Contest: Codeforces - Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) // URL: https://codeforces.com/contest/1208/problem/F // Memory Limit: 256 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=(1<<21)+100; int a[N],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=1;i<=n;i++) {read(a[i]);update(a[i],i);}for(int j=0;j<21;j++) {for(int i=0;i<1<<21;i++) {if(((i>>j)&1)==0) {//i的維度低于i|(1<<j)的維度update(i,fi[i|(1<<j)]);update(i,se[i|(1<<j)]);}}}int ans=0;for(int i=1;i<=n-2;i++) {int cur=0;for(int j=20;j>=0;j--) {if((a[i]>>j)&1) {continue;} else if(se[cur|(1<<j)]>i) {cur|=1<<j;}}ans=max(ans,a[i]|cur);}cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的CodeForces - 1208F Bits And Pieces(SOSdp+贪心)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。