112 上學期電算社 C++ 班社課

社網：https://hsnu-crc-45.github.io/web/
下學期 C++ 社課：https://hackmd.io/@harrisyu/hsnucrc1122

各大 OJ （線上評測系統）

• ZeroJudge 龐大題庫（很多水題就是了）
  • 使用方式
• TIOJ 建中的OJ
• Codeforces
• AtCoder
• CSES

---

9/8 社課

• 簡報：9/1 複習、變數運算、選擇結構
• 上禮拜上課用的筆記：Hello world、資料型態與變數

課後練習

• ZeroJudge a001
• ZeroJudge e926
• ZeroJudge a002
• ZeroJudge a003
• ZeroJudge d050
• ZeroJudge d065
• ZeroJudge d827
• ZeroJudge e835

詳解

a001. 哈囉

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin >> s;
    cout << "hello, " << s;
}

e926. 跳脫字元

在有些符號之前加上反斜線 "\" 會有特殊的作用
像是 "\n" 為換行字元，這些符號稱為 "跳脫字元"
如果要取消這些有功能符號，可以在這些符號前再加上一個 "\"

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    cout << "|'o'|" << '\n';
    cout << "\\^_^/" << '\n';
    cout << "(\"o\")" << '\n';
    cout << "[-%-]";
    
    /*    你也可以這樣寫，只是很醜
    cout << "|'o'|\n\\^_^/\n(\"o\")\n[-%-]";
    */
}

a002. 簡易加法

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    cout << a+b;
}

a003. 兩光法師占卜術

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int m, d, s;
    cin >> m >> d;
    s=(m*2+d)%3;
    if(s==0) cout << "普通";
    else if(s==1) cout << "吉";
    else cout << "大吉";
}

d050. 妳那裡現在幾點了？

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a;
    cin >> a;
    a+=9;
    if(a>=24) a-=24;
    cout << a;
}

d065. 三人行必有我師 (1 行版)

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    if(a>=b&&a>=c) cout << a;
    else if(b>=a&&b>=c) cout << b;
    else cout << c;
}

d827. 買鉛筆

一打比較便宜

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    cout << n/12*50+n%12*5 << endl;
}

e835. p2. 表演座位 (Seats)

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin >> n;
    if(n<=2500){
        if(n%25) cout << "1 " << n/25+1 << ' ' << n%25;
        else cout << "1 " << n/25 << ' ' << 25;
    }
    else if(n<=7500){
        if((n-2500)%50) cout << "2 " << (n-2500)/50+1 << ' ' << (n-2500)%50;
        else cout << "2 " << (n-2500)/50 << ' ' << 50;
    }
    else{
        if((n-7500)%25) cout << "3 " << (n-7500)/25+1 << ' ' << (n-7500)%25;
        else cout << "3 " << (n-7500)/25 << ' ' << 25;
    }
}

9/15 社課

• 簡報：迴圈

課後練習

• ZeroJudge a244
• ZeroJudge a005
• ZeroJudge a010
• ZeroJudge a024 （要用迴圈做哦~）
• ZeroJudge a038
• ZeroJudge c013
• ZeroJudge j605

詳解

a244. 新手訓練 ~ for + if

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    long long n, a, b, c;
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a >> b >> c;
        if(a==1) cout << b+c << '\n';
        if(a==2) cout << b-c << '\n';
        if(a==3) cout << b*c << '\n';
        if(a==4) cout << b/c << '\n';
    }
}

a005. Eva 的回家作業

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int t, a, b, c, d;
    cin >> t;
    for(int i=0; i<t; i++){
        cin >> a >> b >> c >> d;
        cout << a << ' ' << b << ' ' << c << ' ' << d << ' ';
        if(a+c==2*b) cout << 2*d-c << '\n';
        else if(a*c==b*b) cout << d*d/c << '\n';
    }
}

a010. 因數分解

最小質數為

$2$，所以從

$2$ 開始除
對於每個

$i$ 都要檢查是否可以整除

$a$
利用

$n$ 紀錄其指數部分

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a;
    cin >> a;
    for(int i=2; i<=a; i++){
        int n=0;
        while(a%i==0){
            if(n==0) cout << i;
            a/=i;
            n++;
        }
        if(n>1) cout << "^" << n;
        if(a==1) break;
        if(n!=0) cout << " * ";
    }
}

a024. 最大公因數(GCD)

本題利用輾轉相除法

$\mathrm{\forall }a,b,q,r\in Z$
若

$a=bq+r$，則

$gcd(a,b)=gcd(b,r)$

以下為證明

$(a,b)|a\wedge (a,b)|b\Rightarrow (a,b)|a-bq=r$

$\Rightarrow (a,b)|(b,r)$

$(b,r)|b\wedge (b,r)|r\Rightarrow (b,r)|bq+r=a$

$\Rightarrow (b,r)|(a,b)$

$\therefore (a,b)=(b,r)$

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a, b;
    cin >> a >> b;
    while(b){
        int r=a%b;
        a=b;
        b=r;
    }
    cout << a << '\n';
}

a038. 數字翻轉

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a, ans=0;
    cin >> a;
    while(a){
        ans=ans*10+a%10;
        a/=10;
    }
    cout << ans;
}

c013. 00488 - Triangle Wave

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int n, a, f;

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> a >> f;
        for(int j=0; j<f; j++){
            for(int k=1; k<=a; k++){
                for(int l=0; l<k; l++) cout << k;
                cout << '\n';
            }
            for(int k=a-1; k>=0; k--){
                for(int l=0; l<k; l++) cout << k;
                cout << '\n';
            }
        }
    }
}

j605. 1. 程式考試

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int n, mxt, mx, wrong=0;

int main(){
    cin >> n;
    for(int i=0, t, s; i<n; i++){
        cin >> t >> s;
        if(!i) mxt=t, mx=s;
        if(s>mx) mxt=t, mx=s;
        if(s==-1) wrong++;
    }
    int sum=mx-n-wrong*2;
    if(sum<0) sum=0;
    cout << sum << ' ' << mxt << '\n';
}

9/22 社課

• 簡報：陣列與字串

課後練習

• ZeroJudge a015
• ZeroJudge a224
• ZeroJudge a248
• ZeroJudge a528
• ZeroJudge a628
• ZeroJudge b367
• ZeroJudge b759
• ZeroJudge e267
• ZeroJudge e798
• ZeroJudge j606

詳解

a015. 矩陣的翻轉

從題目中給的範例可以看出

$b[i][j]=a[j][i],0\le i<c,0\le j<r$
其中

$a$ 是原陣列，

$b$ 是翻轉後的陣列

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int r, c, a[105][105], b[105][105];

int main(){
    while(cin >> r >> c){
        for(int i=0; i<r; i++){
            for(int j=0; j<c; j++){
                cin >> a[i][j];
            }
        }
        for(int i=0; i<c; i++){
            for(int j=0; j<r; j++){
                b[i][j] = a[j][i];
            }
        }
        for(int i=0; i<c; i++){
            for(int j=0; j<r; j++){
                cout << b[i][j] << ' ';
            }
            cout << '\n';
        }
    }
}

a224. 明明愛明明

先把小寫換成大寫（都換成其中一種），然後計算每個字母數量
如果每個字母數量都是偶數，就一定可以形成迴文
如果有一個字母數量為奇數，那那個多出來的字母可以放在中間
但若有超過一個字母數量為奇數，就無法形成迴文

參考程式碼

#include<bits/stdc++.h>
using namespace std;

string a, b;

int main(){
    while(cin >> a){
        int x[30]={}, y=0;
        b="";
        for(int i=0; i<a.length(); i++){
            if(a[i]>='A'&&a[i]<='Z') b+=a[i];
            else if(a[i]>='a'&&a[i]<='z') b+=a[i]-'a'+'A';
        }
        for(int i=0; i<b.length(); i++) x[b[i]-'A']++;
        for(int i=0; i<=25; i++){
            if(x[i]%2){
                y++;
            }
        }
        if(y<=1) cout << "yes !" << '\n';
        else cout << "no..." << '\n';
    }
}

a248. 新手訓練 ~ 陣列應用

這題根本不需要用到陣列（
直式除法怎麼做，我們就怎麼做

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int a, b, c, n=0;

int main(){
    while(cin >> a >> b >> n){
        c=a/b;
        a=a%b*10;
        cout << c << '.';
        for(int i=0; i<n; i++){
            c=a/b;
            a=a%b*10;
            cout << c;
        }
        cout << '\n';
    }
}

a528. 大數排序

這題超綱了（
你們就且看且看吧

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int n;
string s[1005];

bool cmp(string a, string b){
    if(a[0]!='-'&&b[0]=='-') return false;
    if(a[0]=='-'&&b[0]!='-') return true;
    if(a[0]!='-'&&b[0]!='-'){
        if(a.length()==b.length()){
            for(int i=0; i<a.length(); i++){
                if(a[i]!=b[i]) return a[i]<b[i];
            }
        }
        return a.length()<b.length();
    }
    if(a[0]=='-'&&b[0]=='-'){
        if(a.length()==b.length()){
            for(int i=1; i<a.length(); i++){
                if(a[i]!=b[i]) return a[i]>b[i];
            }
        }
        return a.length()>b.length();
    }
}

int main(){
    while(cin >> n){
        for(int i=0; i<n; i++) cin >> s[i];
        sort(s, s+n, cmp);
        for(int i=0; i<n; i++) cout << s[i] << '\n';
    }
}

a628. 8. Number Spiral

螺旋矩陣
每個人都要體驗一遍的基礎實作題

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int n, a[20][20];

int main(){
    while(cin >> n){
        int turn=0, x=n/2, y=n/2;
        a[x][y]=0;
        int cnt=1, t=1;
        for(int i=0; i<n-1; i++){
            for(int j=0; j<t; j++){
                if(turn==0) y++;
                else if(turn==1) x--;
                else if(turn==2) y--;
                else if(turn==3) x++;
                a[x][y]=cnt;
                cnt++;
            }
            turn++;
            if(turn==4) turn=0;
            for(int j=0; j<t; j++){
                if(turn==0) y++;
                else if(turn==1) x--;
                else if(turn==2) y--;
                else if(turn==3) x++;
                a[x][y]=cnt;
                cnt++;
            }
            turn++;
            if(turn==4) turn=0;
            t++;
        }
        for(int j=0; j<t; j++){
            if(turn==0) y++;
            else if(turn==1) x--;
            else if(turn==2) y--;
            else if(turn==3) x++;
            a[x][y]=cnt;
            cnt++;
        }
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(a[i][j]>=100) cout << ' ';
                else if(a[i][j]>=10) cout << "  ";
                else cout << "   ";
                cout << a[i][j];
            }
            cout << '\n';
        }

    }
}

b367. 翻轉世界

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int t, n, m, arr[15][15];

int main(){
    cin >> t;
    while(t--){
        cin >> n >> m;
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                cin >> arr[i][j];
            }
        }
        bool flag=0;
        for(int i=0; i<n; i++){
            if(flag) break;
            for(int j=0; j<m; j++){
                if(arr[i][j]!=arr[n-1-i][m-1-j]) flag=1;
            }
        }
        if(flag) cout << "keep defending\n";
        else cout << "go forward\n";
    }
}

b759. 我明明就有說過= =

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    string a;
    cin >> a;
    for(int i=0; i<a.length(); i++){
        for(int j=i; j<a.length()+i; j++){
            cout << a[j%a.length()];
        }
        cout << '\n';
    }
}

e267. 11192 - Group Reverse

參考程式碼

#include <bits/stdc++.h>
using namespace std;

int n;
string s;

int main(){
    while(cin >> n, n){
        cin >> s;
        int cnt=s.length()/n, last=0;
        for(int i=0; i<n; i++){
            for(int j=last+cnt-1; j>=last; j--){
                cout << s[j];
            }
            last+=cnt;
        }
        cout << '\n';
    }
}

e798. p5. 卷積神經網路

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int n, arr[20][20];

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin >> arr[i][j];
        }
    }
    for(int i=0; i<n; i+=2){
        for(int j=0; j<n; j+=2){
            int mx=arr[i][j];
            if(arr[i+1][j]>mx) mx=arr[i+1][j];
            if(arr[i][j+1]>mx) mx=arr[i][j+1];
            if(arr[i+1][j+1]>mx) mx=arr[i+1][j+1];
            cout << mx << ' ';
        }
        cout << '\n';
    }
}

j606. 2. 造字程式

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int k, q, r;
string s;
char arr[25][25];

int main(){
    cin >> k >> q >> r >> s;
    for(int i=0; i<s.length(); i++) arr[0][i+1]=s[i];
    for(int i=1; i<=q; i++){
        for(int j=1, x; j<=k; j++){
            cin >> x;
            arr[i][x]=arr[i-1][j];
        }
    }
    for(int i=1; i<=r; i++){
        for(int j=1; j<=q; j++){
            cout << arr[j][i];
        }
        cout << '\n';
    }
}

10/13 社課

• 簡報：函式

課後練習

• e156. 良心題: 求和
• d487. Order's computation process
• d255. 11417 - GCD
• c002. 10696 - f91
• c039. 00100 - The 3n + 1 problem
• c813. 11332 - Summing Digits
• a227. 三龍杯 -> 河內之塔

詳解

e156. 良心題: 求和

做人要有良心（

參考程式碼

#include<bits/stdc++.h>
using namespace std;

int n;

int sum(int a){
    if(a==1) return a;
    return a+sum(a-1);
}

int main(){
    cin >> n;
    cout << sum(n);
}

d487. Order's computation process

#include<bits/stdc++.h>
using namespace std;

int n;

void solve(int a, int ans){
    if(a==0){
        cout << "= " << ans;
        return;
    }
    if(a==n){
        cout << a << ' ';
        solve(a-1, ans*a);
        return;
    }
    cout << "* " << a << ' ';
    solve(a-1, ans*a);

}

int main(){
    while(cin >> n){
        cout << n << "! = ";
        if(n==0) cout << "1 = 1";
        else solve(n, 1);
        cout << '\n';
    }
}

d255. 11417 - GCD

題目就給答案了

順便補充一下
while(cin >> n, n)
意思是讀到 n==0 或 EOF(End of File)

#include<bits/stdc++.h>
using namespace std;

int n, g=0;

int gcd(int a, int b){
    if(a%b==0) return b;
    return gcd(b, a%b);
}

int main(){
    while(cin >> n, n){
        g=0;
        for(int i=1; i<n; i++){
            for(int j=i+1; j<=n; j++){
                g+=gcd(i,j);
            }
        }
        cout << g << '\n';
    }
}

c002. 10696 - f91

#include<bits/stdc++.h>
using namespace std;

int f(int k){
    if(k<=100){
        return f(f(k+11));
    }
    else
        return k-10;
}

int main(){
    int a;
    while(cin >> a, a){
        cout << "f91(" << a << ") = " << f(a) << '\n';
    }
}

c039. 00100 - The 3n + 1 problem

#include<bits/stdc++.h>
using namespace std;

int main(){
    int a, b;
    while(cin >> a >> b){
        int mx=0;
        for(int i=min(a, b); i<=max(a, b); i++){
            int n=i, cnt=0;
            while(n!=1){
                if(n%2) n=3*n+1;
                else n/=2;
                cnt++;
            }
            cnt++;
            if(cnt>mx) mx=cnt;

        }
        cout << a << ' ' << b << ' ' << mx << '\n';
    }
}

c813. 11332 - Summing Digits

記得比較上面的函式讀不到下面還沒宣告的函式
所以 g() 要放下面

#include<bits/stdc++.h>
using namespace std;

int f(int n){
    int s=0;
    while(n>=10){
        s+=n%10;
        n/=10;
    }
    s+=n;
    return s;
}

int g(int n){
    while(n>=10) n=f(n);
    return n;
}

int main(){
    int n;
    while(cin >> n, n){
        cout << g(n) << '\n';
    }
}

a227. 三龍杯 -> 河內之塔

經典題ㄋㄟ，怎麼能不會
弄懂他才算真正進入遞迴的領域

#include<bits/stdc++.h>
using namespace std;

int hanoi(int n, char a, char b, char c){
    if(n==1){
        cout << "Move ring "<< 1 << " from " << a << " to " << c << '\n';
    }
    else{
        hanoi(n-1, a, c, b); // n-1 個做河內塔
        cout << "Move ring "<< n << " from " << a << " to " << c << '\n';
        hanoi(n-1, b, a, c);
    }
}

int main(){
    int n;
    while(cin >> n){
        hanoi(n, 'A', 'B', 'C');
        cout << '\n';
    }
}

10/20 第一次社內賽

• 題本
• 題解

10/27 社課

• 簡報：指標

11/3 社課

• 簡報：struct、STL(1)

課後練習

• d091. 00476 - Points in Figures: Rectangles
• a104. 排序
• h075. 成績排名
• a915. 二维点排序
• k184. pA. 房屋推薦 (house) 如果太難我會把它撤掉（

詳解

d091. 00476 - Points in Figures: Rectangles

我寫題解才發現他的測資是爛的XD
在第 985 個點處輸出沒有空格

#include<bits/stdc++.h>
using namespace std;

char c;
double x, y;
int num=0;

struct rect{
    double a, b, c, d;
};
vector<rect> v;

int main(){
    while(cin >> c){
        if(c=='*') break;
        double a, b, c, d;
        cin >> a >> b >> c >> d;
        v.push_back({a, b, c, d});
    }
    while(cin >> x >> y){
        if(x==9999.9&&y==9999.9) break;
        num++;
        int label=1;
        for(int i=0; i<v.size(); i++){
            if(x>=v[i].a&&x<=v[i].c&&y>=v[i].d&&y<=v[i].b){
                label=0;
                cout << "Point " << num << " is contained in figure " << i+1 << '\n';
            }
        }
        if(label){
            if(num==985){
                cout << "Point " << num << " is not contained in any figure" << '\n';
                continue;
            }
            cout << "Point " << num << " is not contained in any figure " << '\n';
        }
    }
}

a104. 排序

直接看簡報就會啦

#include<bits/stdc++.h>
using namespace std;

int n;

int main(){
    while(cin >> n){
        vector<int> v;
        for(int i=0, x; i<n; i++){
            cin >> x;
            v.push_back(x);
        }
        sort(v.begin(), v.end());
        for(int i=0; i<v.size(); i++) cout << v[i] << ' ';
        cout << '\n';
    }
}

h075. 成績排名

#include<bits/stdc++.h>
using namespace std;

int n;

struct student{
    int id, a, b, c;
    double aver;
    bool operator<(student tmp){
        if(aver!=tmp.aver) return aver<tmp.aver;
        if(a!=tmp.a) return a<tmp.a;
        if(b!=tmp.b) return b<tmp.b;
        if(c!=tmp.c) return c<tmp.c;
        return id>tmp.id; // 編號越小排越前面
    }
} arr[105];

int main(){
    cin >> n;
    for(int i=0; i<n; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        arr[i]={a, b, c, d};
        arr[i].aver=(b*5+c*3+d*2)/10.0; // 平均有可能是小數
    }
    sort(arr, arr+n);
    for(int i=n-1; i>=0; i--) cout << arr[i].id << ' ' << arr[i].aver << '\n';
}

a915. 二维点排序

pair 的大小比較是先比前面再比後面

#include<bits/stdc++.h>
using namespace std;

int n;
vector<pair<int, int>> point;

int main(){
    cin >> n;
    for(int i=0, a, b; i<n; i++){
        cin >> a >> b;
        point.push_back({a, b});
    }
    sort(point.begin(), point.end());
    for(int i=0; i<n; i++) cout << point[i].first << ' ' << point[i].second << '\n';
}

k184. pA. 房屋推薦 (house)

TOI 初選的題目
如果只是單純排序的話會 TLE
要做 IO 優化

#include<bits/stdc++.h>
using namespace std;

int n, m;
struct house{
    int id, r;
    long long x, y;
    long long mnd=(1LL<<63)-1; // 設為 long long 最大值
    bool operator<(house a){
        if(mnd==a.mnd&&r==a.r) return id<a.id;
        if(mnd==a.mnd) return r<a.r;
        return mnd<a.mnd;
    }
} home[100005];

int main(){
    ios::sync_with_stdio(0); cin.tie(0); // 你們可以把這串程式碼拿去查他是什麼

    cin >> n >> m;
    for(int i=0; i<n; i++){
        cin >> home[i].x >> home[i].y >> home[i].r;
        home[i].id=i+1;
    }
    for(int i=0, x, y; i<m; i++){
        cin >> x >> y;
        for(int j=0; j<n; j++){
            home[j].mnd=min(home[j].mnd, (x-home[j].x)*(x-home[j].x)+(y-home[j].y)*(y-home[j].y));
        }
    }
    sort(home, home+n);
    for(int i=0; i<n; i++) cout << home[i].id << '\n';
}

11/10 社課

• 簡報：STL(2)

課後練習

• e447. queue 練習
• i213. stack 練習
• e155. 10935 - Throwing cards away I
• a565. 2.p&q的邂逅
• c123. 00514 - Rails
• d221. 10954 - Add All
• c875. 107北二2.裝置藝術
• d123. 11063 - B2-Sequence
• e641. 10260 - Soundex

11/17 社課

• 簡報：Linked list

課後練習

• b938. kevin 愛殺殺
• [TIOJ 1225] 數字合併
• [Sprout 21] 陸行鳥大賽車
• [Sprout 25] 一天遊戲只能一小時

12/1 社課

• 簡報：重載、前置處理、其他…

12/15 社課

• 簡報：複雜度

12/22 社課

• 簡報：進位制、二進位存儲與運算

12/29 第二次社內賽

• 題本
• 題解