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

Map
Problem UVA
10579 Hay Points 10295
10520 Conformity 11286
Array
Problem UVA
21964 Fill the Containers 11413
23551 Largest Square 10908
10437 Zeros and Ones 10324
暴力法
Problem UVA
10655 Sumsets 10125
10417 The Hotel with Infinite Rooms 10170
22351 Quirksome Squares 256

Map

Hay Points

UVA 10295

題目大意

首先會列出數個單字以及其所對應的價值，之後會有幾段文字，根據文字中出現的單字計算其總價值，如果單字沒有寫出其對應價值，代表價值為 0。

解題方法

使用 Map 儲存列出的單字以及其價值，之後遍歷整段文字，利用 count 判斷單字的價值並加總。

注意事項
  • 要判斷的文字可能有多行，並且用 . 間隔。
程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>

using namespace std;

int m, n, k;
string str;
map<string, int> dict;

int main(){
    cin >> m >> n;
    while(m--){
        cin >> str >> k;
        dict[str] = k;
    }
    while(n--){
        int c = 0;
        while(cin >> str && str != "."){
            if(dict.count(str) != 0) c += dict[str]; //檢查是否有價值
        }
        cout << c << endl;
    }
    return 0;
}

Conformity

UVA 11286

題目大意

輸入包含若干行，每行有五個數字代表學生修習的課程，找到最多人選擇的課程組合有幾個學生選擇，如果有兩個或以上的組合有相同數量的學生選擇，則將他們的選擇人數相加。

解題方法
  • 將輸入的五個課程排序之後作為 Map 的 key，並且每次更新 Map 時紀錄最多人選擇的組合有幾人選擇，之後利用 iterator 遍歷 Map 統計人數。
  • 也可以選擇將課程排序之後轉為 string 並作為 Map 的 key。
注意事項
  • 一定要將輸入的課程排序之後再儲存。
程式碼 
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
#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> v(5);

int main(){
    while(cin >> n && n != 0){
        map<vector<int>, int> m;
        int ma = -1, c = 0;
        while(n--){
            for(int i = 0; i < 5; i++){
                cin >> v[i];
            }
            sort(v.begin(), v.end()); //排序
            if(m.count(v) != 0) m[v]++;
            else m[v] = 1;
            if(m[v] > ma) ma = m[v];
        }
        for(auto i = m.begin(); i != m.end(); i++){
            if(i->second == ma) c += (i->second);
        }
        cout << c << endl;
    }
    return 0;
}

Array

Fill the Containers

UVA 11413

題目大意

有好幾瓶不同容量的牛奶，現在要將其重新分配到幾個瓶子中，每瓶牛奶只能裝到一個瓶子中，不能分配到好幾個瓶子裡，而且只能按照牛奶的順序進行分配，求分配後最大容量的瓶子所需的最小值。
ex:
3 瓶牛奶容量分別為 4, 78, 9，分配到 2 瓶子中，最大容量的瓶子最少需要 4 + 78 = 82，不能分成 4 + 9, 78 因為這樣沒有按照順序。

解題方法

使用二分搜尋，每次判斷是否能夠滿足分配規則，不能滿足就把數字放大，否則把數字縮小，直到找到最小的容量。

注意事項
  • 紀錄牛奶容量的總和可以作為二分搜尋的上限。
程式碼 
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
#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<int> v(1000);

bool check(int x, int n, int m){ //檢查是否滿足分配規則
    int c = 0, tmp = 0;
    for(int i = 0; i < n; i++){
        if(tmp + v[i] > x){
            if(v[i] > x) return false;
            tmp = v[i];
            c++;
        }else tmp += v[i];
    }
    return (c + 1 <= m);
}

int main(){
    while(cin >> n >> m){
        int l = 1, r = 0;
        for(int i = 0; i < n; i++){
            cin >> v[i];
            r += v[i];
        }
        while(r > l){ //二分搜尋
            int mid = (l + r) / 2;
            if(check(mid, n, m)) r = mid;
            else l = mid + 1;
        }
        cout << l << endl;
    }
    return 0;
}

Largest Square

UVA 10908

題目大意

給定一個二維矩陣，裡面包含不同字母，之後輸入一個座標，求以該座標為中心的同字母正方形之最大邊長。

解題方法

由中心開始，每次往外檢查一圈，直到出現不同的字母就停下。

注意事項
  • 注意陣列的邊界。
程式碼 
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
#include <bits/stdc++.h>

using namespace std;

int solve(vector<vector<char>> v, int r, int c){
    int i = 1;
    char t = v[r][c];
    for(; i < max(v.size(), v[0].size()); i++){
        if(r + i >= v.size() || r - i < 0 || c + i >= v[0].size() || c - i < 0) break; //檢查邊界
        int j = 0;
        for(; j < i * 2; j++){ //檢查最外圈
            if(v[r + i][c - i + j] != t || v[r + i - j][c + i] != t || v[r - i][c + i - j] != t || v[r - i + j][c - i] != t) break;
        }
        if(j != i * 2) break;
    }
    return i * 2 - 1;
}

int t, m, n, q, r, c;

int main(){
    cin >> t;
    while(t--){
        cin >> m >> n >> q;
        cout << m << " " << n << " " << q << endl;
        vector<vector<char>> v(m, vector<char>(n));
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                cin >> v[i][j];
            }
        }
        while(q--){
            cin >> r >> c;
            cout << solve(v, r, c) << endl;
        }
    }
    return 0;
}

Zeros and Ones

UVA 10324

題目大意

給定一個由 0 和 1 組成的字串，之後會有數個查詢，每次查詢一個範圍內的數字是否都是相同的，如果範圍內都是同樣的 0 或是 1 則返回正確，否則返回錯誤。

解題方法

另外建立一個陣列儲存前綴和，並利用區間的數字總和判斷區間內是否都是 0 或是 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
#include <bits/stdc++.h>

using namespace std;

string str;
int c = 1, q, a, b;

int main(){
    while(cin >> str){
        cout << "Case " << c << ":" << endl;
        c++;
        vector<int> v(str.size() + 1, 0);
        for(int i = 0; i < str.size(); i++){
            v[i + 1] = v[i] + (str[i] - '0'); //計算前綴和
        }
        cin >> q;
        while(q--){
            cin >> a >> b;
            if(v[a] == v[b + 1] || v[a] + b - a + 1 == v[b + 1]) cout << "Yes" << endl; //判斷區間總和
            else cout << "No" << endl;
        }
    }
    return 0;
}

暴力法

有些題目看似需要去想一些演算法來處理，實際上數字範圍不大，可以直接用暴力的方式去解。

Sumsets

UVA 10125

題目大意

給定一串數字，在這些數字中取出四個不重複數字，使得 a + b + c = d，求出最大可能的 d。

解題方法
  • 將數字排序之後，由大到小將數字做為 d 並檢查，如果滿足條件則退出。
  • 更好的作法可以解 a + b = d - c。
注意事項
  • 注意數字不能重複，而且 d 可能是負值。
程式碼 
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
#include <bits/stdc++.h>

using namespace std;

int n;

int main(){
    while(cin >> n && n != 0){
        if(n < 4){
            cout << "no solution" << endl;
            continue;
        }
        vector<int> v(n);
        for(int i = 0; i < n; i++){
            cin >> v[i];
        }
        sort(v.begin(), v.end());
        int ans = INT_MIN;
        for(int d = n - 1; d >= 0; d--){ //d 由大到小
            for(int c = 0; c < n; c++){
                if(c == d) continue; //避免重複
                for(int b = c + 1; b < n; b++){
                    if(b == d) continue;
                    for(int a = b + 1; a < n; a++){
                        if(a == d) continue;
                        if(v[a] + v[b] + v[c] == v[d]){
                            ans = v[d];
                            break;
                        }
                    }
                    if(ans != INT_MIN) break;
                }
                if(ans != INT_MIN) break;
            }
            if(ans != INT_MIN) break;
        }
        if(ans != INT_MIN) cout << ans << endl;
        else cout << "no solution" << endl;
    }
    return 0;
}

The Hotel with Infinite Rooms

UVA 10170

題目大意

有一間有無限房間的飯店，並且有好幾團旅客依照特定的規則入住：每一團都比前一團多住一天，並且每次只會有一團旅客入住，現在給定第一團旅客所住的天數，求第 n 天是第幾團旅客正在住。

解題方法

不斷累加旅客所住的時間，直到超過所求天數 n 為止。

程式碼 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>

using namespace std;

long long s, d;

int main(){
    while(cin >> s >> d){
        long long c = 0;
        for(int i = s;;i++){
            c += i;
            if(c >= d){
                cout << i << endl;
                break;
            }
        }
    }
    return 0;
}

Quirksome Squares

UVA 256

題目大意

有一種特殊的數字 x 有 2n 位數，可以分成兩個 n 位數 a、b，並且滿足 a2+b2=xa^2 + b^2 = x ，ex: 302+252=302530^2 + 25^2 = 3025，每次會輸入一個數字 2n，求出所有 2n 位數的特殊數字。

解題方法

接收輸入前先把 2, 4, 6, 8 位數的表先建立好，其實就是遍歷範圍內的數字做檢查。

注意事項
  • 注意題目要求位數不夠的話要補 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
25
26
27
#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> v(4, vector<int>());
int n, d[4] = {10, 100, 1000, 10000};

int main(){
    for(int k = 0; k < 4; k++){ //建表
        for(int i = 0; i < d[k]; i++){
            for(int j = 0; j < d[k]; j++){
                if((i + j) * (i + j) == (i * d[k] + j)){
                    v[k].push_back((i + j) * (i + j));
                }
            }
        }
    }
    while(cin >> n){
        for(int i = 0; i < v[n / 2 - 1].size(); i++){
            if(n == 2) printf("%02d\n", v[0][i]); //補 0
            else if(n == 4) printf("%04d\n", v[1][i]);
            else if(n == 6) printf("%06d\n", v[2][i]);
            else printf("%08d\n", v[3][i]);
        }
    }
    return 0;
}