# 演算法課程題解 - 字串
# TOJ 5
## 題目
https://toj.tfcis.org/oj/pro/5/
## 重點
使用getline(cin,s)以讀取含空白字串
## 解法 By Koios1143
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
string s;
int main(){
while(getline(cin,s)){
cout<<"Hello ,"<<s<<" !\n";
}
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(1)$
# TOJ 92
## 題目
https://toj.tfcis.org/oj/pro/92/
## 重點
上課要聽
## 解法 By Koios1143
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main() {
string s1,s2,s3;
cin>>s1>>s2>>s3;
cout<<"Hello, "<<s1<<", "<<s2<<", and "<<s3<<"!\n";
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(1)$
# TOJ 103
## 題目
https://toj.tfcis.org/oj/pro/103/
輸入兩個字串分別表示茶的種類以及甜度
如果種類和甜度都相同就輸出 GOOD
如果只有一種相同就輸出 =~=
如果兩個都不同就輸出 OTZ
## 解法 By Koios1143
### 想法
先分別記錄名稱和甜度是否相同，再利用條件判斷輸出即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main() {
string s1,s2;
int n1,n2;
cin>>s1>>n1>>s2>>n2;
bool name = (s1==s2);
bool sweet = (n1==n2);
if(name && sweet){
cout<<"GOOD\n";
}
else if(name || sweet){
cout<<"=~=\n";
}
else{
cout<<"OTZ\n";
}
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(1)$
# UVa 272
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?272
給一篇文章，將每個 "" 對分別改寫成 `` 以及 ''
## 解法 By Koios1143
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main(){
string s;
bool first=true;
while(getline(cin,s)){
for(int i=0 ; i<s.size() ; i++){
if(s[i]=='\"'){
if(first)
cout<<"``";
else
cout<<"''";
first=!first;
}
else
cout<<s[i];
}
cout<<"\n";
}
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(\Sigma len(s))$
# TOJ 100
## 題目
https://toj.tfcis.org/oj/pro/100/
## 重點
[字元的加減運算](https://emanlaicepsa.github.io/2020/10/29/0-5/)
## 解法 By Koios1143
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main() {
char n;
cin>>n;
cout<<(char)(n-1)<<'\n';
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(1)$
# TOJ 101
## 題目
https://toj.tfcis.org/oj/pro/101/
## 重點
[字元的加減運算](https://emanlaicepsa.github.io/2020/10/29/0-5/)
## 解法 By Koios1143
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main() {
int n;
cin>>n;
cout<<(char)('A'+n-1)<<'\n';
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(1)$
# TOJ 127
## 題目
https://toj.tfcis.org/oj/pro/127/
凱薩加密
給一個數字 $n$ 以及一個字串 $S$ ，求將字串 $S$ 中的所有字元 $c$ 逆回 $n$ 之後的字串
## 解法 By Koios1143
### 想法
首先考慮到如果 $n$ 大於 26 的情況，其實跟 $n\%26$ 是相同的，所以先處理 $n$
接下來針對每個字元處理位移量
如果超出範圍，可以保證只需要再加上一個 26 就可以得到答案
否則直接扣掉 $n$ 即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main(){
int n;
string s;
cin>>n>>s;
n%=26;
for(int i=0 ; i<s.size() ; i++){
if(s[i]-n < 'A')
s[i]=s[i]-n+26;
else
s[i]=s[i]-n;
}
cout<<s<<"\n";
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(len(s))$
# UVa 458
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?458
有一種特定加密方式
若 K = 2 則 apple 經過加密後會變成 crrng
給你一個字串 請從 Sample Output 及 Sample Input 反推 K
## 解法 By MuMu
### 想法
觀察一下他的加密方式 其實可以滿明顯的觀察出
原文 經過此加密且值為 K 時 密文就會是 原文的 ascii + 7
因此可以從 Input 跟 Output 推出 K
直接 `Input[0] - Output[0]` 就可以推出 K
可得出 K = 7
代表 Output 會等於 Input - 7
[bits/stdc++.h library 介紹](https://www.itread01.com/content/1547093362.html)
### 程式碼
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
string s;
while(cin >> s){
for(int i = 0 ; i < s.size() ; i++){
cout << char(s[i] - 7);
}
cout << endl;
}
}
```
# TOJ 96
## 題目
https://toj.tfcis.org/oj/pro/96/
給一個只有兩個運算元以及一個運算子的式子，求該式子的答案
其中，運算元包含 $+, -, *, /$
## 解法 By Koios1143
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main() {
int a,b;
char c;
cin>>a>>c>>b;
if(c=='+'){
cout<<a<<" + "<<b<<" = "<<a+b<<'\n';
}
else if(c=='-'){
cout<<a<<" - "<<b<<" = "<<a-b<<'\n';
}
else if(c=='*'){
cout<<a<<" * "<<b<<" = "<<a*b<<'\n';
}
else if(c=='/'){
if(b==0)
cout<<"ERROR\n";
else
cout<<a<<" / "<<b<<" = "<<a/b<<" ... "<<a%b<<'\n';
}
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(1)$
# TOJ 113
## 題目
https://toj.tfcis.org/oj/pro/113/
## 解法 By Koios1143
### 想法
先找出 $P$ 在字串中的位置，再依據移動方向調整即可
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main(){
int n;
string s;
char c;
cin>>n>>s>>c;
int pos=0;
for(int i=0 ; i<n ; i++){
if(s[i]=='P'){
pos=i;
break;
}
}
if(c=='L'){
swap(s[pos],s[pos-1]);
}
else{
swap(s[pos],s[pos+1]);
}
cout<<s<<'\n';
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(n)$
# TOJ 244
## 題目
https://toj.tfcis.org/oj/pro/244/
將輸入的字串中小寫轉大寫，大寫轉小寫
## 解法 By Koios1143
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main(){
int n;
string s;
cin>>n>>s;
for(int i=0 ; i<s.size() ; i++){
if(s[i]<='Z'){
cout<<(char)(s[i]-'A'+'a');
}
else
cout<<(char)(s[i]-'a'+'A');
}
cout<<"\n";
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(n)$
# TOJ 18
## 題目
https://toj.tfcis.org/oj/pro/18/
輸入一個字串 $S$
定義一個字串是強效字串，唯有在 $S$ 只留下英文字母時，從頭看到尾與從尾看到頭，不分大小寫是相同的
如果是強效字串，在字串前加上 `SETUP! `
## 解法 By Koios1143
### 想法
先利用一個 tmp 字串記錄字串 $S$ 去除英文字母以外的字元，且將字母都轉為小寫的樣子
接下來只需要檢查 tmp 是不是回文即可
判斷方式可以從同到字串的頭到字串的一半，檢查頭尾是否相同
也就是 $tmp[i] = tmp[tmp.size()-1-i]$ 是否成立
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
int main(){
string s;
while(getline(cin,s)){
string tmp="";
for(int i=0 ; i<s.size() ; i++){
if((s[i]>='A' && s[i]<='Z') || (s[i]>='a' && s[i]<='z'))
tmp+=tolower(s[i]);
}
bool powerful=true;
for(int i=0, j=tmp.size()-1 ; i<tmp.size()/2 ; i++, j--){
if(tmp[i]!=tmp[j]){
powerful=false;
break;
}
}
if(powerful)
cout<<"SETUP! "<<s<<"\n";
else
cout<<s<<"\n";
}
return 0;
}
```
### 複雜度分析
總複雜度約為 $O(2len(s))$
# TOJ 115
## 題目
https://toj.tfcis.org/oj/pro/115/
## 解法 By Koios1143
### 程式碼
```cpp=
//By Koios1143
#include<iostream>
using namespace std;
string arr[11];
int main(){
for(int i=0 ; i<11 ; i++){
arr[i] = "EMPTY";
}
int n,m;
string s;
cin>>n;
while(n--){
cin>>s>>m;
arr[m]=s;
}
for(int i=1 ; i<=10 ; i++){
cout<<arr[i]<<"\n";
}
return 0;
}
```
### 複雜度分析
總時間複雜度為 $O(nm)$ ，其中 $m$ 表示可以覆蓋的總牌數
# UVa 10082
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?10082
人在打字常常打錯，現在給你一項任務，將所有輸入的字元都變成在鍵盤中左邊一位的字元
當然，題目保證不會輸入像是 **Q** **A** **Z** **\`** 的邊界字元，請放心
## 解法 By Koios1143
### 想法
直接將鍵盤上的字刷過一遍，沒錯，刷過去
建立一個字串 $tbl$ ，包含鍵盤上的所有字母，並且是由上到下、由左到右的順序
接下來每次我們輸入的時候，只需要到 $tbl$ 找到當前的字母，然後輸出他的前一個就可以了
### 程式碼
```cpp=
#include<iostream>
using namespace std;
string tbl="`1234567890-=QWERTYUIOP[]ASDFGHJKL;'ZXCVBNM,./'";
string s;
int main(){
while(getline(cin,s)){
for(int i=0 ; i<s.size() ; i++){
if(s[i]==' ')
cout<<" ";
else{
for(int j=0 ; j<tbl.size() ; j++){
if(s[i]==tbl[j]){
cout<<tbl[j-1];
break;
}
}
}
}
cout<<"\n";
}
return 0;
}
```
### 時間複雜度分析
假設 $tbl$ 的字串長度為 $N$
每次查詢時間複雜度最差為 $O(N)$
每筆測資時間複雜度為 $O(len(s)N)$
## 解法 By MuMu
### 想法
請不要學樓上這樣
乖乖建表
### 程式碼
```cpp=
#include<iostream>
#include<map>
using namespace std ;
int main(){
map <char , char> arr;
string s;
arr['1']='`',arr['2']='1',arr['3']='2',arr['4']='3';
arr['5']='4',arr['6']='5',arr['7']='6',arr['8']='7';
arr['9']='8',arr['0']='9',arr['-']='0',arr['=']='-';
arr['W']='Q',arr['E']='W',arr['R']='E',arr['T']='R';
arr['Y']='T',arr['U']='Y',arr['I']='U',arr['O']='I';
arr['P']='O',arr['[']='P',arr[']']='[',arr['\\']=']';
arr['S']='A',arr['D']='S',arr['F']='D',arr['G']='F';
arr['H']='G',arr['J']='H',arr['K']='J',arr['L']='K';
arr[';']='L',arr['\'']=';',arr['X']='Z',arr['C']='X';
arr['V']='C',arr['B']='V',arr['N']='B',arr['M']='N';
arr[',']='M',arr['.']=',',arr['/']='.',arr[' ']=' ';
while(getline(cin , s)){
for(int i = 0 ; i < s.size() ; i++){
cout << arr[s[i]];
}
cout << "\n";
}
}
```
### 時間複雜度分析
map 實作為紅黑樹
本身查詢複雜度為 $O(logN)$
字串長度為 $S$
整體複雜度 $O(SlogN)$
## 解法 By sa072686
### 想法
請不要學樓上這樣，既不優雅還開了棵又蠢又笨重的紅黑樹
乖乖建表
### 程式碼
```cpp=
#include<iostream>
using namespace std;
string key="`1234567890-=QWERTYUIOP[]\\ASDFGHJKL;'ZXCVBNM,./";
char tbl[128];
int main()
{
int i;
string s;
for (i=1; i<key.size(); i++)
{
tbl[key[i]] = key[i-1];
}
tbl[' '] = ' ';
while (getline(cin, s))
{
for (i=0; i<s.size(); i++)
{
s[i] = tbl[s[i]];
}
cout << s << "\n";
}
}
```
### 時間複雜度分析
計算量為預處理的 $O(1)$ 加上每次詢問時每個字元 $O(1)$ 查表
複雜度為優雅的 $O(N)$
# UVa 11192
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11192
給一個字串 $S$ 以及一個整數 $N$ ，保證 $len(S)$ 是 $N$ 的整數倍
現在要將字串分成 $N$ 組，並且將每組的字串反過來輸出
## 解法 By Koios1143
### 想法
假設 $M=len(S)/n$
從 $M-1$ 開始，每次把前面 $M$ 個字輸出
再往 $M-1$ 向後移動 $M$，把前面 $M$ 個字輸出
持續這個步驟直到結束
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int n;
string s;
int main(){
while(cin>>n && n){
cin>>s;
n=s.size()/n;
for(int i=n-1 ; i<s.size() ; i+=n){
for(int j=i,cnt=0 ; cnt<n ; j--,cnt++){
cout<<s[j];
}
}
cout<<'\n';
}
return 0;
}
```
### 時間複雜度分析
每筆測資會將字串的每個字都跑過一遍，時間複雜度為 $O(len(S))$
## 另解
使用s.substr()函式以及reverse函式
```cpp=
#include<bits/stdc++.h>
using namespace std;
int group, siz;
string s;
signed main(){
while(cin>>group){
if(group==0) break;
cin>>s;
siz = s.size() / group;
for(int i=0;i<(int)s.size();i+=siz){
string tmp = s.substr(i,siz);
reverse(tmp.begin(),tmp.end());
cout<<tmp;
}
cout<<'\n';
}
}
```
# UVa 11541
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11541
給一個字串，內容都會是一個字元 $C$ 接著一串數字 $N$ ，表示要輸出 $N$ 個 $C$
例如: `A2B3C1` 表示 `AABBBC`
## 解法 By Koios1143
### 想法
分別用一個變數 $tmp$ 和 $cnt$ 紀錄當前要輸出的字元以及要輸出的次數
每次遇到數字，就把 $cnt*10$ ， 再將 $cnt$ 加上當前數字
這樣才可以進位，也因為如此， $cnt$ 的初始值要設定為 0
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int Case=1,t,cnt=0;
string s;
char tmp;
int main(){
cin>>t;
while(t--){
cout<<"Case "<<Case++<<": ";
cin>>s;
cnt=0;
for(int i=0 ; i<=s.size() ; i++){
if(i!=s.size() && s[i]>='0' && s[i]<='9'){
cnt*=10;
cnt+=s[i]-'0';
}
else{
if(cnt==0){
tmp=s[i];
}
else{
for(int j=0 ; j<cnt ; j++){
cout<<tmp;
}
cnt=0;
tmp=s[i];
}
}
}
cout<<"\n";
}
return 0;
}
```
### 時間複雜度分析
假設每次輸出的字元數量是 $N$，需要輸出的字元有 $M$ 個
那麼每筆測資的時間複雜度為 $O(NM)$
總時間複雜度為 $O(tNM)$
# UVa 11577
## 題目
http://domen111.github.io/UVa-Easy-Viewer/?11577
給一個字串，求字串中的所有英文字母轉成小寫後，出現次數最多的有哪些
## 解法 By Koios1143
### 想法
用一個陣列 $cnt$ 儲存每個字母出現的次數，將 $cnt$ 中最大的值對應到的字母輸出
### 程式碼
```cpp=
#include<iostream>
using namespace std;
int cnt[26];
int n,px;
string s;
int main(){
cin>>n;
getchar();
while(n--){
int ans=0;
for(int i=0 ; i<26 ; i++){
cnt[i]=0;
}
getline(cin,s);
for(int i=0 ; i<s.size() ; i++){
if((s[i]>='A' && s[i]<='Z') || (s[i]>='a' && s[i]<='z')){
px=tolower(s[i])-'a';
cnt[px]++;
ans=max(ans, cnt[px]);
}
}
for(int i=0 ; i<26 ; i++){
if(cnt[i]==ans){
cout<<(char)('a'+i);
}
}
cout<<'\n';
}
return 0;
}
```
### 時間複雜度分析
每筆測資會將整個字串看過一遍，時間複雜度為 $O(len(s))$
輸出的時間複雜度很小，可以直接視為 $O(1)$
每筆測資時間複雜度約為 $O(len(s))$
# ZJ a020
## 題目
https://zerojudge.tw/ShowProblem?problemid=a020
給一個身分證字號，求是否符合身份證字號的規則，其規則如下:
1. 先依照表格，將英文字母對應到數字
```
A=10 台北市 J=18 新竹縣 S=26 高雄縣
B=11 台中市 K=19 苗栗縣 T=27 屏東縣
C=12 基隆市 L=20 台中縣 U=28 花蓮縣
D=13 台南市 M=21 南投縣 V=29 台東縣
E=14 高雄市 N=22 彰化縣 W=32 金門縣
F=15 台北縣 O=35 新竹市 X=30 澎湖縣
G=16 宜蘭縣 P=23 雲林縣 Y=31 陽明山
H=17 桃園縣 Q=24 嘉義縣 Z=33 連江縣
I=34 嘉義市 R=25 台南縣
```
2. 將第 1 步得到的數字的**十位數**以及**個位數乘上 9** 的值記錄下來為 $n$
3. 數字從最左邊到最右邊依序乘上 8, 7, 6, ... ,2, 1 ，並相加記錄下來為 $m$
4. 若 $n+m$ 是 10 的倍數，表示正確，否則錯誤
若是正確的身分證輸出 `real` ， 否則輸出 `fake`
## 解法 By Koios1143
### 想法
建立一個對照的表格(這裡以 function 實現)，讓英文字能對應到相對的數字
接著做第 2 步驟，再判斷即可
建表稍微麻煩，但是只要用心就可以完成了
### 程式碼
```cpp=
#include<iostream>
using namespace std;
string s;
int cnt=0,tmp;
int get_num(char c){
if(c>='A'&&c<='H')
return 10+(c-'A');
else if(c=='I')
return 34;
else if(c>='J' && c<='N')
return 18+(c-'J');
else if(c=='O')
return 35;
else if(c>='P' && c<='V')
return 23+(c-'P');
else if(c=='W')
return 32;
else if(c=='X')
return 30;
else if(c=='Y')
return 31;
else if(c=='Z')
return 33;
}
int main(){
cin>>s;
tmp=get_num(s[0]);
cnt+=(tmp/10)+(tmp%10)*9;
for(int i=1, T=8 ; i<s.size() ; i++,T--){
if(T==0)
cnt+=s[i]-'0';
cnt+=(s[i]-'0')*T;
}
if(cnt%10==0)
cout<<"real\n";
else
cout<<"fake\n";
return 0;
}
```
### 時間複雜度分析
由於字串的長度很小，並且每次計算的量值也很小，直接以 $O(1)$ 記之
## 解法 by sa072686
請不要學樓上，乖乖建表
### 程式碼
```cpp=
#include <iostream>
using namespace std;
// 0123456789012345678901234567890123456789
string id = "__________ABCDEFGHJKLMNPQRSTUVXYWZIO";
int tbl[128];
int main()
{
int i, j, ans;
string s;
for (i=0; i<id.size(); i++)
{
tbl[ id[i] ] = i;
}
while (cin >> s)
{
ans = tbl[s[0]]/10 + (tbl[s[0]]%10 * 9);
for (i=1, j=8; j>0; i++, j--)
{
ans += (s[i]-'0') * j;
}
ans += s[i] - '0';
cout << (ans%10?"fake":"real") << "\n";
}
return 0;
}
```
### 時間複雜度分析
由於字串的長度很小，並且每次計算的量值也很小，直接以 $O(1)$ 記之
###### tags: `SCIST 演算法 題解`
Sign in with Wallet
Connect another wallet