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

本次題庫擷取自 CPE 2025/12/09 歷屆考題。

1. Uva 10079 - Pizza Cutting

PDF Source：https://onlinejudge.org/external/100/10079.pdf

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

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

解題思路：

先從最小情況 base case N = 0 開始推算起：

• N = 0：表示不切，輸出 1 塊。
• N = 1：切 1 刀，輸出 2 塊。
• N = 2：切 2 刀，且第 2 刀要跟第 1 刀相交才能切最多塊，輸出 2 + 2 = 4 塊。
• N = 3：切 3 刀，第 3 刀要跟前 2 刀相交才能切最多塊，輸出 4 + 3 = 7 塊。

到這邊就可以推導公式了：第 $n$ 刀最多可以跟前面的 $n - 1$ 條線相交，從而創造出 $n$ 個新區塊，可求得遞迴式：$f(n) = f(n - 1) + n$

建議本題使用 for 迴圈寫遞迴式，若要用函數方法寫遞迴式，則需要使用 Dynamic Programming 的技巧，不然很容易超時。

另一種方式則是將這個遞迴式展開：$f(n) = 1 + (1 + 2 + 3 + \cdots + n)$

整理一下得到：$f(n) = 1 + \frac{n(n + 1)}{2}$

範例程式碼：

#include <iostream>

using namespace std;

using ll = long long;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    ll N;
    while (cin >> N && N >= 0){
        ll ans = 1 + N * (N + 1) / 2;
        cout << ans << '\n';
    }
}

2. Uva 11321 - Sort! Sort!! and Sort!!!

PDF Source：https://onlinejudge.org/external/113/11321.pdf

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

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

解題思路：

該題意圖很明顯了，就是要叫你用自訂排序。本人使用 lambda 函式進行自訂排序，記得要捕捉變數 M 進來，因為他是外部變數。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int N, M;
    while (cin >> N >> M && (N != 0 && M != 0)){
        vector <int> num(N);
        for (int i = 0; i < N; ++i) cin >> num[i];
        sort(num.begin(), num.end(), [M](const int& a, const int& b){
            int ma = a % M, mb = b % M;
            if (ma != mb) return ma < mb; // 前小後大 -> 升序
            
            bool a_odd = a % 2 != 0;
            bool b_odd = b % 2 != 0;
            
            // 假設 b_odd = false;
            if (a_odd != b_odd) return a_odd; // 奇數在前
            
            if (a_odd && b_odd) return a > b; // 大奇數在前 -> 表示就要降序
            
            return a < b; // 小偶數在前 -> 表示就要升序
        });
        
        cout << N << " " << M << '\n';
        for (const int& i : num){
            cout << i << '\n';
        }
    }
    cout << "0 0\n";
}

3. Uva 706 - LC-Display

PDF Source：https://onlinejudge.org/external/7/706.pdf

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

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

解題思路：

這題難的地方在於你不能一個一個數字去做輸出，而是要一次就把題目要求的輸入全部寫出來。

橫線是一個 dash（-），而直線則為管線符號（|）。

首先可將一個數字的 LCD 顯示拆解成 5 個區域依序輸出：

• 頂部（Top）：橫線區域。
• 上半部（Upper Vertical）：直線區域（高度 s）。
• 中間（Middle）：橫線區域。
• 下半部（Lower Vertical）：直線區域（高度 s）。
• 底部（Bottom）：橫線區域。

另外每個數字的寬度是 s + 2（左直線 + s 寬度 + 右直線），數字之間要有一個空白分隔。

本題可以使用查表的方式進行，可以先做出 0~9 數字的橫線、直線是否有無的陣列：

H_RISK 代表橫線區域，1 就是有橫線，0 就是沒有。分成三個區域：Top、Mid、Bot，每個區域都有對應的 0 ~ 9 數字。

const int H_RISK[3][10] = {
    {1, 0, 1, 1, 0, 1, 1, 1, 1, 1}, // Top (頂部)
    {0, 0, 1, 1, 1, 1, 1, 0, 1, 1}, // Mid (中間)
    {1, 0, 1, 1, 0, 1, 1, 0, 1, 1}  // Bot (底部)
};

V_RISK 代表直線區域，0 = 沒東西、1 = 左邊、2 = 右邊、3 = 兩邊。

const int V_RISK[2][10] = {
    {3, 2, 2, 2, 3, 1, 1, 2, 3, 3}, // Upper (上半部)
    {3, 2, 1, 2, 2, 2, 3, 2, 3, 2}  // Lower (下半部)
};

接下來就是實作繪製橫線、直線的函式，當中會頻繁用到變數 s，這時候把他設在全域變數會比較好，以免在主函式還要再輸入 s 引數，會比較麻煩。當中 rowType 參數則是 Top、Mid、Bot、Upper、Lower。

void drawH(int rowType) {
    for (int i = 0; i < n_str.length(); ++i) {
        int digit = n_str[i] - '0';
        
        // 數字間的間隔
        // 除了第一個數字以外都要先印空白
        if (i > 0) cout << " "; 

        cout << " "; // 左上/左下角的空白角落
        for (int k = 0; k < s; k++) {
            if (H_RISK[rowType][digit]) cout << "-";
            else cout << " ";
        }
        cout << " "; // 右上/右下角的空白角落
    }
    cout << '\n';
}

void drawV(int rowType) {
    // 直線的高度是 s 所以要重複 s 次
    for (int line = 0; line < s; ++line) {
        for (int i = 0; i < n_str.length(); ++i) {
            int digit = n_str[i] - '0';
            int type = V_RISK[rowType][digit];

            if (i > 0) cout << " ";

            // 左邊的線
            if (type == 1 || type == 3) cout << "|";
            else cout << " ";

            // 中間的空白
            for (int k = 0; k < s; k++) cout << " ";

            // 右邊的線
            if (type == 2 || type == 3) cout << "|";
            else cout << " ";
        }
        cout << '\n';
    }
}

最後在主函式呼叫這些函式即可，要為 rowType 從上到下填入參數。

範例程式碼：

#include <bits/stdc++.h>

using namespace std;

const int H_RISK[3][10] = {
    {1, 0, 1, 1, 0, 1, 1, 1, 1, 1},
    {0, 0, 1, 1, 1, 1, 1, 0, 1, 1},
    {1, 0, 1, 1, 0, 1, 1, 0, 1, 1}
};

const int V_RISK[2][10] = {
    {3, 2, 2, 2, 3, 1, 1, 2, 3, 3},
    {3, 2, 1, 2, 2, 2, 3, 2, 3, 2},
};

int s;
string n_str;

void drawH(int rowType){
    for (int i = 0; i < n_str.length(); ++i){
        int digit = n_str[i] - '0';
        
        if (i > 0) cout << " ";
        
        cout << " ";
        for (int k = 0; k < s; ++k){
            if (H_RISK[rowType][digit]) cout << "-";
            else cout << " ";
        }
        cout << " ";
    }
    cout << '\n';
}

void drawV(int rowType){
    for (int line = 0; line < s; ++line){
        for (int i = 0; i < n_str.length(); ++i){
            int digit = n_str[i] - '0';
            int type = V_RISK[rowType][digit];
            
            if (i > 0) cout << " ";
            
            if (type == 1 || type == 3) cout << "|";
            else cout << " ";
            
            for (int k = 0; k < s; ++k) cout << " ";
            
            if (type == 2 || type == 3) cout << "|";
            else cout << " ";
        }
        cout << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    while (cin >> s >> n_str && (s != 0 || n_str != "0")){
        drawH(0);
        drawV(0);
        drawH(1);
        drawV(1);
        drawH(2);
        
        cout << '\n';
    }
}