TOJ 4

題目

https://toj.tfcis.org/oj/pro/4/

有 $N$ 個插頭以及電器，分別用長度 $L$ 的 $0/1$ 字串來表示，唯有電器以及插頭完全相同才能配對

現在你只有一種操作方式: 把插頭的某個位元反轉，請問最少需要多少操作才可以讓所有電器以及插頭配對

如果不可能則輸出 IMPOSSIBLE

想法

如果說全部的電器都會對應到一個特定的插頭，那麼第一個電器一定會有一個對應的插頭

枚舉所有插座對應到第一個電器的情況，檢查是否所有的電器跟插座是否匹配

至於如何反轉可以這樣想

要讓插座 $m$ 配對上電器 $n$，那麼需要反轉的位元就是兩兩不相同的位元，可以用 xor 檢查出來，得到 $p = m \oplus n$

接下來要去反轉每個插座 $m_i$，則 $m_i^{‘} = m_i \oplus p$

Code

//By Koios1143
#include<iostream>
#include<algorithm>
using namespace std;
int t, n, l;
long long change, ans, res, apps[1005], plugs[1005], tmp[1005];
string s;

int main(){
    cin>>t;
    for(int Case=1 ; Case<=t ; Case++){
        cin>>n>>l;
        for(int i=0 ; i<n ; i++){
            cin>>s;
            // 將 0/1 字串轉成數字
            apps[i] = 0;
            for(int j=0 ; j<l ; j++){
                apps[i] |= ((long long)(s[j]-'0')<<j);
            }
        }
		
	// 先排序好，之後比較好判斷是否匹配
        sort(apps, apps+n);
		
        for(int i=0 ; i<n ; i++){
            cin>>s;
            // 將 0/1 字串轉成數字
            plugs[i] = 0;
            for(int j=0 ; j<l ; j++){
                plugs[i] |= ((long long)(s[j]-'0')<<j);
            }
        }
        
        ans = -1;
        for(int i=0 ; i<n ; i++){
            // 只看 apps[0] 以及 plugs[i]
            // 找出需要轉換的 bit
            change = apps[0] ^ plugs[i];
            // 將每個插座轉換後的結果儲存在新的陣列
            for(int j=0 ; j<n ; j++){
                tmp[j] = plugs[j] ^ change;
            }
            // 排序後檢查
            sort(tmp, tmp+n);
            bool found = true;
            for(int j=0 ; j<n ; j++){
                if(apps[j] != tmp[j]){
                    found = false;
                    break;
                }
            }
            
			// 匹配成功
            if(found){
                res = 0;
                while(change){
                    // 操作數等同 change 中 bit 為 1 的數量
                    // 以 lowbit 來找
                    res++;
                    change ^= (change & -change); // lowbit
                }
                if(ans == -1) ans = res;
                else ans = min(ans, res);
            }
        }
        if(ans == -1){
            cout<<"Case #"<<Case<<": IMPOSSIBLE\n";
        }
        else{
            cout<<"Case #"<<Case<<": "<<ans<<"\n";
        }
    }
    return 0;
}

時間複雜度分析

每筆測資輸入時間複雜度為 $O(NL)$

預先排序 app 的時間複雜度為 $O(NlogN)$

匹配過程重複 $N$ 次，每次切成新插座所需時間複雜度為 $O(N)$，排序時間複雜度為 $O(NlogN)$，檢查時間複雜度為 $O(N)$，計算操作數量時間複雜度為 $O(logL)$

匹配總時間複雜度為 $O(N^2 + N^2logN + NlogL)$

總時間複雜度為 $O(t(NL + N^2 + N^2logN + NlogL))$