# C++ 基礎語法練習題：Unit-8 C++字串(string)、常用字串函數
講義不是我寫的，原文連結為 [Yui Huang 演算法學習筆記：C++ 基礎語法](https://yuihuang.com/syntax/)
我只是將自己寫的練習題程式碼記錄下來。
最後更新日期：2024年11月12日
## [ZeroJudge: a130. 12015 - Google is Feeling Lucky](https://zerojudge.tw/ShowProblem?problemid=a130)
### Python 程式碼
執行時間最久約為 27 ms，使用記憶體最多約為 3.6 MB，通過測試。
```python=
from collections import defaultdict
T = int(input())
for i in range(1, T+1):
print(f"Case #{i:d}:")
data = defaultdict(list) # 以相關度為 key，val 為一維串列，內容為網址
imax = 0 # 目前最高的相關度
for _ in range(10):
url, rank = input().split()
rank = int(rank)
if rank > imax: imax = rank
data[rank].append(url)
for d in data[imax]: print(d)
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 340 kB，通過測試。
```cpp=
#include <iostream>
#include <unordered_map>
#include <vector>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T;
for(int i=1; i<=T; i++) {
cout << "Case #" << i << ":\n";
unordered_map<int, vector<string>> data; // 以相關度為 key，val 為一維串列，內容為網址
int imax = 0; // 目前最高的相關度
for(int j=0; j<10; j++) {
string url; int rank; cin >> url >> rank;
if (rank > imax) imax = rank;
data[rank].push_back(url);
}
for(auto d : data[imax]) cout << d << "\n";
}
return 0;
}
```
## [ZeroJudge: b428. 凱薩加密](https://zerojudge.tw/ShowProblem?problemid=b428)
### Python 程式碼
執行時間最久約為 19 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
import sys
for line in sys.stdin:
plaintext = line
ciphertext = input()
print((ord(ciphertext[0]) - ord(plaintext[0]) + 26) % 26)
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 332 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
string plaintext, ciphertext;
while(cin >> plaintext >> ciphertext)
cout << (ciphertext[0] - plaintext[0] + 26) % 26 << "\n";
return 0;
}
```
## [ZeroJudge: a065. 提款卡密碼](https://zerojudge.tw/ShowProblem?problemid=a065)
### Python 程式碼
執行時間最久約為 19 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
s = input()
n = len(s)
pw = ""
for i in range(n-1):
pw += str(abs(ord(s[i+1]) - ord(s[i])))
print(pw)
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 356 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
string s, pw = "";
cin >> s;
int n = (int)s.size();
for(int i=0; i<n-1; i++) pw += to_string(abs(s[i+1] - s[i]));
cout << pw << "\n";
return 0;
}
```
## [ZeroJudge: d235. 10929 - You can say 11](https://zerojudge.tw/ShowProblem?problemid=d235)
### Python 程式碼
執行時間最久約為 41 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
while True:
s = input()
if s == "0": break
odd, even = 0, 0
n = len(s)
for i in range(0, n, 2): odd += int(s[i])
for i in range(1, n, 2): even += int(s[i])
if abs(odd - even) % 11 == 0:
print(f"{s:s} is a multiple of 11.")
else:
print(f"{s:s} is not a multiple of 11.")
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 336 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
while(true) {
string s; cin >> s;
if (s == "0") break;
int odd = 0, even = 0, n = (int)s.size();
for(int i=0; i<n; i+=2) odd += s[i] - '0';
for(int i=1; i<n; i+=2) even += s[i] - '0';
if (abs(odd - even) % 11 == 0)
cout << s << " is a multiple of 11.\n";
else
cout << s << " is not a multiple of 11.\n";
}
return 0;
}
```
## [ZeroJudge: d275. 11586 - Train Tracks](https://zerojudge.tw/ShowProblem?problemid=d275)
### Python 程式碼
執行時間最久約為 18 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
n = int(input())
for _ in range(n):
data = list(input().split())
data.append(data[0])
m = len(data)
flag = True
if m <= 2: flag = False #.原來的軌道數為 1，不能成環
for i in range(m-1):
if (data[i][1] == 'M' and data[i+1][0] == 'M') or \
(data[i][1] == 'F' and data[i+1][0] == 'F'):
flag = False
break
print("LOOP" if flag else "NO LOOP")
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 336 kB，通過測試。
```cpp=
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
cin.ignore();
for(int i=0; i<n; i++) {
vector<string> data;
string s; getline(cin, s);
stringstream ss; ss << s;
while(ss >> s) data.push_back(s);
data.push_back(data[0]);
int m = (int)data.size();
bool flag = true;
if (m <= 2) flag = false;
for(int j=0; j<m-1; j++) {
if ((data[j][1] == 'M' && data[j+1][0] == 'M') || (data[j][1] == 'F' && data[j+1][0] == 'F')) {
flag = false;
break;
}
}
cout << (flag ? "LOOP\n" : "NO LOOP\n");
}
return 0;
}
```
## [ZeroJudge: c459. 2. 自戀數](https://zerojudge.tw/ShowProblem?problemid=c459)
### Python 程式碼
執行時間最久約為 18 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
import sys
for line in sys.stdin:
b, n = line.split() # 底數 b，要測試的整數 n，格式為字串
b = int(b) # b 轉為 int
m = len(n) # n 的位數 m
tot = 0 # 加總
for c in n: # 依序由 n 讀取字元 c，轉成 int 計算 c**m 再加到 tot
tot += int(c)**m
print("YES" if tot == int(n, b) else "NO") # 將 n 以 b 為底轉成 int 比較是否等於 tot
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 360 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int conv(string s, int base) {
int ans = 0, b = 1;
int n = (int)s.size();
for(int i=0; i<n; i++) {
char c = s[n-1-i];
ans += (c - '0')*b;
b *= base;
}
return ans;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int b; string n; // 底數 b，要測試的整數 n
while(cin >> b >> n) {
int m = (int)n.size(); // n 的位數 m
int tot = 0; // 加總
for(char c : n) // 依序由 n 讀取字元 c，轉成 int 計算 c**m 再加到 tot
tot += (int)pow((c - '0'), m);
cout << (tot == conv(n, b) ? "YES\n" : "NO\n"); // 將 n 以 b 為底轉成 int 比較是否等於 tot
}
return 0;
}
```
## [ZeroJudge: d267. 11577 - Letter Frequency](https://zerojudge.tw/ShowProblem?problemid=d267)
### Python 程式碼
執行時間最久約為 26 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
n = int(input())
for _ in range(n):
cnt = [0]*26
s = input()
for c in s:
if 'A' <= c <= 'Z':
cnt[ord(c) - ord('A')] += 1
elif 'a' <= c <= 'z':
cnt[ord(c) - ord('a')] += 1
imax = max(cnt)
for i in range(26):
if cnt[i] == imax:
print(chr(i + ord('a')), end="")
print()
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 324 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int n; cin >> n; cin.ignore(); // 要用 cin.ignore() 跳過這行的 \n
for(int i=0; i<n; i++) {
int cnt[26] = {0};
string s; getline(cin, s);
for(char c : s) {
if (c >= 'A' && c <= 'Z')
cnt[c-'A']++;
else if (c >= 'a' && c <= 'z')
cnt[c-'a']++;
}
int imax = 0;
for(int i=0; i<26; i++)
if (cnt[i] > imax) imax = cnt[i];
for(int i=0; i<26; i++)
if (cnt[i] == imax)
cout << char(i + 'a');
cout << "\n";
}
return 0;
}
```
## [ZeroJudge: d671. 11716 - Digital Fortress](https://zerojudge.tw/ShowProblem?problemid=d671)
### Python 程式碼
執行時間最久約為 17 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
T = int(input())
for _ in range(T):
s = input()
n = len(s)
m = int(n**0.5)
if m*m != n:
print("INVALID")
else:
for i in range(m):
for j in range(m):
print(s[i+j*m], end="")
print()
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 340 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int T; cin >> T; cin.ignore();
for(int t=0; t<T; t++) {
string s; getline(cin, s);
int n = (int)s.size();
int m = sqrt(n);
if (m*m != n) {
cout << "INVALID\n";
} else {
for(int i=0; i<m; i++) {
for(int j=0; j<m; j++) {
cout << s[i+j*m];
}
}
cout << "\n";
}
}
return 0;
}
```
## [ZeroJudge: c015. 10018 - Reverse and Add](https://zerojudge.tw/ShowProblem?problemid=c015)
### Python 程式碼
執行時間最久約為 29 ms，使用記憶體最多約為 3.3 MB，通過測試。
```python=
def palindrome(s):
n = len(s)
for i in range(n//2):
if s[i] != s[-(i+1)]:
return False
return True
N = int(input())
for _ in range(N):
P = input()
cnt = 1 # 至少要先運算1次
N = int(P) + int(P[::-1])
P = str(N)
while not palindrome(P):
cnt += 1
N = int(P) + int(P[::-1])
P = str(N)
print(f"{cnt:d} {P:s}")
```
### C++ 程式碼
執行時間最久約為 2 ms，使用記憶體最多約為 352 kB，通過測試。
```cpp=
#include <iostream>
#include <string>
using namespace std;
bool palindrome(string s) {
int n = (int)s.size();
for(int i=0; i<n/2; i++)
if (s[i] != s[n-1-i])
return false;
return true;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int N; cin >> N;
for(int i=0; i<N; i++) {
string P, R; cin >> P;
int cnt = 0;
do { // 至少要先運算1次
cnt++;
R = string(P.rbegin(), P.rend());
int N = stoi(P) + stoi(R);
P = to_string(N);
} while(!palindrome(P));
cout << cnt << " " << P << "\n";
}
return 0;
}
```
---
###### tags:`演算法`、`APCS`、`Python`、`C++`
Sign in with Wallet
Connect another wallet