【Uva 題庫解題】C++ 個人解題筆記 - part7

本次題庫擷取自 CPE 2026/05/26 歷屆考題：https://cpe.mcu.edu.tw/cpe/test_data/2026-05-26

1. Uva 11639 - Guard the Land

PDF Source：https://onlinejudge.org/external/116/11639.pdf

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2686

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=e568

難度：★☆☆☆☆

題目觀察與解題思路

題目給定 $100 \times 100$ 大小的土地，每晚有兩名守衛，各自負責一個矩形區域。

若某區域被兩名守衛同時看守，稱為 strongly secured。
只被一名守衛看守，稱為 weakly secured。
完全沒被守衛看守，稱為 unsecured。

題目每組測資會給兩個矩形，每個矩形由左下角 $(x_1, y_1)$ 與右上角 $(x_2, y_2)$ 表示，且座標範圍皆在 0 到 100 之間。

假設第一個矩形面積是 $A$ ，第二個矩形面積是 $B$ ，兩者重疊面積是 $I$ ，則： $$\text{strong} = I$$ $$\text{weak}=A+B−2I$$ $$\text{unsecured}=10000−strong−weak$$

為什麼 weak 要減掉 $2I$ ？因為 $A+B$ 會把重疊區域算兩次，但 weak 表示剛好被一個守衛看守的區域，所以重疊區域不能算進 weak 裡面，因此兩個矩形各自都要扣掉重疊的那塊，也就是扣掉 $2I$ 。

說到這裡，問題是如何計算兩個矩形的重疊面積，解法如下：

兩個矩形若有交集，交集矩形的左下角為 $(max(x_1^{(1)}, x_1^{(2)}), max(y_1^{(1)}, y_1^{(2)}))$ （上標的 (1)、(2) 表示題目給定兩個矩形的點）
承上，交集矩形的右上角為 $(max(x_2^{(1)}, x_2^{(2)}), max(y_2^{(1)}, y_2^{(2)}))$
最後可得交集寬度為 $w = min(x_2^{(1)}, x_2^{(2)}) - max(x_1^{(1)}, x_1^{(2)})$ $w = m i n (x_{2}^{(1)}, x_{2}^{(2)}) - m a x (x_{1}^{(1)}, x_{1}^{(2)})$ ，高度為 $h = min(y_2^{(1)}, y_2^{(2)}) - max(y_1^{(1)}, y_1^{(2)})$ $h = m i n (y_{2}^{(1)}, y_{2}^{(2)}) - m a x (y_{1}^{(1)}, y_{1}^{(2)})$
- 若 $w > 0$ 且 $h > 0$ 表示兩個矩形有重疊，反之無重疊。

有了以上這些式子後，就可以開始實作程式了：

#include <bits/stdc++.h>

using namespace std;

struct rect{
    int x1, y1, x2, y2;
};

int area(rect r){
    return (r.x2 - r.x1) * (r.y2 - r.y1);
}

int ans(rect r1, rect r2){
    int left = max(r1.x1, r2.x1);
    int right = min(r1.x2, r2.x2);
    int bottom = max(r1.y1, r2.y1);
    int top = min(r1.y2, r2.y2);
    
    int w = right - left;
    int h = top - bottom;
    
    if (w <= 0 || h <= 0) return 0;
    return w * h;
}

int main(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i){
        rect r1, r2;
        
        cin >> r1.x1 >> r1.y1 >> r1.x2 >> r1.y2;
        cin >> r2.x1 >> r2.y1 >> r2.x2 >> r2.y2;
        
        int A = area(r1), B = area(r2);
        int I = ans(r1, r2);
        
        int strong = I;
        int weak = A + B - 2*I;
        int unsecure = 10000 - strong - weak;
        
        cout << "Night " << i << ": " << strong << " " << weak << " " << unsecure << '\n';
    }
}

3. Uva 11956 - Brainfuck

PDF Source：https://onlinejudge.org/external/119/11956.pdf

Uva Online Judge：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3107

難度：★★☆☆☆

題目觀察

這題的重點是執行完所有指令後，輸出整個 100-byte 記憶體的十六進位 dump。輸出格式為：Case X: XX XX XX ... XX

其中：

每個 byte 都要用兩位十六進位表示。
英文字母要大寫，例如 1F、0A。
每個 byte 之間剛好一個空白。
總共輸出 100 個 byte。
. 指令只代表輸出目前 byte，但題目最後只要求記憶體 dump，所以模擬時可以直接忽略它，因為它不會改變記憶體，題目輸出要求是執行後的 memory dump。

解題思路

建立一個大小為 100 的陣列：int mem[100] = {};

用 ptr 表示目前指標位置，一開始 int ptr = 0;，接著逐字元掃描 Brainfuck 指令字串。

指令處理他有列一個表給你，如下：

指令	操作
`>`	指標右移，若超過 99 則回到 0
`<`	指標左移，若小於 0 則回到 99
`+`	目前 byte 加 1，若從 255 再加則變 0
`-`	目前 byte 減 1，若從 0 再減則變 255
`.`	不影響記憶體，可以忽略

可以用取模處理指標：

1 2	ptr = (ptr + 1) % 100; ptr = (ptr + 99) % 100;

其中 (ptr + 99) % 100 等價於往左一格，避免 C++ 中負數取模造成問題。

byte 循環也可以用取模處理：

1 2	mem[ptr] = (mem[ptr] + 1) % 256; mem[ptr] = (mem[ptr] + 255) % 256;

C++ 解答

#include <bits/stdc++.h>

using namespace std;

int main(){
    int t;
    cin >> t;
    for (int i = 1; i <= t; ++i){
        string cmd;
        cin >> cmd;
        
        int mem[100] = {};
        int ptr = 0;
        
        for (char c : cmd){
            if (c == '>') ptr = (ptr + 1) % 100;
            else if (c == '<') ptr = (ptr + 99) % 100;
            else if (c == '+') mem[ptr] = (mem[ptr] + 1) % 256;
            else if (c == '-') mem[ptr] = (mem[ptr] + 255) % 256;
            else if (c == '.') continue;
        }
        
        cout << "Case " << i << ":";
        
        for (int i = 0; i < 100; ++i) cout << " " << uppercase << hex << setw(2) << setfill('0') << mem[i];
        
        cout << dec << setfill(' ') << '\n';
    }
}

格式控制（iomanip）：

語法	功能
`hex`	以十六進位輸出
`uppercase`	十六進位字母使用大寫
`setw(2)`	至少輸出 2 位
`setfill('0')`	不足 2 位時補 `0`

cout << dec << setfill(' ') << '\n'; 為恢復成十進位輸出格式，避免後續輸出被 hex 或 setfill('0') 影響。

4. Uva 665 - False coin

PDF Source：https://onlinejudge.org/external/6/665.pdf

Uva Online Judge：https://onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=606

Zerojudge：https://zerojudge.tw/ShowProblem?problemid=c095

難度：★★★☆☆

題目觀察

假幣只有一枚，但不知道它是比較重還是比較輕。

對某一枚硬幣 c 來說，它有兩種可能：

c 是假幣，而且比較輕。
c 是假幣，而且比較重。

因此可以直接暴力枚舉，像是假設第 1 枚是假幣且偏輕、假設第 1 枚是假幣且偏重；假設第 2 枚是假幣且偏輕、假設第 2 枚是假幣且偏重 … 以此類推。

然後檢查這個假設是否能完全符合所有秤重結果，若最後只有一個硬幣編號可能是假幣，就輸出；否則輸出 0。

解題思路

對於某個候選硬幣 coin：

假設它是輕的，可以令它的重量變化為 -1。
假設它是重的，可以令它的重量變化為 +1。

其他所有真幣重量都一樣，且題目保證左右兩邊放的硬幣數量相同，因此真幣的重量會互相抵消，只要看假幣是否出現在左盤或右盤即可。

例如假設 coin 是偏輕的話，則可能會有以下幾個情形：

coin 在左盤的話：左盤少一點，所以結果應該是 <
coin 在右盤的話：右盤少一點，所以左盤比較重，結果應該是 >
coin 不在這次秤重中的話：左右盤都是真幣，所以結果應該是 =

假設 coin 是偏重時，則上述情形的方向相反。

那在實作時要怎麼寫呢？如下：

1 2	leftWeight = 0; rightWeight = 0;

如果假幣在左盤，leftWeight += delta;。
如果假幣在右盤，rightWeight += delta;。

當中 delta 的值代表以下兩個意思：

delta = -1 表示假幣輕。
delta = 1 代表假幣重。

接著比較 leftWeight 和 rightWeight，得到這次假設下的秤重結果，檢查是否和題目給的一致，最後統計所有符合條件的硬幣編號。

需要注意的是，即使同一枚硬幣「偏重」和「偏輕」這兩個條件都能符合，也仍然屬於同一個硬幣編號，因此應用 set<int> 存候選硬幣編號，避免重複計算。

C++ 解答

#include <bits/stdc++.h>

using namespace std;

struct Weighing{
    vector <int> leftPan;
    vector <int> rightPan;
    char result;
};

char cmp(int leftWeight, int rightWeight){
    if (leftWeight < rightWeight) return '<';
    if (leftWeight > rightWeight) return '>';
    return '=';
}

bool candidate(int coin, int delta, const vector <Weighing>& weighings){
    for (const auto& w : weighings){
        int leftWeight = 0, rightWeight = 0;
        
        for (int x : w.leftPan) if (x == coin) leftWeight += delta;
        for (int x : w.rightPan) if (x == coin) rightWeight += delta;
        
        char expected = cmp(leftWeight, rightWeight);
        
        if (expected != w.result) return false;
    }
    return true;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int M;
    cin >> M;
    
    for (int tcase = 0; tcase < M; ++tcase){
        int N, K;
        cin >> N >> K;
        
        vector <Weighing> weighings;
        
        for (int i = 0; i < K; ++i){
            int P;
            cin >> P;
            
            Weighing w;
            w.leftPan.resize(P);
            w.rightPan.resize(P);
            
            for (int j = 0; j < P; ++j) cin >> w.leftPan[j];
            for (int j = 0; j < P; ++j) cin >> w.rightPan[j];
            
            cin >> w.result;

            weighings.push_back(w);
        }
        
        set<int> ans;
        
        for (int coin = 1; coin <= N; coin++) {
            // 假設 coin 是偏輕的假幣
            if (candidate(coin, -1, weighings)) ans.insert(coin);
            // 假設 coin 是偏重的假幣
            if (candidate(coin, 1, weighings)) ans.insert(coin);
        }

        if (ans.size() == 1) cout << *ans.begin() << "\n";
        else cout << 0 << "\n";

        if (tcase != M - 1) cout << "\n";
    }
}