---
# System prepended metadata

title: 2022中和高中培訓練習總題解
tags: [中和高中]

---

# 2022中和高中培訓練習總題解


## funny-contest

### Special formula

照著公式抄

```cpp=
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    float n;
    cin >> n;
    float ans = n*(n/2+n*n)+n*n*n/(n+7)*(n+12)/n-2022;
    cout << fixed << setprecision(3) << ans;
}
```

### Grade calculation

使用if進行判斷

```cpp=
#include<iostream>
#include<iomanip>
using namespace std;
int main(){
    int n;
    cin >> n;
    if(n<60){
        cout << 'F';
    }else if(n>=60 && n<=70){
        cout << 'C';
    }else if(n>=71 && n<=89){
        cout << 'B';
    }else if(n>=90 && n<=100){
        cout << 'A';
    }else if(n>=100){
        cout << "A+";
    }
}
```
## 1019 review

### A. Sum

```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    for(int i=0;i<t;i++){
        int a[3];
        cin >> a[0] >> a[1] >> a[2];
        sort(a,a+3);
        if(a[0]+a[1]== a[2])cout << "YES" << '\n';
        else cout << "NO" << '\n';
    }
}
```

---

### B. Increasing

不可能嚴格遞增的條件是陣列中出現相同的數字，以此去判斷即可

```cpp=
#pragma GCC optimize("Ofast")
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cctype>
#include<deque>
#include<string>
#include<stack>
#include<string.h>
#include<random>
#include<chrono>
#define int long long int
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define T int _T;cin >> _T;while(_T--)
using namespace std;
using namespace __gnu_pbds;
const int SIZE = 1e6+7;
const int MOD = 1e9+7;
bool cmp(int a,int b){return a>b;}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
struct chash {
    const uint64_t C = (int)(2e18*acos((long double)-1))+71;
    const int RANDOM = rng();
    int operator()(int x) const {
    return __builtin_bswap64((x^RANDOM)*C); }
};
template<class K,class U> using ht = gp_hash_table<K,U,chash>;
 
void file(){
    #ifndef ONLINE_JUDGE
       freopen("D:\\programming\\CP\\1.in", "r", stdin);
       freopen("D:\\programming\\CP\\1.out", "w", stdout);
    #endif
}
void solve(){
	map<int,int> m;
	int n;
	cin >> n;
	bool flag = 1;
	for(int i=0;i<n;i++){
		int x;
		cin >> x;
		if(m[x]>0)flag = 0;
		m[x]++;
	}
	if(flag)cout << "YES" << '\n';
	else cout << "NO" << '\n';
}
 
signed main(){
    IOS
    //file();
    T
    solve();
}
```

---

### C. Stripes

你會發現，最後的放的彩帶一定是完整的，因此去檢查每個水平與垂直行是否有完整的彩帶即可。

```cpp=
#pragma GCC optimize("Ofast")
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cctype>
#include<deque>
#include<string>
#include<stack>
#include<string.h>
#include<random>
#include<chrono>
#define int long long int
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define T int _T;cin >> _T;while(_T--)
using namespace std;
using namespace __gnu_pbds;
const int SIZE = 1e6+7;
const int MOD = 1e9+7;
bool cmp(int a,int b){return a>b;}
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
struct chash {
    const uint64_t C = (int)(2e18*acos((long double)-1))+71;
    const int RANDOM = rng();
    int operator()(int x) const {
    return __builtin_bswap64((x^RANDOM)*C); }
};
template<class K,class U> using ht = gp_hash_table<K,U,chash>;
 
void file(){
    #ifndef ONLINE_JUDGE
       freopen("D:\\programming\\CP\\1.in", "r", stdin);
       freopen("D:\\programming\\CP\\1.out", "w", stdout);
    #endif
}
 
 
char a[10][10];
void solve(){
	for(int i=0;i<8;i++)for(int j=0;j<8;j++)cin >> a[i][j];

	for(int i=0;i<8;i++){
		bool ok = 1;
		for(int j=0;j<8;j++){
			
			if(a[i][j]!='R'){
				ok = 0;
				break;
			}
		}
		if(ok){
			cout << 'R' << '\n';
			return;
		}
	}
	for(int i=0;i<8;i++){
		bool ok = 1;
		for(int j=0;j<8;j++){
			
			if(a[j][i]!='B'){
				ok = 0;
				break;
			}
		}
		if(ok){
			cout << 'B' << '\n';
			return;
		}
	}
	
 
}
 
signed main(){
    IOS
    //file();
    T
    solve();
}
```


---

### D. YES or YES?
利用tolower函式將我的所有英文字母轉換為小寫，最後直接判斷即可。
```cpp=
#include<iostream>
#include<iomanip>
#include<cctype>
#include<math.h>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cctype>
#include<deque>
#include<string>
#include<stack>
#include<string.h>
#define int long long int
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define T int _T;cin >> _T;while(_T--)
using namespace std;
const int SIZE = 1<<20;
 
void solve(){
    string s;
    cin >> s;
    for(int i=0;i<s.size();i++)s[i]=tolower(s[i]);
    if(s=="yes")cout << "YES" << '\n';
    else cout << "NO" << '\n';
}
 
 
signed main(){
    IOS
    T
    solve();    
}
 
```

---
### E. Print a Pedestal

為了使$1st$的高是所有解中最小，我們可以將所有的木塊取平均，並且不管剩下幾塊，都需要將$3th$位置的木塊丟給$1st$的位置，使其保證$1st$一定是最高的。如果剩1塊，就直接丟給$1st$的位置。如果剩2塊，就分別丟給$1st$和$2th$的位置

```cpp=
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cctype>
#include<deque>
#include<string>
#include<stack>
#include<string.h>
#define int long long int
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define T int _T;cin >> _T;while(_T--)
using namespace std;
const int SIZE = 1<<20;
 
void solve(){
	int n;
	cin >> n;
	int a1=n/3;
	int a2=n/3;
	int a3=n/3;
	if(n%3==1){
		a2++;
	}else if(n%3==2){
		a1++,a2++;
	}
	a3--,a2++;
	cout << a1 << " " << a2 << " " << a3 << '\n';
}
 
 
signed main(){
    IOS
    T
    solve();
}
 
```

---


## implement



### 我是第一題實作題

模擬就好

```cpp=
#include<iostream>
#include<iomanip>
#include<math.h>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<bitset>
#include<cctype>
#include<deque>
#include<string>
#include<stack>
#include<string.h>
#define int long long int
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define T int _T;cin >> _T;while(_T--)
using namespace std;
const int SIZE = 1<<20;
 
char c[100][100];
int n,m;
 
void turn(int i,int j){
    int nowi=i;
    bool flag=0;
    while(nowi+1<n && c[nowi+1][j]!='o' && c[nowi+1][j]!='*'){flag=1;nowi++;}
    if(flag){
        c[nowi][j]='*';
        c[i][j]='.';
    }
}
 
void solve(){
    cin >> n >> m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            cin >> c[i][j];
    
    for(int i=n-1;i>=0;i--){
        for(int j=m-1;j>=0;j--){
            if(c[i][j]=='*'){
                turn(i,j);
            }
        }
    }
    
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout << c[i][j];
        }
        cout << '\n';
    }
    cout << '\n';
 
}
 
 
signed main(){
    IOS
    T
    solve();
}
```

### 我是第二題實作題

題目只會有一個主教，因此可以遍歷整個棋盤，只要找到井字號就檢查四個角，四個角都有井字號時就是主教放的位置。


```cpp=
#include<bits/stdc++.h>
using namespace std;
 
int main(){
    int r;
    cin >> r;
    for(int i=0;i<r;i++){
        string s;
        int x,y;
        int space[10][10];
        for(int j=1;j<=8;j++){
            cin >> s;
            for(int k=1;k<=8;k++){
                if(s[k-1]=='.'){
                    space[j][k] = 0;
                }
                else if(s[k-1]=='#'){
                    space[j][k] = 1;
                }
            }
        }
        for(int j=1;j<=8;j++){
            for(int k=1;k<=8;k++){
                if(space[j][k]==1&&space[j+1][k+1]==1&&space[j+1][k-1]==1&&space[j-1][k+1]==1&&space[j-1][k-1]==1){
                    x=j;
                    y=k;
                }
            }
        }
        cout << x << ' ' << y << '\n';
    }
 
}
```

---

## 新北市賽考古題

### 鋪磁磚問題

這是dp問題，我們發現直接用遞迴會太慢，因此我們用一個陣列F紀錄這個答案的值。

```cpp=
#include<bits/stdc++.h>
#define int long long int
using namespace std;

int F[100];

int f(int n){
    if(F[n]>0)return F[n];

    F[n] = f(n-1)+f(n-2)+f(n-3);
    return F[n];
}

signed main(){
    int n;
    cin >> n;
    F[1] = 1;
    F[2] = 2;
    F[3] = 4;

    cout << f(n) << '\n';
}

```
### 製作看板

```cpp=
#include<bits/stdc++.h>
using namespace std;
char m[100][100];
int main(){
    int r,c,dcnt=0;
    string s;
    cin >> r >> c;
    cin >> s;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cin >> m[i][j];
            if(m[i][j] == '.')dcnt++; //計算有幾個點
        }
    }
    if(s.size()<dcnt){ // 條件符合就代表字串兩旁要留空位
        int spacelen = (dcnt - s.size())/2;
        string tmp = string(spacelen,'.');
        s = tmp + s + tmp;
    }

    //將空位替換成我們的字串
    int nowi = 0;
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            if(m[i][j] == '.'){
                m[i][j] = s[nowi];
                nowi++;
            }
        }
    }

    //輸出答案
    for(int i=0;i<r;i++){
        for(int j=0;j<c;j++){
            cout << m[i][j];
        }
        cout << '\n';
    }
}

```

### 質數切割法

用到遞迴

```cpp=
#include<bits/stdc++.h>
#define int long long int
using namespace std;
 
int F[100];
 
bool check(int n){ // 檢查是否為質數
    if(n == 1) return 0;
    for(int i=2;i<=sqrt(n);i++){
        if(n%i == 0)return 0;
    }
    return 1;
}
 
int f(int l){ //遞迴函式
    if(l<=3)return 0;
    int best = 1000000007;
    for(int i=1;i<=l/2;i++){
        if(check(i)==1 && check(l-i) == 1){
            int sum = l+f(i)+f(l-i);
            best = min(sum,best);
        }
    }
    return (best== 1000000007? 0 : best); //三元運算子
}
 
signed main(){
    int l;
    cin >> l;
    cout << f(l) << '\n'; // 開始遞迴
}

```



### 賓果遊戲


```cpp=
#include<bits/stdc++.h>
using namespace std;
int a[100],m[100][100];
int main(){
    int n;
    cin >> n;
    int ans =0 ,ans2 = 0;
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        a[x]++;
    }
    //初始化我的二維陣列
    for(int i=0;i<5;i++){
        for(int j=0;j<5;j++){
            int y;
            cin >> y;
            if(a[y]>0)m[i][j] = 1;
            else m[i][j] = 0;
        }
    }

    //水平行檢查
    for(int i=0;i<5;i++){
        int ok = 0;
        for(int j=0;j<5;j++){
            if(m[i][j] == 0)ok++;
        }
        if(ok == 0)ans++;
        else if(ok == 1)ans2++;
    }

    //垂直列檢查
    for(int i=0;i<5;i++){
        int ok = 0;
        for(int j=0;j<5;j++){
            if(m[j][i] == 0)ok++;
        }
        if(ok == 0)ans++;
        else if(ok == 1)ans2++;
    }

    //左上右下斜線檢查
    int ok2 = 0;
    for(int i=0;i<5;i++){
        if(m[i][i] == 0)ok2++;
    }
    if(ok2 == 0)ans++;
    else if(ok2 == 1)ans2++;

    //右上左下斜線檢查
    ok2 = 0;
    for(int i=0;i<5;i++){
        if(m[i][5-i-1] == 0)ok2++;
    }
    if(ok2 == 0)ans++;
    else if(ok2 == 1)ans2++;
    cout << ans << " " << ans2 << '\n';
}

```


### 報表排序

```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
    int t;
    cin >> t;
    while(t--){
        vector<pair<string,int>> v; //存部門對應的數字
        vector<string> v2; //存部門代號
        int num[100]; // 存報表內容

        string s;
        cin.get(); // 把換行字元吃掉，不然getline不會讀到東西
        getline(cin,s); // 連空白都會讀進去的輸入字串語法
        string tmp;//暫存字元


        //如果碰到空白就代表部門的編號尾巴已經結束了，就可以直接push_back進去vector裡面
        for(int i=0;i<s.size();i++){
            if(s[i] != ' '){
                tmp+=s[i];
            }else{
                v2.push_back(tmp);
                tmp.clear(); // 清空string裡面的字元
            }
        }
        v2.push_back(tmp); // 因為最後一個部門後面不會有空白所以不會進入到v2中，因此最後需要將它加進去

        for(int i=0;i<v2.size();i++){
            cin >> num[i];
        }

        for(int i=0;i<v2.size();i++){
            v.push_back(make_pair(v2[i],num[i]));
        }
        sort(v.begin(),v.end());

        for(int i=0;i<v.size();i++){
            cout << v[i].first << " " << v[i].second << '\n';
        }
    }
}


```

###### tags: `中和高中`