UVa11659 - Informants (數論 Math theorm、暴力搜尋 Brute force)

題目大意

ACM 是一家間諜公司，裡面有很多的線民，但這些線民認為某部分線民講的不是實話、某些是實話。

我們的目的是要找出最多的線民數量，且這些線民不會不信任彼此。

題目連結

重點觀念

• 透過二進制進行效率優化
• 理解 C++ 運算優先順序

分析與心得

一道好題。
只要是二進制的題目，我都認為他是好題，因為它打破了大部分的人的思考常規，可以讓我深刻的了解到當遇到大量關於是或否、對或錯時，都應該想到用二進制來解決這種問題。

主要想法是對每一個線民所信任的線民、不信任的做紀錄(or 運算)，之後再暴力搜尋即可找出。
線民可以用此方式表示 \(011100\)，表示有 3 位線民，分別是 C、D、E。(從右至左開始字典序)

這樣在記錄信任、不信任的線民時可以使用 or 運算。舉例：

• 信任 A 線民 \(0001\)
• 信任 B 線民 \(0010\)
• 結果 (or 運算) \(0011\)

最壞時間複雜度大約是 \(2^20*20=20971520\)，基本上只要 judge 是有名的 judge 基本上能夠忍受的時間複雜度是 2000 萬 ~ 3000 萬，都可以去試試看。能 AC 就是對的，效率優化在 AC 面前都沒有用

主要大家要稍微注意，C++ 的二進制運算比起邏輯運算(or、and…) 優先順序更為後面，因此要善用括號。
沒想到，我就因為一直以為二進制的括號比邏輯運算優先度更高，讓我在 debug 一直抓錯想法…。

參考連結

C + + 內建運算子、優先順序和關聯性 by Microsoft
Uva11659 Informants by txya900619

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
const int MAXN = 25;
int n, a, x, y;
int say_wrong[MAXN], say_correct[MAXN];
// say_wrong 判斷 index 線民不信任那些人。二進制表示 0010，表示不喜歡 B 線民
// say_correct 判斷 index 線民信任那些人。二進制表示 0010，表示喜歡 B 線民

int bit_count(int x){ //判斷其最大長度，也就是可以信任的線民數量
    int cnt = 0; //此數字最大有幾個 1(幾個線民)
    while(x){ //不斷除2，然後判斷最尾數的位元是不是為 1，是就 cnt+1
        if(x & 1) cnt += 1; 
        x >>= 1;
    }
    return cnt; //回傳線民
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif // LOCAL
    while(cin >> n >> a && (n+a!=0)){
        memset(say_correct, 0, sizeof(say_correct)); //清空資料
        memset(say_wrong, 0, sizeof(say_wrong)); //清空資料
        for(int i = 0; i < a; i++){ //輸入信任與不信任
            cin >> x >> y;
            if(y > 0) say_correct[x] |= 1 << y-1; //進行記錄，並且合併過去資料
            if(y < 0) say_wrong[x] |= 1 << -y-1; //進行記錄，並且合併過去資料
        }

        int limit = 1 << n; //最大的排列組合數量
        int max1 = 0; //最多的線民數量，且這些線民不會不信任彼此
        for(int i = 0; i < limit; i++){ //開始進行暴力搜尋 
            int necessary_informants = i; //每一種線民們的組合方式，EX: 0110，有 B、C 線民
            int flag = 1; //判斷這組合有沒有互相不信任的線民
            for(int j = 1; j <= n; j++){ //對 j 線民找出信任與不信任的關聯
                int necessary_informant = necessary_informants & (1 << j-1);
                //判斷這個組合的線民，第 j 個有沒有在這組合裡面。
                //如果有，那在做 & 運算會大於 1，反之則是零。
                //(1 << j-1) 讓第 j 位 bit 為 1，表示第 j 位有線民

                int is_wrong = ( ((say_wrong[j] & i) != 0) || ((say_correct[j] & i) != say_correct[j]));
                //判斷 j 號村民不信任的線民是否有在此組合內
                //((say_wrong[j] & i) != 0) 
                //如果不信任的線民與我們這次的組合有關聯則表示此組合並不正確
                //((say_correct[j] & i) != say_correct[j])
                //信任的線民必須完全重疊於我們這次的組合，反之表示有些線民沒有被信任到，
                //那之後暴力搜尋會搜尋到，這裡先判斷為錯誤

                if(necessary_informant && is_wrong){
                //如果 necessary_informant 為否表示此組合沒有 j 號村民，因此不用在意他不信任誰
                // is_wrong 如果為否表示此組合有符合 j 號線民的想法。
                //如果上面兩個其中一個為 yes，則跳出組合，表示此組合不會是正確的組合。

                    //debug 用
                    /*
                    cout << "i is " << i << '\n';
                    cout << "necessary_informant " << necessary_informant << '\n';
                    cout << "j is " << j << '\n';
                    cout << "debug " << say_wrong[j] << ' ' << say_correct[j] << '\n';
                    cout << "info " << ((say_wrong[j] & i) != 0) << ' ' << ((say_correct[j] & i) != say_correct[j]) << '\n';
                    cout << "is_wrong " << is_wrong << '\n';
                    */

                    flag = 0; //表示此組合絕對不會是答案
                    break;
                }
            }
            if(flag){ //如果 flag 有可能是答案，那就跟 max1 比較誰有最大的線民數量
                //cout << "i is " << i << '\n';
                max1 = max(bit_count(necessary_informants), max1);
            }
        }
        cout << max1 << '\n'; //輸出答案
    }
    return 0;
}

用紙筆去 Debug

因為只是自己在思考過程中隨手做的筆記，覺得不是對讀者這麼有幫助，因此放在文章最下面。

有時候用想或用看的可能不太能夠懂這演算法，那就用寫的吧！這是大衛我自己學習的手稿，紀錄者我的學習過程。