主題鏈接~~>

做題情緒：好題，做拉的比賽的時候想了非常久，想到枚舉變幻某一位的 0 為 1 。可是每一個數都這樣枚舉豈不超時的節奏，當時沒想到事實上從大到小枚舉一次就 ok 了。

解題思路：

? ? ? ? ? ? ? ?本題要求兩個數 ?a & b = 0 , 假設 a ?= ?10010 , b 至少（指在 a 中的為 1 的位必須為 0 ）是 01101 ，還能夠是 00101 ，00001 。00000。就相當于你去買東西一樣，先提出你的要求（必須滿足）。至于其它方面都無所謂。

這樣我們能夠枚舉 b 中的 1 。讓其變為 0 ，那么，如何枚舉呢 ?？ 一個一個的枚舉是不能夠的，肯定超時，我們能夠統一枚舉一下，就跟狀態壓縮更新狀態一樣，相當于遞推。用動態規劃的思想去優化它，每一個數最多僅僅變化 0 的個數。然后再用變化了的數去變化。

代碼：

#include<iostream> #include<sstream> #include<map> #include<cmath> #include<fstream> #include<queue> #include<vector> #include<sstream> #include<cstring> #include<cstdio> #include<stack> #include<bitset> #include<ctime> #include<string> #include<cctype> #include<iomanip> #include<algorithm> using namespace std ; #define INT __int64 #define L(x) (x * 2) #define R(x) (x * 2 + 1) const int INF = 0x3f3f3f3f ; const double esp = 0.0000000001 ; const double PI = acos(-1.0) ; const INT mod = 1e9 + 7 ; const int MY = 15 ; const int MX = (1<<22) + 5 ; int n ; int dp[MX] ,g[MX] ; int main() {//freopen("input.txt" ,"r" ,stdin) ;while(~scanf("%d" ,&n)){int S = (1<<22) - 1 ;memset(dp ,0 ,sizeof(dp)) ;for(int i = 0 ;i < n ; ++i){scanf("%d" ,&g[i]) ;dp[g[i]^S] = g[i] ; // g[I] 須要的還有一半}for(int i = S ; i >= 0 ; --i) // 枚舉各種狀態{if(!dp[i]) // 假設沒有存值{for(int j = 0 ;j < 22 ; ++j) // 給其加入 1 讓其變成有值if(dp[i|(1<<j)])dp[i] = dp[i|(1<<j)] ;}}for(int i = 0 ;i < n ; ++i){if(i) cout<<" " ;if(dp[g[i]]) cout<<dp[g[i]] ;else cout<<"-1" ;}cout<<endl ;}return 0 ; }
?? ?

版權聲明：本文博客原創文章，博客，未經同意，不得轉載。

總結

以上是生活随笔為你收集整理的Codeforces 164 E Compatible Numbers的全部內容，希望文章能夠幫你解決所遇到的問題。

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