ZeroJudge 解題筆記：g499. 109北二1.感測器的比較

作者：王一哲
日期：2025年11月8日


ZeroJudge 題目連結：g499. 109北二1.感測器的比較

解題想法

這題理論上可以用 while 迴圈計算 a 的個位數為 0 且 b 的個位數為 1 的數量，每次計算後將 a, b 除以 2，直到 a, b 其中一個等於 0 為止，但是這樣的速度很慢，用 C++ 可以過關，但是用 Python 在第 16 筆測資會超時。 改用位元運算，因為題目要求 a 的位數為 0、b 的位數為 1，先取 a XOR b，這樣位數不同的部分計算結果為 1，再與 b 取 AND，只有 a 的位數為 0、b 的位數為 1 的部分計算結果為 1。如果是 Python 可以用 bin 將計算結果轉成二進位制的字串，計算其中有幾個 1 即可。

Python 程式碼

第10筆測資開始超時。

data = list(map(int, input().split()))  # 讀取資料
n = data[0]  # 共有 n 對資料
cnt = 0  # A 測到0，B 測到 1 的次數
for i in range(1, 2*n+1, 2):  # 讀取 n 對資料
    a, b = data[i], data[i+1]  # a, b 的值
    while a > 0 or b > 0:  # 當 a 大於 0 或 b 大於 0 繼續執行 
        if a%2 == 0 and b%2 == 1: cnt += 1  # 如果 a 的個位數為 0 且 b 的個位數為 1，cnt 加 1
        a >>= 1; b >>= 1  # a, b 除以 2
print(cnt)  # 印出答案

改用 sys.stdin.readline 及 sys.stdout.write 加速，第16筆測資開始超時。

import sys

data = list(map(int, sys.stdin.readline().split()))  # 讀取資料
n = data[0]  # 共有 n 對資料
cnt = 0  # A 測到0，B 測到 1 的次數
for i in range(1, 2*n+1, 2):  # 讀取 n 對資料
    a, b = data[i], data[i+1]  # a, b 的值
    while a > 0 or b > 0:  # 當 a 大於 0 或 b 大於 0 繼續執行 
        if a&1 == 0 and b&1 == 1: cnt += 1  # 如果 a 的個位數為 0 且 b 的個位數為 1，cnt 加 1
        a >>= 1; b >>= 1  # a, b 除以 2
sys.stdout.write(f"{cnt:d}\n")  # 印出答案

改用位元運算，使用時間約為 2.8 s，記憶體約為 255.7 MB，通過測試。

import sys

data = list(map(int, sys.stdin.readline().split()))  # 讀取資料
n = data[0]  # 共有 n 對資料
cnt = 0  # A 測到0，B 測到 1 的次數
for i in range(1, 2*n+1, 2):  # 讀取 n 對資料
    a, b = data[i], data[i+1]  # a, b 的值
    cnt += sum(c == '1' for c in bin(b & (a^b))[2:])
sys.stdout.write(f"{cnt:d}\n")  # 印出答案

C++ 程式碼

使用時間約為 0.3 s，記憶體約為 88 kB，通過測試。

#include <cstdio>
typedef long long LL;
using namespace std;

int main() {
    int n; scanf("%d", &n);  // 共有 n 對資料
    int cnt = 0;  // A 測到 0，B 測到 1 的次數
    for(int i=0; i<n; i++) {  // 讀取 n 對資料
        LL a, b; scanf("%lld %lld", &a, &b);  // a, b 的值
        while(a > 0 || b > 0) {  // 當 a 大於 0 或 b 大於 0 繼續執行 
            if (a%2 == 0 && b%2 == 1) cnt++;  // 如果 a 的個位數為 0 且 b 的個位數為 1，cnt 加 1
            a >>= 1; b >>= 1;  // a, b 除以 2
        }
    }
    printf("%d\n", cnt);  // 印出答案
    return 0;
}

計算有幾個 1 的部分還是跑迴圈，速度跟上面的寫法差不多。使用時間約為 0.3 s，記憶體約為 80 kB，通過測試。

#include <cstdio>
typedef long long LL;
using namespace std;

int count_digits(LL x) {
    int cnt = 0;
    while(x > 0) {
        if (x&1) cnt++;
        x >>= 1;
    }
    return cnt;
}

int main() {
    int n; scanf("%d", &n);  // 共有 n 對資料
    int cnt = 0;  // A 測到 0，B 測到 1 的次數
    for(int i=0; i<n; i++) {  // 讀取 n 對資料
        LL a, b; scanf("%lld %lld", &a, &b);  // a, b 的值
        cnt += count_digits(b & (a^b)); 
    }
    printf("%d\n", cnt);  // 印出答案
    return 0;
}

改用 bitset，速度比較快，使用時間約為 0.2 s，記憶體約為 104 kB，通過測試。

#include <cstdio>
#include <bitset>
typedef long long LL;
using namespace std;


int main() {
    int n; scanf("%d", &n);  // 共有 n 對資料
    int cnt = 0;  // A 測到 0，B 測到 1 的次數
    for(int i=0; i<n; i++) {  // 讀取 n 對資料
        LL a, b; scanf("%lld %lld", &a, &b);  // a, b 的值
        bitset<32> set_a (a), set_b (b);
        cnt += (set_b & (set_a ^ set_b)).count(); 
    }
    printf("%d\n", cnt);  // 印出答案
    return 0;
}