# 競程班第二堂社課
:::spoiler 目錄:
[TOC]
:::
如果你還沒加discord:
## 開始之前
來稍微複習一下上一堂的內容
### 程式架構:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
//code
return 0;
}
```
---
### 變數型態:
```cpp=
#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;
}
```
---
### 輸入輸出、四則運算:
```cpp=
#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;
}
```
---
### 條件式:
```cpp=
#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 |
```cpp=
#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++，打程式:
```cpp=
#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)
---
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int a = 10;
while(a > 0){
cout<<a<<' ';
a -= 1;
}
return 0;
}
```
輸出:
---
:::info
補充:
```cpp
while(a > 0)
```
也可以寫成
```cpp
while(a)
```
因為當把一個`int`當作條件式時，$0$會視為`false`，而其他數字會被視為`true`。
因此，`while(1)`會是一個無限迴圈。
:::
---
:::info
補充:
```cpp=
int n;
while(cin>>n){
//code
}
```
cin >> n是取得n之後，把n賦予給cin，如果能賦予，就會回傳true，則條件式成立，進入while迴圈
反之，如果輸入無效或EOF(End of File)，n無法賦予給cin，則條件式不成立，跳脫迴圈
:::
---
### for
使用方式: for(開始迴圈前做的事;繼續的條件;每跑一圈**後**會做的事){}
---
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
for(int i = 0; i <= 10; i++){
cout<<i<<' ';
}
return 0;
}
```
寫成while的話就是:
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
int i = 0;
while(i <= 10){
cout<<i<<' ';
i++;
}
return 0;
}
```
輸出:
---
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
for(int i = 1; i < 1000; i *= 2){
cout<<i<<' ';
}
return 0;
}
```
輸出:
---
### 巢狀迴圈
就字面上的意思
```cpp=
#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: 結束這一圈
---
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
for(int i = 0; ; i++){ //for迴圈沒有條件式會視為無限迴圈
if(i > 10){
break;
}
cout<<i<<' ';
}
return 0;
}
```
輸出:
---
```cpp=
#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迴圈內宣告的變數，只會在大括號範圍內有效。
```cpp=
#include<bits/stdc++.h>
using namespace std;
int main(){
for(int i = 0; i < 10; i++){
//code
}
cout<<i; //<---這裡會報錯
}
```
## 陣列
一串東西
宣告:
```cpp
int a[3], b[4]={0,1,10000,-1};
string s[2]={"qwerty","123456"};
```
中括號內是大小
:::warning
:warning: 索引值(index)從0開始，大小為3的陣列裡面分別是第0項、第1項、第2項。
:::
### 存取
```cpp=
#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;
}
```
### 遍歷陣列
---
```cpp=
#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):
```cpp=
#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
}
```
---
### 二維陣列
即陣列的陣列，可以想成是一個表格。
宣告:
```cpp
int a[2][3]={{1, 9, 10}, {4, 0, -6}};
bool b[100][3][4]; //三維陣列
```
基本上和一維一樣。
---
```cpp=
#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>`就不用。
```cpp=
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
```cpp=
#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
```cpp=
#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
```cpp=
#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
```cpp=
#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
```cpp=
#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
```cpp=
#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:
```cpp=
#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;
}
```
:::