大概刷了 50 題左右 GPE Helper 上面比較常出現的題目，根據題目類型分類做一些筆記，方便之後複習。

字串處理
Problem UVA
24941 Uncompress 245
11041 Children’s Game 10905
10582 Power Strings 10298
動態規劃
Problem UVA
23681 Bachet’s Game 10404
22181 Dollars 147
2008-28 Longest monotonically increasing subsequence
10621 Luggage 10664
23651 The jackpot 10684

字串處理

Uncompress

UVA 245

題目大意

介紹了一種文本壓縮的方式，每次遇到重新單字時，將其移入一個 list 的最前方，如果遇到已經出現過的單字，則以其在 list 中的位置來代替該單字，並且將其在 list 中再次移到最前方。現在給定一段壓縮文本，要求將其復原。

解題方法

用 getline 處理輸入，儲存使用 vector 來實現，用 erase、push_back 函數來處理 vector 中的單字。

注意事項
  • 可能會有符號與單字、數字相連的情況。
  • 輸入可能有空行。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>

using namespace std;

string str, ans, tmp;
int n;
vector<string> v;

int main(){
    while(getline(cin, str) && str != "0"){
        ans = "";
        tmp = "";
        str += "\n";
        n = 0;
        for(int k = 0; k < str.size(); k++){
            if((str[k] >= 'a' && str[k] <= 'z' ) || (str[k] >= 'A' && str[k] <= 'Z' )){ //字母
                tmp += str[k];
            }else if(str[k] >= '0' && str[k] <= '9'){ //數字
                n = n * 10 + (str[k] - '0');
            }else{ //空格、符號、換行
                if(n != 0){
                    ans += v[v.size() - n];
                    v.push_back(v[v.size() - n]);
                    v.erase(v.begin() + (v.size() - n - 1));
                    n = 0;
                }else if(tmp != ""){
                    ans += tmp;
                    v.push_back(tmp);
                    tmp = "";
                }
                ans += str[k];
            }
        }
        cout << ans;
    }
    return 0;
}

Children’s Game

UVA 10905

題目大意

給定一串數字，求出這些數字排列可以組合出的最大值。

解題方法

利用自訂的排序函數 cmp 將數字排序。

注意事項
  • 直接將輸入值以 string 儲存而不是用 int 可以方便比較。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;

bool cmp(string str1, string str2){
    return str1 + str2 > str2 + str1;
}

int n;

int main(){
    while(cin >> n && n != 0){
        vector<string> v(n);
        for(int i = 0; i < n; i++){
            cin >> v[i];
        }
        sort(v.begin(), v.end(), cmp);
        for(int i = 0; i < n; i++){
            cout << v[i];
        }
        cout << endl;
    }
    return 0;
}

Power Strings

UVA 10298

題目大意

求出一個字串的最大循環次數。
ex:
aaaaa : 5
ababab : 3
abcd : 1

解題方法

尋找字串長度的因數，並使用 substr 取子字串進行檢查。

注意事項
  • substr 的參數使用為 str.substr(起點, 長度) 而非 str.substr(起點, 終點)。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <bits/stdc++.h>

using namespace std;

string str;

int solve(string str){
    int l = str.size();
    for(int i = l; i >= 1; i--){ //由大到小
        if(l % i == 0){ //因數
            bool b = true;
            string tmp = str.substr(0, l / i); //取第一個子字串
            for(int j = 1; j < i; j++){
                if(tmp != str.substr(j * (l / i), l / i)){ //比對
                    b = false;
                    break;
                }
            }
            if(b) return i;
        }
    }
}

int main(){
    while(cin >> str && str != "."){
        cout << solve(str) << endl;
    }
    return 0;
}

動態規劃

Bachet’s Game

UVA 10404

題目大意

取石頭遊戲，給定特定數量的石頭，並且兩人輪流取石頭，能取的石頭數量為固定的幾個值，假設兩人都做出最佳選擇，求最後的勝利者。

解題方法

使用一個 vector 儲存 剩餘 i 個石頭時的勝利者，並利用動態規劃更新。

注意事項
  • 注意 dp[0] 的初始化。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>

using namespace std;

int n, m;

int main(){
    while(cin >> n >> m){
        int arr[m];
        for(int i = 0; i < m; i++){
            cin >> arr[i];
        }
        vector<int> dp(n + 1, 0); // i = 0 時第二個人勝利
        for(int i = 1; i <= n; i++){
            for(int j = 0; j < m; j++){
                if(i - arr[j] >= 0 && dp[i - arr[j]] == 0) dp[i] = 1;
            }
        }
        if(dp[n]) cout << "Stan wins" << endl;
        else cout << "Ollie wins" << endl;

    }
    return 0;
}

Dollars

UVA 147

題目大意

給定特定金額，求出可以湊出該金額的方法數。

解題方法

使用一個 vector 儲存 湊出金額 i 的方法數，並根據輸入來輸出對應的方法數。

注意事項
  • 組合數量可能超過 int 範圍。
  • 金額有小數點，儲存在表格時必須乘以 100，由小數點轉為整數時，可能會有精度的誤差，因此要加上 0.5 避免錯誤 (或是也可以處理輸入時分成整數與小數兩個部分)。
  • 注意輸出格式，可以用 printf 方便處理。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <bits/stdc++.h>

using namespace std;

vector<long long> dp(30001, 0);
int c[11] = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5};
double n;

int main(){
    dp[0] = 1;
    for(int i = 10; i >= 0; i--){
        for(int j = c[i]; j <= 30000; j++){
            dp[j] += dp[j - c[i]];
        }
    }
    while(cin >> n && n != 0){
        printf("%6.2f%17lld\n", n, dp[(int)(n * 100 + 0.5)]);
    }
    return 0;
}

Longest monotonically increasing subsequence

題目大意

給定一串數字，求出 LIS 的數量，並且印出所有 LIS。

解題方法
  • 先利用動態規劃求每個位置結尾的 LIS 長度，之後利用遞迴回推的方式列印出所有 LIS。
  • 因為數字最多只有 9 個，因此也可以直接暴力求解。
注意事項
  • 注意 LIS 數量的計算方式以及回推的方法。
程式碼1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;

void printLIS(vector<int> v, vector<int> dp, int i, vector<int>& path){
    path.push_back(v[i]);
    if(dp[i] == 1){ //回推到底
        for(int k = path.size() - 1; k >= 0; k--){
            cout << path[k] << " ";
        }
        cout << endl;
    }else{
        for(int j = i - 1; j >= 0; j--){
            if(v[j] < v[i] && dp[j] + 1 == dp[i]) printLIS(v, dp, j, path); //往前推一位
        }
    }
    path.pop_back();
    return;
}

int m;

int main(){
    cin >> m;
    while(m--){
        int n, len = 0;
        cin >> n;
        // c[i] 為以 i 為結尾的 LIS 數量
        vector<int> v(n), dp(n, 1), c(n, 1);
        for(int i = 0; i < n; i++){
            cin >> v[i];
            for(int j = 0; j < i; j++){
                if(v[j] < v[i]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        c[i] = c[j];
                    }else if(dp[j] + 1 == dp[i]){
                        c[i] += c[j];
                    }
                }
            }
            len = max(len, dp[i]); // LIS 長度
        }
        int cLIS = 0; //LIS 數量
        for(int i = 0; i < n; i++){
            if(dp[i] == len) cLIS += c[i];
        }
        cout << cLIS << endl;
        vector<int> path;
        for(int i = 0; i < n; i++){
            if(dp[i] == len) printLIS(v, dp, i, path);
        }
    }
    return 0;
}
程式碼2 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> LIS;

void findLIS(vector<int> v, vector<int> dp, int i, vector<int>& path, int len){
    if(path.size() == len){ //符合 LIS 長度
        LIS.push_back(path);
        return;
    }
    if(i == v.size()) return;
    if(path.size() == 0 || path[path.size() - 1] < v[i]){ //滿足規則，加入該數字
        path.push_back(v[i]);
        findLIS(v, dp, i + 1, path, len);
        path.pop_back();
    }
    findLIS(v, dp, i + 1, path, len); //不加入該數字
    return;
}

int m;

int main() {
    cin >> m;
    while(m--){
        LIS.clear();
        int n, len = 0;
        cin >> n;
        vector<int> v(n), dp(n, 1), c(n, 1);
        for(int i = 0; i < n; i++){
            cin >> v[i];
            for(int j = 0; j < i; j++){
                if(v[j] < v[i]) dp[i] = max(dp[i], dp[j] + 1);
            }
            len = max(len, dp[i]);
        }
        vector<int> path;
        findLIS(v, dp, 0, path, len);
        cout << LIS.size() << endl;
        for(int i = 0; i < LIS.size(); i++){
            for(int j = 0; j < len; j++){
                cout << LIS[i][j]  << " ";
            }
            cout << endl;
        }
    }
    return 0;
}

Luggage

UVA 10664

題目大意

給出一串數字，代表各個行李的重量，找出是否能夠將行李分為同樣重量的兩堆。

解題方法

首先統計行李總重量以及數量，如果為奇數則直接輸出否，之後利用動態規劃判斷是否能夠湊出 總重量 / 2 這個重量，類似硬幣問題，但是每個硬幣只能使用一次。

注意事項
  • 輸入是一行一行的，並不知道行李數量，因此輸入用 getline 和 stringstream 處理。
  • 每個行李只有一個，動態規劃遍歷重量時的順序應該是由後往前，避免重複使用。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

int n;
string str, s;

int main(){
    cin >> n;
    getline(cin, str);
    while(n--){
        getline(cin, str);
        vector<int> v;
        stringstream ss(str);
        int ws = 0;
        while(ss >> s){
            int k = 0;
            for(int i = 0; i < s.size(); i++){
                k = k * 10 + (s[i] - '0');
            }
            v.push_back(k);
            ws += k;
        }
        if(ws % 2 == 1 || v.size() % 2 == 1){ //判斷總重量與數量
            cout << "NO" << endl;
            continue;
        }
        vector<int> dp(ws / 2 + 1, 0);
        dp[0] = 1;
        for(int i = 0; i < v.size(); i++){
            for(int j = dp.size() - 1; j >= v[i]; j--){ //由後往前
                if(dp[j - v[i]] == 1) dp[j] = 1;
            }
        }
        if(dp[dp.size() - 1] == 1) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

The jackpot

UVA 10684

題目大意

給出一串數字，代表每次賭注的收益，可能有正(賺錢)有負(賠錢)，求出一段連續的投注可以獲得的最高收益，如果可以獲得正收益，則輸出最大收益，否則輸出否。

解題方法

最大子數列問題，使用 Kadane’s Algorithm 求最大值。

注意事項
  • 如果最大值為 0 則同樣無法獲得正收益，要注意判斷。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>

using namespace std;

int n;

int main(){
    while(cin >> n && n != 0){
        vector<int> v(n);
        for(int i = 0; i < n; i++){
            cin >> v[i];
        }
        int cursum = 0, maxsum = v[0];
        for(int i = 0; i < n; i++){
            cursum = max(cursum + v[i], v[i]);
            maxsum = max(maxsum, cursum);
        }
        if(maxsum <= 0) cout << "Losing streak." << endl; //包括 0
        else cout << "The maximum winning streak is " << maxsum << "." << endl;
    }
    return 0;
}