---
# System prepended metadata

title: 輔仁中學114學年度學科能力競賽資訊科校內初賽解答

---

# 輔仁中學114學年度學科能力競賽資訊科校內初賽解答
# 初賽題目
https://drive.google.com/file/d/1Gc-kO_fPxCOVtjRkAvmt_cMr6iPsXm9N/view
# 校內初賽練習連結
https://codeforces.com/contestInvitation/464baa45ac0b1f2390b0a05fd29cd33c58386a7f
## problem A-Hello World
### 考點:基本輸入輸出
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int t;
    cin>>t;
    while(t--){
        cin>>s;
        cout<<"Hello, "<<s<<endl;
    }
}

```
## problem B-蛤?除法
### 考點:浮點數數以及小數點後的輸出控制
```cpp=
#include <bits/stdc++.h>
using namespace std;
//考浮點數
int main(){
    long long int a,b;
    cin>>a>>b;
    cout<<fixed<<setprecision(5)<<(long double)a/b<<endl;

}

```
## problem C-破譯密碼
### 考點:字元運算
```cpp=
#include <bits/stdc++.h>
using namespace std;
int main(){
    string s;
    int n;
    int x;
    cin>>s>>x>>n;
    for(int i=0;i<x;i++){
        if(s[i]+n<32){
            cout<<" ";
        }
        else if(s[i]+n>126){
            cout<<"~";
        }
        else
            cout<<(char)(s[i]+n);
        if(s[i]-n<32){
            cout<<" ";
        }
        else if(s[i]-n>126){
            cout<<"~";
        }
        else
            cout<<(char)(s[i]-n);

    }
}

```
## problem D-色塊計算
### 考點:地迴、暴力
```cpp=
#include <bits/stdc++.h>
using namespace std;
vector<int> appear(101,0);
vector<vector<bool>> visited(101,vector<bool>(101,false));
vector<vector<int>> mapp(101,vector<int>(101));
int now;
int n,m;
void ff(int x,int y){
    if(x<0 or x>=n ){}
    else if(y<0 or y>=m){}
    else if(mapp[x][y]==now and !visited[x][y]){
        visited[x][y]=true;
        ff(x+1,y);
        ff(x-1,y);
        ff(x,y+1);
        ff(x,y-1);
    }

}
int main(){

    cin>>n>>m;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>mapp[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            if(!visited[i][j]){
                now=mapp[i][j];
                ff(i,j);
                appear[now]++;
            }
        }
    }
    for(int i=1;i<101;i++){
        cout<<i<<" "<<appear[i]<<endl;
    }
}

```
## problem E-環圖?
### 考點:樹、樹的搜尋、邏輯

```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define Jackis666 ios::sync_with_stdio(0); cin.tie(0)
vector<vector<int>> graph;
vector<bool> visited;
void dfs(int s){
    visited[s]=true;
    for(int e:graph[s]){
        if(!visited[e]){
            dfs(e);
        }
    }
}
signed main(){
    Jackis666;
    int n,m;
    cin>>n>>m;

    graph.resize(n + 1);
    visited.resize(n + 1, false);
    vector<int> cc(n+1,0);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
        cc[a]++;
        cc[b]++;
    }
    if(n!=m){
        cout<<"No";
        return 0;
    }
    for(int i=1;i<=n;i++){
        if(cc[i]!=2){
            cout<<"No";
            return 0;
        }
    }
    dfs(1);
    for(int i=1;i<=n;i++){
        if(!visited[i]){
            cout<<"No";
            return 0;
        }
    }
    cout<<"Yes";




}

```

## problem F-象棋危機
### 考點:邏輯判斷、大型實作
```cpp=
#include <bits/stdc++.h>
using namespace std;
/*K/k: 帥/將
A/a: 仕/士
E/e: 相/象
H/h: 馬/馬
R/r: 車/車
C/c: 炮/包
S/s: 兵/卒
#代表那格沒東西
*/
int dx_h[8] = {-2, -2, 2, 2, -1, 1, -1, 1};//馬方向
int dy_h[8] = {-1, 1, -1, 1, -2, -2, 2, 2};
int bx_h[8] = {-1, -1, 1, 1, 0, 0, 0, 0};//馬有沒有被檔
int by_h[8] = {0, 0, 0, 0, -1, -1, 1, 1};
bool inBoard(int x, int y) {
    return x >= 0 && x < 10 && y >= 0 && y < 9;
}
int main(){
    char who;
    cin>>who;
    string mp[10];
    for(int i=0;i<10;i++){
        cin>>mp[i];
    }
    char tar=(who=='A')?'k':'K';//king
    char sold=(who=='A')?'S':'s';//兵
    char horse=(who=='A')?'H':'h';//馬
    char rook=(who=='A')?'R':'r';//車
    char cannon=(who=='A')?'C':'c';//炮

    int tx=0,ty=0;
    for(int i=0;i<10;i++){
        for(int j=0;j<9;j++){
            if(mp[i][j]==tar){
                tx=j;ty=i;
                break;
            }
        }
    }
    //先找兵
    int dir=(who=='A')?-1:1;
    if(ty+dir>=0 and ty+dir<10 and mp[ty + dir][tx] == sold){
        cout << (who == 'A' ? "A" : "B") << endl;
        return 0;
    }
    if(tx-1>=0 and mp[ty][tx-1]==sold){
        cout << (who == 'A' ? "A" : "B") << endl;
        return 0;
    }
    if(tx+1<9 and mp[ty][tx+1]==sold){
        cout << (who == 'A' ? "A" : "B") << endl;
        return 0;
    }
    //判斷馬
    for (int d = 0; d < 8; ++d) {
        int nx = tx + dx_h[d], ny = ty + dy_h[d];
        int bx = tx + bx_h[d], by = ty + by_h[d];
        if (inBoard(ny, nx) && inBoard(by, bx)) {
            if (mp[ny][nx] == horse && mp[by][bx] == '#') {
                cout << (who == 'A' ? "A" : "B") << endl;
                return 0;
            }
        }
    }
    //判斷車
    for(int d=-1;d<=1;d+=2){
        //垂直
        for(int y=ty+d;y>=0 and y<10;y+=d){
            if(mp[y][tx]=='#') continue;
            if(mp[y][tx]==rook){
                cout << (who == 'A' ? "A" : "B") << endl;
                return 0;
            }
            break;
        }
        for(int x=tx+d;x>=0 and x<9;x+=d){
            if(mp[ty][x]=='#') continue;
            if(mp[ty][x]==rook){
                cout << (who == 'A' ? "A" : "B") << endl;
                return 0;
            }
            break;
        }




    }
    //判斷炮
    for(int d=-1;d<=1;d+=2){
        int ok=0;
        for(int y=ty+d;y>=0 and y<10;y+=d){
            if(mp[y][tx]!='#') ok++;
            if(mp[y][tx]==cannon and ok==2){
                cout << (who == 'A' ? "A" : "B") << endl;
                return 0;
            }
            if(ok>2) break;
        }
        ok=0;
        for(int x=tx+d;x>=0 and x<9;x+=d){
            if(mp[ty][x]!='#') ok++;
            if(mp[ty][x]==cannon and ok==2){
                cout << (who == 'A' ? "A" : "B") << endl;
                return 0;
            }
            if(ok>2) break;
        }

    }
    //最後
    cout<<"C"<<endl;

}

```
## problem G-老師生氣了!
### 考點:動態規劃(dp)、二分搜尋
#### 以0為底
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
//¦Òdp
struct student{
    int s,e;
    int teacher;

};
bool cmp(student &a,student &b){
    if(a.e == b.e) {
        return a.teacher < b.teacher;
    }
    return a.e < b.e;

}
signed main(){
    int n;
    cin>>n;
    vector<student> st(n);
    for(int i=0;i<n;i++){
        cin>>st[i].s>>st[i].e>>st[i].teacher;
    }
    sort(st.begin(),st.end(),cmp);
    vector<int> dp(n,0);
    vector<int> people(n,0);
    dp[0]=st[0].teacher;
    people[0]=1;
    for(int i=1;i<n;i++){
        int now=st[i].teacher;
        int left=0;int right=i-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(st[mid].e<st[i].s){
                left=mid+1;
            }
            else{
                right=mid-1;
            }

        }
        if(right>=0){
            now+=dp[right];
            if(now>dp[i-1]){
                people[i]=people[right]+1;
                dp[i]=now;
            }
            else if(now==dp[i-1]){
                people[i]=min(people[i-1],people[right]+1);
                dp[i]=now;
            }
            else{
                dp[i]=dp[i-1];
                people[i]=people[i-1];
            }
        }
        else{//若找不到就比較前一個和址選這一個
            if (st[i].teacher > dp[i - 1]) {
            dp[i] = st[i].teacher;
            people[i] = 1;
            }
            else if(st[i].teacher == dp[i - 1]) {
            dp[i] = st[i].teacher;
            people[i] = min(people[i - 1], 1LL);
            }
            else{
            dp[i] = dp[i - 1];
            people[i] = people[i - 1];
            }
        }
    }
    cout<<people[n-1]<<" "<<dp[n-1];




}

```
#### 以1為底
```cpp=
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct student{
    int s,e;
    int teacher;

};
bool cmp(student &a,student &b){
    if(a.e == b.e) {
        return a.teacher < b.teacher;
    }
    return a.e < b.e;

}
signed main(){
    int n;
    cin>>n;
    vector<student> st(n+1);st[0].s=0;st[0].e=0;st[0].teacher=0;
    for(int i=1;i<=n;i++){
        cin>>st[i].s>>st[i].e>>st[i].teacher;
    }
    sort(st.begin(),st.end(),cmp);
    vector<int> dp(n+1,0);
    vector<int> people(n+1,0);
    dp[1]=st[1].teacher;
    people[1]=1;
    for(int i=2;i<=n;i++){
        int now=st[i].teacher;
        int left=0;int right=i-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(st[mid].e<st[i].s){
                left=mid+1;
            }
            else{
                right=mid-1;
            }

        }

        now+=dp[right];
        if(now>dp[i-1]){
            people[i]=people[right]+1;
            dp[i]=now;
        }
        else if(now==dp[i-1]){
            people[i]=min(people[i-1],people[right]+1);
            dp[i]=now;
        }
        else{
            dp[i]=dp[i-1];
            people[i]=people[i-1];
        }

    }
    cout<<people[n]<<" "<<dp[n];
}

```
## problem H-為甚麼玻璃要上色?
### 考點:前綴和、邏輯判斷
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
    //Jackis666
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        vector<int>cnt(n+1,0),a(m);
        for(int i=0;i<m;i++){
            cin>>a[i];
            cnt[a[i]]++;
        }
        vector<int>pre(n+2,0);
        for(int i=n;i>0;i--){
            pre[i]=cnt[i]+pre[i+1];
        }
        long long ans=0;
        for(int i=1;i<n;i++){
            int l=pre[i];//左邊顏色
            int r=pre[n-i];//右邊顏色
            int c=pre[max(i,n-i)];//全部同一個顏色
            ans+=1LL*l*r-c;
        }
        cout<<ans<<endl;
    }
}
```