ZeroJudge 解題筆記：d326. 程式設計師的面試問題(二)

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


ZeroJudge 題目連結：d326. 程式設計師的面試問題(二)

解題想法

這題考二進位制補數的觀念，用 C++ 的 bitset 寫起來超快。

Python 程式碼

使用時間約為 18 ms，記憶體約為 3.3 MB，通過測試。

import sys

def negative(num):  # 輸入 10 進位負整數，輸出其補數加 1
    s = bin(num)[3:]  # 轉成 2 進位制字串，刪除開頭的 -0b
    s = s.zfill(32)  # 前面補 0 到 32 位數
    t = ''  # 儲存輸出結果的空字串
    for c in s:  # 從 s 依序讀取字元 c
        if c == '0': t += '1'  # 如果 c 是 0，將 1 加到 t
        else: t += '0'  # 如果 c 是 1，將 0 加到 t
    return int(t, 2)+1  # 將 t 轉回整數、加 1，再回傳

result = []
for line in sys.stdin:
    v, a ,b = map(int, line.split())  # 要計算的整數 v，第 a 位數改成 b
    if v < 0:  # 如果 v 是負數
        vb = f"{negative(v):032b}"  # 呼叫 negative 代入 v 計算結果，再用 format 輸出成 32 位數的 2 進位制整數字串
    else:  # 反之，直接用 format 輸出成 32 位數的 2 進位制整數字串
        vb = f"{v:032b}"
    ans = f"{vb[:31-a]}{b:d}{vb[32-a:]}\n"  # 用切片將第 a 位數換成 b
    result.append(ans)
sys.stdout.write("".join(result))

C++ 程式碼

不用 bitset，寫起來很麻煩。使用時間約為 3 ms，記憶體約為 344 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;
        
string bin(int num) {  // 輸入 10 進位整數，輸出 2 進位制字串
    string t = "";  // 儲存輸出結果的空字串
    if (num >= 0) {  // 正數
        while(num) {  // 當 num 不為 0 繼續執行
            t = char((num&1) + '0') + t;  // num 與 1 取 and 再加上 '0'，轉成 char，加到 t 最後面
            num >>= 1;  // num 除以 2
        }
        int m = (int)t.size();  // 目前 t 的長度
        for(int i=0; i<32-m; i++) t = '0' + t;  // 前面補 0 到 32 位數
        return t;  // 回傳 t
    } else {  // 負數
        num = -num;  // 轉成正值
        string s = "";  // 暫存正值用的空字串
        while(num) {  // 當 num 不為 0 繼續執行
            s = char((num&1) + '0') + s;  // num 與 1 取 and 再加上 '0'，轉成 char，加到 s 最前面
            num >>= 1;  // num 除以 2
        }
        int m = (int)s.size();  // 目前 s 的長度
        for(int i=0; i<32-m; i++) s = '0' + s;  // 前面補 0 到 32 位數
        string u = "";  // 暫存補數用的空字串
        for(char c : s) {  // 從 s 依序讀取字元 c
            if (c == '0') u += '1';  // 如果 c 是 0，將 1 加到 u
            else u += '0';  // 如果 c 是 1，將 0 加到 u
        }
        long com = 0, b = 1;  // 補數要用 long，基底 b 從 1 開始
        for(int i=31; i>=0; i--) {  // 從 u 最後一位往前讀取
            com += (u[i] - '0')*b;  // u[31-i] 轉成整數，乘以 b，加到 com
            b <<= 1;  // b 乘以 2
        }
        com++;  // 補數加 1
        while(com > 0) {  // 當 com 不為 0 繼續執行
            t = char((com&1) + '0') + t;  // com 與 1 取 and 再加上 '0'，轉成 char，加到 t 最後面
            com >>= 1;  // com 除以 2
        }
        int p = (int)t.size();  // 目前 t 的長度
        for(int i=0; i<32-p; i++) t = '0' + t;  // 前面補 0 到 32 位數
        return t;  // 回傳 t
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int v, a, b;  // 要計算的整數 v，第 a 位數改成 b
    while(cin >> v >> a >> b) {
        string s = bin(v);  // 呼叫 bin 將 v 轉成 2 進位制字串
        cout << s.substr(0, 31-a) + char(b+'0') + s.substr(32-a) << "\n";
    }
    return 0;
}

用 bitset 超好寫，使用時間約為 2 ms，記憶體約為 324 kB，通過測試。

#include <iostream>
#include <string>
#include <bitset>
using namespace std;

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int v, a, b;  // 要計算的整數 v，第 a 位數改成 b
    while(cin >> v >> a >> b) {
        bitset<32> bitv ((unsigned long long)v);  // 將 v 轉成 32 位元的 bitset
        string s = bitv.to_string();  // 將 bitv 轉成字串
        cout << s.substr(0, 31-a) + char(b+'0') + s.substr(32-a) << "\n";
    }
    return 0;
}