# 競程班第二堂社課
:::spoiler 目錄:
[TOC]
:::

## 開始之前
來稍微複習一下上一堂的內容

### 程式架構:

#include<bits/stdc++.h>
using namespace std;
int main(){
    //code
    return 0;
}

---
### 變數型態:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a = 1234;
    string s1 = "qwerty", s2 = "This is a string.";
    char c = 'a';
    float f = 1.234;
    bool b = true; //bool b = 1;
    return 0;
}

---
### 輸入輸出、四則運算:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    string s1,s2;
    cin>>a>>b>>s1>>s2;
    cout<<"a + b = "<<a+b<<endl;
    cout<<"s1 is "<<s1<<endl;
    cout<<"s2 is "<<s2<<endl;
    return 0;
}

---
### 條件式:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    if(n == 0){
        cout<<"n is 0"<<endl;
    }
    else if(n == 1){
        cout<<"n is 1"<<endl;
    }
    else if(n < 0){
        cout<<"n is negative"<<endl;
    }
    else{
        cout<<"n is very big"<<endl;
    }
    return 0;
}

:::warning
:warning:
== 用於判斷
= 用於賦值
:::

---
### 布林運算子:
計算布林值之間的關係，回傳布林值
**AND: &&
OR: ||
NOT: !**
| AND | True | False |
|----| ---- | ----- |
| True | True | False |
| False | False | False |

| OR | True | False |
|----| ---- | ----- |
| True | True | True |
| False | True | False |

| NOT | True | False |
|----| ---- | ----- |
|----| False | True |

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a;
    cin>>a;
    if(a > 0 && !( a % 2 == 0)){
        cout<<a<<" is a positive odd number"<<endl;
    }
    else{
    	cout<<a<<" is not a positive odd number"<<endl;
	}
    return 0;
}

:::warning
:warning: 多用括號
:::

---
## IDE
整合開發環境
通常包含編輯器、除錯器、編譯器or直譯器。
### [vscode](https://code.visualstudio.com/)
不含編譯器，安裝過程麻煩
### [Code::Blocks](https://www.codeblocks.org/)
APCS指定IDE
### [Dev-C++](https://www.bloodshed.net/)
介面簡潔、適合入門。但版本很舊，所以我都用[embarcadero dev-c++](https://www.embarcadero.com/free-tools/dev-cpp/free-download)（語言記得選英文）

## OJ
online judge，線上解題系統
### [Codeforces](https://codeforces.com/)
題目、比賽超多，打競程的通常用這個最多，不過很多怪題。
### [CSES](https://cses.fi/problemset/list/)
只有300題，但都是很經典的題型，刷這個對APCS、TOI很有幫助。
### [Atcoder](https://atcoder.jp/home)
日本網站，因此比賽時間比Codeforces舒服多了。
### [ZeroJudge](https://zerojudge.tw/)
台灣網站，有APCS和很多比賽的考古題
### [TCIRC](https://judge.tcirc.tw/)
一中電研的OJ，有AP325的習題。
### [TIOJ](https://tioj.ck.tp.edu.tw/)
建中的，有IOICamp和NPSC的題目

## 學習資源
[USACO Guide](https://usaco.guide/) 英文，各個難度都有，有很多參考code
[AP325](https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m) 中文，適合APCS 3級

## 如何寫題目
以Codeforces為例。
在problemset裡面可以照難度或通過人數排序，假設你選了通過人數最多的[這一題](https://codeforces.com/problemset/problem/4/A)


題目大意:給你一個正整數$w$，問它是否可以拆成兩個正偶數之和。

解法:
$w$必須要是不為2的正偶數才會是`Yes`，否則都是`No`。

打開你的Dev-C++，打程式:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int w;
    cin>>w;
    if(w % 2 == 0 && w != 2){
        cout<<"YES"<<endl;
    }
    else{
        cout<<"NO"<<endl;
    }
    return 0;
}

存檔後(xxx.cpp)按下compile and run

會出現一個exe檔，你可以在這裡測試範例測資，輸入8，按Enter，應該輸出YES

回到Codeforces，在右方找到這個。
Luaguage選擇GNU C++20 11.2.0 (64bit,winlbs)，檔案選擇剛剛的cpp檔(不是exe檔)

submit後會到這個畫面
按 # 可以看到詳細資料
Verdict大致可能有以下結果(各OJ皆如此):
* AC (Accept): 你通過了，你超電
* WA (Wrong Answer): 表示答案錯誤
* TLE (Time Limit Exceed): 表示執行超過時間限制
* MLE (Memory Limit Exceed): 表示程序執行超過記憶體限制
* OLE (Output Limit Exceed): 表示程序輸出檔超過限制
* RE (Runtime Error): 表示執行時錯誤，通常為記憶體配置錯誤 如：使用了超過陣列大小的位置
* CE (Compile Error): 表示編譯錯誤。

## 迴圈
### while
使用方式: while(繼續的條件){}
會重複大括號內的程式直到判斷式為`false`(0)

---

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a = 10;
    while(a > 0){
        cout<<a<<' ';
        a -= 1;
    }
    return 0;
}

輸出:

---
:::info
補充:

while(a > 0)

也可以寫成

while(a)

因為當把一個`int`當作條件式時，$0$會視為`false`，而其他數字會被視為`true`。
因此，`while(1)`會是一個無限迴圈。
:::

---
:::info
補充:

int n;
while(cin>>n){
    //code
}

cin >> n是取得n之後，把n賦予給cin，如果能賦予，就會回傳true，則條件式成立，進入while迴圈
反之，如果輸入無效或EOF(End of File)，n無法賦予給cin，則條件式不成立，跳脫迴圈
:::

---
### for
使用方式: for(開始迴圈前做的事;繼續的條件;每跑一圈**後**會做的事){}

---

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int i = 0; i <= 10; i++){
        cout<<i<<' ';
    }
    return 0;
}

寫成while的話就是:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int i = 0;
    while(i <= 10){
        cout<<i<<' ';
        i++;
    }
    return 0;
}

輸出:

---

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int i = 1; i < 1000; i *= 2){
        cout<<i<<' ';
    }
    return 0;
}

輸出:

---

### 巢狀迴圈
就字面上的意思

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int i = 1; i <= 4; i++){
    	for(int j = 0; j < i; j++){
            cout<<'*';
        }
        cout<<endl;
    }
    return 0;
}

輸出:

---
### break 與 continue
break: 跳脫迴圈
continue: 結束這一圈

---

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int i = 0; ; i++){ //for迴圈沒有條件式會視為無限迴圈
        if(i > 10){
            break;
        }
        cout<<i<<' ';
    }
    return 0;
}

輸出:

---

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int i = 0; i < 10; i++){
        if(i % 2 == 0){
            continue;
        }
        cout<<i<<' ';
    }
    return 0;
}

輸出:

---
### 變數的有效範圍
對於在for迴圈內宣告的變數，只會在大括號範圍內有效。

#include<bits/stdc++.h>
using namespace std;
int main(){
    for(int i = 0; i < 10; i++){
        //code
    }
    cout<<i; //<---這裡會報錯
}

## 陣列
一串東西
宣告:

int a[3], b[4]={0,1,10000,-1};
string s[2]={"qwerty","123456"};

中括號內是大小
:::warning
:warning: 索引值(index)從0開始，大小為3的陣列裡面分別是第0項、第1項、第2項。
:::
### 存取

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[3]={100, 1, -10};
    a[1] = 6;     //{100,6,-10}
    a[0] += 99;   //{199,6,-10}
    a[2] -= a[1]; //{199,6,-16}
    a[0] ++;      //{200,6,-16}
    return 0;
}

### 遍歷陣列

---

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a[4] = {-1, 2, 1000, 0};
    for(int i = 0; i < 4; i++){
        cout<<a[i]<<' ';
    }
    return 0;
}

輸出:

---
題目要輸入一個陣列時，通常會先跟你說它的大小，像[這一題](https://cses.fi/problemset/task/1094):

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    //code
}

---
### 二維陣列
即陣列的陣列，可以想成是一個表格。
宣告:

int a[2][3]={{1, 9, 10}, {4, 0, -6}};
bool b[100][3][4]; //三維陣列

基本上和一維一樣。

---

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    cin>>n>>m;
    int a[n][m];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            cin >> a[i][j];
        }
    }
}

---
## 常用函式
需`#include<algorithm>`，如果已經用了`#include<bits/stdc++.h>`就不用。

int a = 3, b = 4, c = 5;
int mn = min({a, b, c});
int mx = max({a, b, c, -100000});
//如果只有兩項可以不用大括號，如 max(a,b)
swap(a, b); //a 變為 4，b 變為 3

## 練習題
:::warning
:warning: 如果運算過程會超過`int`範圍($-2^{31}$到$2^{31}-1$)，請改用`long long`
:::
[b016: 山谷的回聲](https://judge.tcirc.tw/ShowProblem?problemid=b016)
:::spoiler AC code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    for(int i = 0; i < n; i++){
        cout<<"Hello, World!"<<endl;
    }
    return 0;
}

:::
\
[b021: 電電找因數](https://judge.tcirc.tw/ShowProblem?problemid=b021)
:::spoiler AC code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        for(int i = 1; i <= n;i++){
            if(n % i == 0){
                cout<<i<<" ";
            }
        }
        cout<<endl;
    }
}

:::
\
[b026: 乖乖寫作業](https://judge.tcirc.tw/ShowProblem?problemid=b026)
:::spoiler AC code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    long long a[n];
    for(int i = 0; i < n; i++){
        cin>>a[i];
    }
    for(int i = n - 1; i >= 0; i--){
        cout<<a[i]<<" ";
    }
    cout<<endl;
    return 0;
}

:::
\
[b027: 找出學霸](https://judge.tcirc.tw/ShowProblem?problemid=b027)
:::spoiler AC code

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    while(cin>>n){
        int mxpos, mxval = -1, mnpos, mnval = 101;
        for(int nowpos = 0; nowpos < n; nowpos++){
            int nowval;
            cin>>nowval;
            if(nowval > mxval){
                mxval = nowval;
                mxpos = nowpos;
            }
            if(nowval < mnval){
                mnval = nowval;
                mnpos = nowpos;
            }
        }
        cout<<mxpos + 1<<' '<<mxval<<' '<<mnpos + 1<<' '<<mnval<<endl;
    }
    return 0;
}

:::
\
[Weird Algorithm](https://cses.fi/problemset/task/1068)
:::spoiler AC code

#include<bits/stdc++.h>
using namespace std;
signed main(){
    long long n;
    cin>>n;
    cout<<n<<" ";
    while(n != 1){
        if(n % 2 == 1){
            n = n * 3 + 1;
            cout<<n<<" ";
        }
        else{
            n /= 2;
            cout<<n<<" ";
        }
    }
    return 0;
}

:::
\
[Missing Number](https://cses.fi/problemset/task/1083)
:::spoiler 提示:
可以用數學解
:::
:::spoiler AC code

#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,sum;
    cin>>n;
    sum=n * (n + 1) / 2;
    for(int i = 0; i < n - 1; i++){
        int a;
        cin>>a;
        sum-=a;
    }
    cout<<sum<<endl;

:::
\
[Increasing Array](https://cses.fi/problemset/task/1094)
:::spoiler AC code:

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, pre, now;
    long long ans=0;
    cin>>n;
    cin>>pre;
    for(int i = 1; i < n; i++){
        cin>>now;
        if(pre > now){
            ans += pre - now;
            now = pre;
        }
        pre = now;
    }
    cout<<ans;
    return 0;
}

:::