大概刷了 50 題左右 GPE Helper 上面比較常出現的題目，根據題目類型分類做一些筆記，方便之後複習。
質數表
| Problem |
UVA |
| 24461 Sum of Consecutive Prime Numbers |
1210 |
| 23571 Smith Numbers |
10042 |
約瑟夫問題
| Problem |
UVA |
| 21944 Power Crisis |
151 |
| 10607 Joseph’s Cousin |
10015 |
座標系
| Problem |
UVA |
| 2009-24 Unique lines |
|
| 10551 Bee Maja |
10182 |
運算式
| Problem |
UVA |
| 2008-37 Prefix expression evaluation |
|
| 23671 Camel trading |
10700 |
質數表
Sum of Consecutive Prime Numbers
UVA 1210
題目大意
根據題目輸入的數字，計算其能夠寫成幾種連續質數的和，ex: 53 = 5 + 7 + 11 + 13 + 17 同時 53 也是一個質數，故需要輸出 2。
解題方法
先建立一個儲存質數的 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
| #include <bits/stdc++.h>
using namespace std;
vector<int> prime_table(10001, 1), prime;
int n;
int main(){
for(int i = 2; i <= 10000; i++){
if(prime_table[i] == 1){
for(int j = i + i; j <= 10000; j += i) prime_table[j] = 0;
prime.push_back(i);
}
}
while(cin >> n && n != 0){
int c = 0;
for(int i = 0; prime[i] <= n && i < prime.size(); i++){
int s = 0;
for(int j = i; s < n && j < prime.size(); j++){
s += prime[j];
}
if(s == n) c++;
}
cout << c << endl;
}
return 0;
}
|
Smith Numbers
UVA 10042
題目大意
Smith Numbers 的定義為原數字的各位數字和與其質因數分解的每個數字的各位數字和相同，ex: 4937775 = 3 · 5 · 5 · 65837 且兩邊的各位數字和相同。輸入一個數字，求出大於該數字的最小 Smith Numbers。
解題方法
建立一個質數表，方便之後的質因數分解，從題目給出的數字開始增加，並且判斷是否為 Smith Numbers，每次質因數分解結束時可能會有三種情況需要分開討論：
- 剩下
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
55
56
57
58
59
60
61
62
63
| #include <bits/stdc++.h>
using namespace std;
vector<int> prime;
vector<bool> p(100000, true);
void primeTable(){
for(int i = 2; i < 100000; i++){
if(p[i]){
prime.push_back(i);
for(int j = i + i; j < 100000; j += i){
p[j] = false;
}
}
}
return;
}
int s(int x){
int c = 0;
while(x != 0){
c += (x % 10);
x /= 10;
}
return c;
}
bool check(int x){
if(x < 100000 && p[x]) return false;
int c1 = s(x), c2 = 0, tmp = x;
for(int i = 0; i < prime.size(); i++){
if(x == 1) break;
if(x % prime[i] == 0){
int t = s(prime[i]);
while(x % prime[i] == 0){
c2 += t;
x /= prime[i];
}
}
}
if(x == tmp) return false;
if(x != 1) c2 += s(x);
if(c1 == c2) return true;
return false;
}
int n, m;
int main(){
primeTable();
cin >> n;
while(n--){
cin >> m;
for(int i = m + 1; i <= INT_MAX; i++){
if(check(i)){
cout << i << endl;
break;
}
}
}
return 0;
}
|
約瑟夫問題
Power Crisis
UVA 151
題目大意
基本上就是 約瑟夫問題，每次輸入一個大於 13 的人數 n，求出數字 m 做為每次跳過的人數，使得第 13 個人可以最後存活。
解題方法
遍歷 1 ~ n 的數字，使用約瑟夫問題的公式，計算最後存活的人並判斷是否正確。
注意事項
程式碼
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
| #include <bits/stdc++.h>
using namespace std;
int n;
bool check(int n, int x){
int k = 0;
for(int i = 1; i < n; i++){
k = (k + x) % i;
}
return (k == 11);
}
int main(){
while(cin >> n && n != 0){
for(int i = 1; i <= n; i++){
if(check(n, i)){
cout << i << endl;
break;
}
}
}
return 0;
}
|
Joseph’s Cousin
UVA 10015
題目大意
約瑟夫問題 的變體，每次輸入人數 n，並且第 i 次跳過的人數為第 i 個質數，ex:第一次跳 2 人，第二次跳 3 人，第三次跳 5 人…，求出最後剩下的人。
解題方法
把質數表建好，套上約瑟夫問題的公式，不過每次跳過的人數是質數表上對應的數字。
注意事項
程式碼
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
| #include <bits/stdc++.h>
using namespace std;
vector<bool> v(100000, true);
vector<int> p;
void prime(){
for(int i = 2; i < 50000; i++){
if(v[i]){
p.push_back(i);
if(p.size() == 3501) break;
for(int k = i + i; k <= 50000; k += i){
v[k] = false;
}
}
}
}
int f(int n){
int k = 0;
for(int i = 1; i <= n; i++){
k = (k + p[n - i]) % i;
}
return k + 1;
}
int n;
int main(){
prime();
while(cin >> n && n != 0){
cout << f(n) << endl;
}
return 0;
}
|
座標系
Unique lines
題目大意
給定若干個平面上的點，求這幾個點可以產生多少不同的線。
解題方法
首先遍歷所有點，並儲存每條邊的斜率，以及經過的其中一個點，分別儲存兩點間在 x 和 y 軸的變化量，之後遍歷所有儲存的邊，檢查是否有重複邊。
注意事項
- 如果是儲存斜率的話，可能會有正無限與負無限判斷的問題，分別儲存
x 和 y 軸的變化量可以避免這個問題。
程式碼
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, t;
vector<vector<int>> v;
int main(){
cin >> n;
while(n--){
v.clear();
int ans = 0;
cin >> t;
int arr[t][2];
for(int i = 0; i < t; i++){
cin >> arr[i][0] >> arr[i][1];
for(int j = 0; j < i; j++){
v.push_back({arr[i][0] - arr[j][0], arr[i][1] - arr[j][1], arr[i][0], arr[i][1]});
}
}
for(int i = 0; i < v.size(); i++){
int b = 1;
for(int j = i + 1; j < v.size(); j++){
if(v[i][0] * v[j][1] != v[i][1] * v[j][0]) continue;
if(v[i][0] * (v[i][3] - v[j][3]) == v[i][1] *(v[i][2] - v[j][2])){
b = 0;
break;
}
}
if(b == 1) ans++;
}
cout << ans << endl;
}
return 0;
}
|
Bee Maja
UVA 10182
題目大意
在一個六邊形的座標系中，有兩種表達格子的方式 (Maja’s & Willi’s)，每次輸入一個數字 (Willi’s)，需要轉換成 Maja’s 座標表達方式輸出。
解題方法
觀察六邊形的右下那條邊，可以發現兩種表達方式都有規律，Maja’s 座標分別為 {0, 1}, {0, 1}, {0, 2}...，Willi’s 座標分別為 1, 7, 19... 可以發現他們的差為 6 的整數倍，根據規律可以提前把轉換的表建立好。
程式碼
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
| #include <bits/stdc++.h>
using namespace std;
int n, dir[6][2] = {{0, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 0}, {1, -1}};
vector<pair<int, int>> v(200000);
int main(){
for(int i = 0; i <= 200; i++){
int p = 1 + i * (i + 1) * 3, x = i, y = 0;
v[p] = {x, y};
for(int j = 0; j < 5; j++){
for(int k = 0; k < i; k++){
p--;
x += dir[j][0];
y += dir[j][1];
v[p] = {x, y};
}
}
for(int k = 0; k < i - 1; k++){
p--;
x += dir[5][0];
y += dir[5][1];
v[p] = {x, y};
}
}
while(cin >> n){
cout << v[n].first << " " << v[n].second << endl;
}
return 0;
}
|
運算式
Prefix expression evaluation
題目大意
根據輸入的前序表達式計算其結果，如果該表達式不合法則輸出 illegal。
解題方法
將輸入的字串由後往前檢查，如果是數字則放入 stack 中，如果是符號則取出 stack 頂部的兩個數字做運算，運算完之後再放回 stack 中，最後剩下的數字就是計算的結果，如果在運算的過程有遇到 stack 為空的情況代表表達式有錯誤。
注意事項
- 遍歷字串的時候是由後往前的，因此處理數字的時候要注意。
程式碼
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;
string str;
int main(){
while(getline(cin, str) && str != "."){
stack<int> stk;
int n = 0, t = 1, b = 1;
for(int i = str.size() - 1; i >= 0; i--){
if(str[i] >= '0' && str[i] <= '9'){
n += t * (str[i] - '0');
t *= 10;
}else{
if(str[i] == ' '){
if(str[i + 1] >= '0' && str[i + 1] <= '9'){
stk.push(n);
t = 1;
n = 0;
}
continue;
}
if(stk.empty()){
b = 0;
break;
}
int n1 = stk.top();
stk.pop();
if(stk.empty()){
b = 0;
break;
}
int n2 = stk.top();
stk.pop();
int tmp;
if(str[i] == '+') tmp = n1 + n2;
else if(str[i] == '-') tmp = n1 - n2;
else if(str[i] == '*') tmp = n1 * n2;
else if(str[i] == '/') tmp = n1 / n2;
else if(str[i] == '%') tmp = n1 % n2;
stk.push(tmp);
}
}
if(b == 0) cout << "illegal" << endl;
else{
int ans = stk.top();
stk.pop();
if(!stk.empty()) cout << "illegal" << endl;
else cout << ans << endl;
}
}
return 0;
}
|
Camel trading
UVA 10700
題目大意
題目的輸入為一個式子，裡面只包含數字以及 *, + 兩個符號，可以隨意地在式子中加入括號，求出計算後所能得到的最大以及最小值。
解題方法
最大值一定是把所有有加號的數字先相加之後才相乘，最小值則是先處理相乘之後再相加，可以先將符號和數字分別儲存，後面再取出處理。
程式碼
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
| #include <bits/stdc++.h>
using namespace std;
long long maxn(vector<long long> num, vector<char> op){
for(int i = 0; i < op.size(); i++){
if(op[i] == '+'){
num[i + 1] += num[i];
num[i] = 1;
}
}
for(int i = 1; i < num.size(); i++){
num[i] *= num[i - 1];
}
return num[num.size() - 1];
}
long long minn(vector<long long> num, vector<char> op){
for(int i = 0; i < op.size(); i++){
if(op[i] == '*'){
num[i + 1] *= num[i];
num[i] = 0;
}
}
for(int i = 1; i < num.size(); i++){
num[i] += num[i - 1];
}
return num[num.size() - 1];
}
int n;
string str;
int main(){
cin >> n;
while(n--){
cin >> str;
vector<long long> num;
vector<char> op;
int tmp = 0;
for(int i = 0; i < str.size(); i++){
if(str[i] == '+' || str[i] == '*'){
op.push_back(str[i]);
num.push_back(tmp);
tmp = 0;
}else tmp = tmp * 10 + (str[i] - '0');
}
num.push_back(tmp);
cout << "The maximum and minimum are " << maxn(num, op) << " and " << minn(num, op) << "." << endl;
}
return 0;
}
|
