程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces 164 E Compatible Numbers

Codeforces 164 E Compatible Numbers

編輯：C++入門知識

Codeforces 164 E Compatible Numbers

題目鏈接~~>

做題感悟：確實是好題，做拉的比賽的時候想了很久，想到枚舉變幻某一位的 0 為 1 ，但是每個數都這樣枚舉豈不超時的節奏，當時沒想到其實從大到小枚舉一次就 ok 了。

解題思路：

本題要求兩個數 a & b = 0 , 如果 a = 10010 , b 至少（指在 a 中的為 1 的位必須為 0 ）是 01101 ，還可以是 00101 ，00001 ，00000。就相當於你去買東西一樣，先提出你的要求（必須滿足），至於其他方面都無所謂。這樣我們可以枚舉 b 中的 1 ，讓其變為 0 ，那麼，怎樣枚舉呢？一個一個的枚舉是不可以的，肯定超時，我們可以統一枚舉一下，就跟狀態壓縮更新狀態一樣，相當於遞推，用動態規劃的思想去優化它，每個數最多只變化 0 的個數，然後再用變化了的數去變化。

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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<