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

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

1. Uva 10591 - Happy Number

PDF Source：https://onlinejudge.org/external/105/10591.pdf

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

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

難度：★☆☆☆☆

題目翻譯：

令正整數 $S_0$ 的平方和表示為 $S_1$ 。同理，令 $S_1$ 的平方和用 $S_2$ 表示，依此類推。若對某個 $i ≥ 1$ 的 $S_i = 1$ ，則原始整數 $S_0$ 稱為快樂數（Happy Number）。一個不快樂的數字稱為不快樂數（Unhappy Number）。例如，7 是快樂數，因為 $7 → 49 → 97 → 130 → 10 → 1$ ；而 4 不是快樂數： $4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4$ 。

Input:

輸入包含多個測資，輸入的第一行會給出測資的數量。每個測資由一條包含小於 $10^9$ 的正整數 $N$ 的行組成。

Output:

對於每個測資，你必須印出以下訊息之一：

1 2	Case #p: N is a Happy number. Case #p: N is an Unhappy number.

這裡 $p$ 代表測資編號（從 1 開始）。如果數字 $N$ 是快樂數，你應該印出第一則訊息；否則，列印第二行。

Sample Input:

Sample Output:

1
2
3

Case #1: 7 is a Happy number.
Case #2: 4 is an Unhappy number.
Case #3: 13 is a Happy number.

解題思路:

計算每位的平方和，可以透過輔助函式（我在此定義為 getNext()）來計算，以免寫在 main() 裡面，只能用一次就沒了。

接著可以用 int curr = n 去追蹤 Happy Number，以及利用 std::set 的不重複特性來求解。

具體做法是寫一個 while()，可以判斷當 curr 為 1 的時候停下，但這樣還不夠，還要額外判斷 curr 是否重複了（即 seen.find(curr) != seen.end()，若該份數字未在 seen 裡面找到，就繼續執行迴圈）。

Code:

#include <bits/stdc++.h>

using namespace std;

int getNext(int n) {
    int sum = 0;
    while (n > 0) {
        int digit = n % 10;
        sum += digit * digit;
        n /= 10;
    }
    return sum;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);

    int t;
    if (cin >> t) {
        for (int p = 1; p <= t; ++p) {
            int n;
            cin >> n;
            
            int curr = n;
            unordered_set<int> seen; 
            // 這裡用 unordered_set 是因為這題用不到有序的 可以拿來稍微提速

            while (curr != 1 && seen.find(curr) == seen.end()) {
                seen.insert(curr);
                curr = getNext(curr);
            }
            
            cout << "Case #" << p << ": " << n << (curr == 1 ? " is a Happy number.\n" : " is an Unhappy number.\n");
        }
    }

    return 0;
}

2. Uva 10010 - Where’s Waldorf?

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

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

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

難度：★★☆☆☆

題目翻譯：

給定一個 $m \times n$ 個字母格網格（ $1 \le m, n \le 50$ ）及一串單字，找出該單字所在的網格位置。

一個單字會對應格子中一條直線、不間斷的字母線。
一個單字可以與格子中的字母匹配，不論大小寫（即大寫和小寫字母應視為相同）。
匹配可在八個方向中任意進行，可以是水平、垂直或斜向穿越網格。

Input:

輸入以一行上的一個正整數開始，該整數本身表示後續情況的數量，每個情況如下所述。這行後面跟著一行空白，兩個連續輸入之間也有一行空行。

輸入以一對整數 $m$ 開始，後面以 $n, 1 \le m,n \le 50$ （十進位表示）在單一行上。

接下來的 $m$ 行每行包含 $n$ 個字母；此為必須要找到的列表中單字的字母格子。格子中的字母可以是大寫或小寫。沿著字母格線，另一整數 $k$ 獨立出現在一行上（ $1 \le k \le 20$ ）。接下來的 $k$ 行輸入包含要搜尋的單字清單，每行一個單字。這些單字可能只包含大寫和小寫字母（不包含空格、連字號或其他非字母字母）。

Output:

每個測資的輸出必須遵循以下描述：

兩個連續測資的輸出會以空白行分隔。
對於字串中的每個字，必須輸出一對整數，代表該字在網格中的位置。
整數之間必須間隔一個空格。
第一個整數是網格中該單字首字母所在的行（ $1$ 代表格子最頂端的行， $m$ 代表最底的行）。
第二個整數是網格中能找到該單字第一個字母的列（ $1$ 代表格子最左邊的列， $n$ 代表最右邊的列）。
如果一個單字能在網格中出現多於一次，則輸出的位置應對應該單字最上面的位置（即該單字第一個字母最接近網格頂端的位置）。
如果兩個或以上的字在最上面，輸出應該對應這些出現中最左邊的那個。
所有單字至少在格子中出現一次。

Sample Input:

1

8 11
abcDEFGhigg
hEbkWalDork
FtyAwaldORm
FtsimrLqsrc
byoArBeDeyv
Klcbqwikomk
strEBGadhrb
yUiqlxcnBjf
4
Waldorf
Bambi
Betty
Dagbert

Sample Output:

解題思路:

看到有八個方向，所以可以先定義好這八個方向（避免寫一堆 if-else 很麻煩）：

1
2
3

            //  左上  上 右上 左 右 左下 下 右下
const int dx[] = {-1, -1, -1, 0 , 0,  1, 1, 1};
const int dy[] = {-1,  0,  1, -1, 1, -1, 0, 1};

dx 管的是上下，dy 管左右。

另外題目還有說大小寫是不區分的，所以可以在輸入的時候，就把字串中的每個字元統一轉成大寫或是小寫，在這邊我全部轉小寫。

在後續的 k 輸入測資部分，可以用 string word;、cin >> word; 的方式讀字串，不用額外為了他再建一個 vector。

接著就是從最外層的 x 開始，再套一個內層 y 的 for 迴圈去跑這 2D 的 vector，如果在跑的過程中有遇到跟 word[0] 開頭一樣的字：

跑 for(int d = 0; d < 8; ++d) 的迴圈。
裡面設 int nx = x, ny = y 表示現在的位置。
int idx; 用來算字數的，如果字數跟 word 是一樣的話，就表示已經找到了。

之後跑 for (idx = 1; idx < len; ++idx) 迴圈，主要是往一個方向一直跑，如果碰到邊界、grid[nx][ny] 跟 word[nx][ny] 對不上的話，就 break，換一個方向走。

Code:

#include <bits/stdc++.h>

using namespace std;
            //  左上  上 右上 左 右 左下 下 右下
const int dx[] = {-1, -1, -1, 0 , 0,  1, 1, 1};
const int dy[] = {-1,  0,  1, -1, 1, -1, 0, 1};

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--){
        int m, n;
        cin >> m >> n;
        
        vector <string> grid(m);
        for (int i = 0; i < m; ++i){
            cin >> grid[i];
            for (int j = 0; j < n; ++j) grid[i][j] = tolower(grid[i][j]);
        }
        
        int k;
        cin >> k;
        while (k--){
            string word;
            cin >> word;
            
            for (char& c : word) c = tolower(c);
            
            int len = word.size();
            bool found = false;
            
            for (int x = 0; x < m && !found; ++x){
                for (int y = 0; y < n && !found; ++y){
                    if (grid[x][y] == word[0]){
                        for (int d = 0; d < 8; ++d){
                            int nx = x, ny = y;
                            int idx;
                            
                            for (idx = 1; idx < len; ++idx){
                                nx += dx[d];
                                ny += dy[d];
                                
                                if (nx < 0 || nx >= m || ny < 0 || ny >= n) break;
                                if (grid[nx][ny] != word[idx]) break;
                            }
                            
                            if (idx == len){
                                cout << x + 1 << " " << y + 1 << '\n';
                                found = true;
                                break;
                            }
                        }
                    }
                }
            }
        }
        if (t > 0) cout << '\n';
    }
}

3. Uva 10226 - Hardwood Species

CPE 49 必考題，這就不說了，詳細請至：https://hackmd.io/@LukeTseng/S1ztO0-vel#43-Hardwood-Species

4. Uva 10365 - Blocks

PDF Source：https://onlinejudge.org/external/103/10365.pdf

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

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

難度：★★★☆☆

題目翻譯：

Donald 想送一份禮物給他的新侄子 Fooey。Donald 是個有點傳統的人，所以他選擇送一組由 $N$ 個經典嬰兒積木組成的禮物。每個積木都是一個 $1$ 英寸乘以 $1$ 英寸乘以 $1$ 英寸的正方體。Donald 想把這些積木堆疊成一個長方體，並用牛皮紙包裝起來以便寄送。請問 Donald 需要多少牛皮紙？

Input:

輸入的第一行包含一個整數 $C$ ，代表測資的數量。對於每個測資，會額外提供一行包含一個整數 $N$ ，即要運送的積木數量。 $N$ 不會超過 1000。

Output:

你的程式應針對每個測資產生一行輸出，給出將積木堆疊在一起時，包裝所需的最少紙張面積（單位為平方英寸）。

Sample Input:

Sample Output:

題目說明:

現在有 $N$ 個大小完全一樣的積木（每個都是 1x1x1 的小正方體），要把這 $N$ 個積木全部用上，拼成一個實心的、沒有空隙的大長方體，最後用牛皮紙把整個大長方體包裝起來。

題目問的是要找出哪一種拼法可以最省包裝紙，並算出最少需要多少面積的紙。

從題目給出的資訊，可以得出以下這些資訊：

積木總數 $N$ 就是長方體的體積。
包裝紙的用量就是長方體的表面積。
要找出三個正整數來代表長方體的長（ $L$ ）、寬（ $W$ ）、高（ $H$ ）。

限制條件： $L \times W \times H = N$ （確保剛好用完 $N$ 個積木）。

求解公式：在滿足上述條件下，讓表面積公式 $2(L \times W + W \times H + H \times L)$ 的計算結果達到最小值。

解題思路:

這題即為窮舉法，因為 $N$ 最高只到 $1000$ ，另外有些地方是可以做剪枝的，如下：

避免重複計算相同的組合（例如 $1 \times 2 \times 5$ 和 $2 \times 1 \times 5$ ），可強制規定邊長的大小關係為 $L \le W \le H$ 。
基於上述規定，最小的邊 $L$ 絕對不可能大於 $N$ 的立方根，所以在第一層迴圈中，條件設為 l * l * l <= n 即可。
當確定 $L$ 後，剩下的兩邊乘積為 $N / L$ （ $W \times H = N / L$ ），第二小的邊 $W$ 必須 >= $L$ ，且絕對不可能大於 $N / L$ 的平方根，所以第二層迴圈條件為 w * w <= remain， remain 是剩下的面積 $N / L$ 。

接著在雙重迴圈中，透過取餘數 % 來檢查當前的 $L$ 和 $W$ 是否能整除總數，如果可以，就能算出第三個邊 $H$ ，然後套用表面積公式，用 min() 去做比較跟更新。

:::info
至於最小的邊 $L$ 絕對不可能大於 $\sqrt[3]{N}$ ，這個是因為前面已經限制 $L \le W \le H$ ，假設 $W = H = L$ ，則 $L^3 \le N \rightarrow L \le \sqrt[3]{N}$ ，因此得到最小的邊 $L$ 絕不可能大於 $\sqrt[3]{N}$ ，而第二小的邊 $W$ 絕對不可能大於 $N / L$ 的平方根的原理也是同理。
:::

Code:

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        
        int min_area = INT_MAX;
        for (int l = 1; l * l * l <= n; ++l){
            if (n % l == 0){
                int remain = n / l;
                
                for (int w = l; w * w <= remain; ++w){
                    if (remain % w == 0){
                        int h = remain / w;
                        
                        min_area = min(min_area, 2 * (l * w + w * h + h * l));
                    }
                }
            }
        }
        
        cout << min_area << '\n';
    }
}

5. Uva 11039 - Building designing

PDF Source：https://onlinejudge.org/external/110/11039.pdf

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

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

難度：★★☆☆☆

題目翻譯：

一位建築師想要設計一棟非常高的建築。這棟建築由若干樓層組成，且每一層樓都有特定的尺寸。每一層樓的尺寸必須大於其正上方那一層樓的尺寸。此外，設計師（他是某支著名西班牙足球隊的粉絲）想要將建築塗成藍色和紅色，每一層塗一種顏色，且規定相鄰兩個樓層的顏色必須不同。

為了設計這棟建築，建築師擁有 $n$ 個可用的樓層，並已知它們各自的尺寸與顏色。所有可用樓層的尺寸皆不相同。建築師希望在滿足上述限制的情況下，利用這些可用樓層設計出最高（樓層數最多）的建築。

Input:

輸入檔案的第一行包含一個整數 $p$ ，代表需要求解的測資數量。每個測資的第一行包含可用樓層的數量。接著，每一行會出現一個樓層的尺寸與顏色，由一個介於 $-999999$ 到 $999999$ 之間的整數表示（不包含 0）。

負數代表紅色樓層。
正數代表藍色樓層。
樓層的尺寸即為該數字的絕對值。
不存在兩個尺寸相同的樓層。
單一問題的最大樓層數為 $500,000$ 。

Output:

針對每個測資，輸出應包含一行文字，顯示在上述條件下所能建出的最高建築之樓層總數。

Sample Input:

Sample Output:

1
2

2
5

解題思路:

這題就是貪婪+排序。

要蓋出最高的建築，目標就是盡可能選多一點的樓層，根據題目限制，樓層必須滿足兩個條件：

尺寸限制：由下到上，樓層的絕對值要嚴格遞減（底層最大，頂層最小）。
顏色限制：相鄰樓層的顏色必須不同（即正負號交替）。

在尺寸限制上，可以先做排序，但會有個問題就是顏色問題（有正有負），這部分在排序函式裡面加個絕對值即可。

顏色限制上，可以透過兩個變數來做到：int color = (floor[i] > 0) ? 1 : -1; 表示現在的顏色，int lastColor = 0; 表示最後的顏色是什麼。

如果 lastColor == 0 表示還沒有任何顏色，樓高可以 ++，並更新 lastColor；若下一輪 lastColor != color，就表示現在的顏色跟上一個顏色不同。

Code:

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        
        vector <int> floor(n);
        for (int i = 0; i < n; ++i) cin >> floor[i];
        
        sort(floor.begin(), floor.end(), [](int a, int b){
            return abs(a) > abs(b);
        });
        
        int maxH = 0, lastColor = 0;
        
        for (int i = 0; i < n; ++i){
            int color = (floor[i] > 0) ? 1 : -1;
            
            if (lastColor == 0 || color != lastColor){
                maxH++;
                lastColor = color;
            }
        }
        
        cout << maxH << '\n';
    }
}

6. Uva 11526 - H(n)

PDF Source：https://onlinejudge.org/external/115/11526.pdf

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

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

難度：★★★★★

題目翻譯：

以下 C++ 函式會回傳出什麼值？

long long H(int n){
    long long res = 0;
    for( int i = 1; i <= n; i=i+1 ){
        res = (res + n/i);
    }
    return res;
}

Input:

第一行輸入為整數 $T$ （ $T \le 1000$ ），表示測資數量，接下來的每 $T$ 行都會包含一個有號的 32 位元整數 $n$ 。

Output:

對於每個測資，輸出只會有一行包含 $H(n)$ 。

Sample Input:

1
2
3

2
5
10

Sample Output:

1
2

10
27

解題思路:

題目的時限是 5 秒，而且 $n$ 最大可到 20 億，測資又有 1000 筆，如果照寫程式碼的話，時間複雜度會是 $O(n)$ ，絕對會超時，因此要想辦法降到 $O(\sqrt{n})$ 。

在此會用到的一種技巧叫做 Square Root Decomposition，稱之為分塊。

來觀察一下 $n/i$ 在這段函式裡的的變化。假設 $n = 10$ ：

$i = 1$ ： $10 / 1 = 10$
$i = 2$ ： $10 / 2 = 5$
$i = 3$ ： $10 / 3 = 3$
$i = 4$ ： $10 / 4 = 2$
$i = 5$ ： $10 / 5 = 2$
$i = 6$ ： $10 / 6 = 1$
$i = 7$ ： $10 / 7 = 1$
$i = 8$ ： $10 / 8 = 1$
$i = 9$ ： $10 / 9 = 1$
$i = 10$ ： $10 / 10 = 1$

會發現在這裡面，隨著 $i$ 變大， $n/i$ 的結果會出現大量重複的區塊，像是當 $i$ 從 6 到 10 時， $n/i$ 的值都是 1。

既然值都一樣，就不用一個一個慢慢加，而是可以直接算出這個區塊的長度，然後用乘法一次加總起來。

如果已知目前區塊的起點是 $i$ ，那與 $n/i$ 擁有相同商數的區塊終點 $j$ 可以用以下公式求出：$$j = \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$$

知道起點 $i$ 和終點 $j$ 後，區塊的總和即：(j - i + 1) * (n / i)

這怎麼求的？

假設現正在處理某個特定的數字 $i$ （區塊的起點），且已知 $n$ 除以 $i$ 的商數，則令商數為 $k$ ：$$k = \lfloor \frac{n}{i} \rfloor$$

目標是要找到一個最大的整數 $j$ ，使得 $n$ 除以 $j$ 的商數仍然等於 $k$ ，即要滿足以下條件，並且讓 $j$ 盡可能大：$$\lfloor \frac{n}{j} \rfloor = k$$

根據 floor 函數 $\lfloor x \rfloor$ 的定義，如果 $\lfloor x \rfloor = k$ ，就表示 $x$ 必定落在 $k$ （含）與 $k + 1$ （不含）之間。

因此，可將 $\lfloor \frac{n}{j} \rfloor = k$ 轉換成不等式：$$k \le \frac{n}{j} < k + 1$$

接下來透過代數運算，把 $j$ 獨立出來，首先要將整個不等式取倒數（要注意因為 $k, n, j$ 都是正整數，取倒數時不等號方向會反轉）：$$\frac{1}{k + 1} < \frac{j}{n} \le \frac{1}{k}$$

然後把不等式的每一項都乘上 $n$ ：$$\frac{n}{k + 1} < j \le \frac{n}{k}$$

看到這裡，再把以上這條對照 floor 函數的定義，最後你就會得出：$$j = \lfloor \frac{n}{k} \rfloor$$

然後再把 k 代回去得到這個公式的模樣：$$j = \lfloor \frac{n}{\lfloor \frac{n}{i} \rfloor} \rfloor$$

在 C++ 不用特地寫 floor() 因為 C++ 的 / 本身就在做這件事情了。

Code:

#include <iostream>

using namespace std;

long long H(int n){
    long long res = 0;
    // 迴圈小改: int 改 long long
    // i = i + 1 改成 i = j + 1 (因為那個區塊算完就直接從終點 j 跳比較快)
    for( long long i = 1, j; i <= n; i=j +1 ){
        j = n / (n / i);
        res += (j - i + 1) * (n / i);
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--){
        int n;
        cin >> n;
        cout << H(n) << '\n';
    }
}

7. Uva 12063 - Zeros and Ones

PDF Source：https://onlinejudge.org/external/120/12063.pdf

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

No Zerojudge.

難度：★★★☆☆

題目翻譯：

二進位數字及其位元模式對電腦程式設計師來說總是非常有趣。在這個問題中，你需要計算符合以下性質的正二進位數字的數量：

這些數字的長度剛好是 $N$ 個位元，且沒有前導零。
零和一出現的頻率相等。
這些數字是 $K$ 的倍數。

Input:

輸入檔包含多組測資。輸入的第一行給出測資的數量 $T$ （ $1 \le T \le 100$ ）。接下來會有 $T$ 組測資，每組測資佔一行。每組測資的輸入包含兩個整數 $N$ （ $1 \le N \le 64$ ）和 $K$ （ $0 \le K \le 100$ ）。

Output:

對於每組輸入，首先印出測資的編號。然後印出具備上述性質的二進位數字的數量。

圖例：下表顯示了一些範例測資可能出現的數字：

【Uva 題庫解題】C++ 個人解題筆記 - part6 - 7. Uva 12063 - Zeros and Ones

Sample Input:

Sample Output:

Case 1: 1
Case 2: 3
Case 3: 6
Case 4: 1662453
Case 5: 465428353255261088

解題思路:

此為動態規劃（DP）演算法問題。

這題要在給定的長度 $N$ 中，構造出滿足特定條件的二進位數字，並計算總共有幾種合法組合，不用真的把這些數字印出來，只需要計算數量即可，看到這裡就知道這題是 DP 了。

可用由左至右逐位填寫二進位數字的方式來思考，對於每個位置，僅可填入 0 或 1。

狀態定義：

要確定走到目前這一步時的狀態，首先要知道三件事：

idx：目前填了多少個位元（從左邊數）。
rem：目前構造出的數字，除以 $K$ 的餘數是多少。
ones：目前填了多少個 1。

在此建立一個三維陣列 dp[idx][rem][ones] 來存狀態，避免重複計算。

轉移式：

當於第 idx 位要往下填入數字時，有兩種選擇：

填 0：數字向左移一位，new_rem = (rem * 2 + 0) % K，1 的數量不變。
填 1：數字向左移一位並加一， new_rem = (rem * 2 + 1) % K。1 的數量++。

註：rem * 2 是因為現在在算二進位。

Code:

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

int N, K;
long long dp[65][105][65]; 

long long dfs(int idx, int rem, int ones) {
    if (idx == N) { // 填滿 N 個位元結束
        if (rem == 0 && ones * 2 == N) {
            return 1;
        }
        return 0;
    }
    
    if (dp[idx][rem][ones] != -1) {
        return dp[idx][rem][ones];
    }
    
    long long ans = 0;
    
    ans += dfs(idx + 1, (rem * 2) % K, ones);
    ans += dfs(idx + 1, (rem * 2 + 1) % K, ones + 1);

    return dp[idx][rem][ones] = ans;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(nullptr);
    
    int T;
    if (cin >> T) {
        for (int tcase = 1; tcase <= T; tcase++) {
            cin >> N >> K;
            
            cout << "Case " << tcase << ": ";
            
            // N 是奇數不能把 0 跟 1 平分
            // K 是要跟別人做 mod 不能等於 0
            if (N % 2 != 0 || K == 0) { 
                cout << "0\n";
                continue;
            }
            
            memset(dp, -1, sizeof(dp));
            
            long long result = dfs(1, 1 % K, 1); // 由於沒前導 0，第一位填 1
            
            cout << result << '\n';
        }
    }
}