{%hackmd @hipp0\Hippotumuxthem %}

<style>

.text-center{
text-align: center; //文字置中
}
.text-left{
text-align: left; //文字靠左
}
.text-right{
text-align: right; //文字靠右
}

</style>

<style>
.reveal .slides {
text-align: left;
font-size:30px;
}
</style>

# C++ 基礎III

---

<h2 style='color:#C4C400'> 複習 </h2>

----

<h3 style='color:#C4C400'> for </h3>

int n = 100;
for(int i = 0 ; i < n ; i++){
    int x;
    cin >> x;
}

----

<h2 style='color:#C4C400'> while </h2>

用法如下：

// 
while (a > b) {
    
}

// 無窮迴圈 
while (true){
    
}

----

<h3 style='color:#C4C400'> 很多條件 (continue/break) </h3>

while (true) {
    if (a > b && c > d && MAP[x][y] == 0) continue;
    else if (a < b && c < d && MAP[x][y] == 1) break;
    cout << "haha" << a << " " << b << endl;
}

----

<h3 style='color:#C4C400'> 離開當前的迴圈? </h3>

以下錯誤寫法

int ans1, ans2;
for (int i = 0 ; i < 10 ; i++) {
    for (int j = i + 1 ; j < 10 ; j++) {
        if (i * j > 78) {
            ans1 = i, ans2 = j;
            break;
        }
    }
}
cout << ans1 << " " << ans2 << endl;

----

<h3 style='color:#C4C400'> 正確寫法 </h3>

int ans1, ans2;
bool check = false;
for (itn i = 0 ; i < 10 ; i++) {
    for (int j = 0 ; j < 10 ; j++) {
        if (i * j > 78) {
            ans1 = i, ans2 = j;
            check = true;
            break;
        }
    }
    if (check) break;
}
cout << ans1 << " " << ans2 << endl;

----

<h2 style='color:#C4C400'> 題目的各種輸入方式 </h2>

----

<h3 style='color:#C4C400'> t筆輸入 </h3>

int t;
cin >> t;
while (t--) {
    // do
}

// 如果題目要求輸出 case i 
for (int i = 1 ; i <= t ; i++) {
    cout << "Case " << i << " ";
    // do
}

----

<h3 style='color:#C4C400'> 輸入直到讀到某個值 </h3>

例如讀到 -1 為止

int t;
cin >> t;
while (true) {
    if (t == -1) break;
    // do
    cin >> t;
}

----

<h3 style='color:#C4C400'> 輸入直到 EOF </h3>

EOF = end of file

int t;
while (cin >> t) {
    // do
}

----

<h3 style='color:#C4C400'> 輸出 n 個數字用空白隔開 </h3>

要求: 尾巴不能有空白

int ans[10] = {2,3,4,1,5,6,7,1,2,3};
bool first = true;
for (int i = 0 ; i < 10 ; i++){
    if (first) {
        cout << ans[i];
        first = false;
    }else{
        cout << " " << ans[i];
    }
}
cout << '\n';

----

<h2 style='color:#C4C400'> 陣列宣告 </h2>

int a[15]; //a[0]~a[14] 共15個
char b[150]; //b[0]~b[149] 共150個
double c[200]; //c[0]~c[199] 共200個
string str[1500]; //str[0]~str[1499] 共1500個

----

<h3 style='color:#C4C400'> 使用 </h3>

int a[5] = {1,2,3,4,5};
cout << a[0] + a[2] << '\n';
a[3] = 6;
cout << a[1] + a[3];
for (int i = 0 ; i < 5 ; i++) { // 注意 是 0~4
    cout << a[i] << ' ';
}
cout << '\n';

----

<h3 style='color:#C4C400'> 多維陣列 </h3>

陣列是可以有多個維度的，例如：

int arr[13][14][15] = {0}; // 設0，
cin >> arr[2][5][6];
cout << arr[2][5][6] << '\n';

// 也可以這樣定義，一樣不夠的會自動補 0 
int arr[2][3] ={{1,2,3},{4,5,6}}; 

----

<h3 style='color:#C4C400'> 注意事項 </h3>

- 陣列的 index (索引值) 是從 0 開始到 size - 1，引用超過會報 RE or WA。
- 陣列宣告過後，不可改變大小或重新宣告。
- 如果在裡面宣告沒有給定初始值，他不會自動幫你補 0 !!!!!!
- 陣列大小大概只能開到 2e6 左右

----

<h3 style='color:#C4C400'> string </h3>

#include <algorithm> // 記得記得要加
#include <string>
#include <iostream>

using namespace std;
int main(void) {
    string s = "123456", s2 = "abcd";
    reverse(s.begin(), s.end());
    if (s > s2) cout << s << '\n';
    else cout << s2 << '\n';
}

----

<h3 style='color:#C4C400'> 酷酷的標頭檔 (懶人) </h3>

#include <bits/stdc++.h>

包含


----

<h3 style='color:#C4C400'> 輸入輸出優化 </h3>

檢定不會用到，但我提一下
請注意: 不要使用 endl 會導致使用 flush 而無法加快，請使用 '\n'

#include <bits/stdc++.h>
using namesapce std;
int main(void) {
    ios::sync_with_stdio(false),cin.tie(0);
}

---

<h2 style='color:#C4C400'> 檢討題目 </h2>

----

<h3 style='color:#C4C400'> HB01 </h3>

https://ncuma-oj.math.ncu.edu.tw/problem/HB01

----

<h3 style='color:#C4C400'> 純字串寫法 </h3>

 	int a, b, c;
 	cin >> a >> b >> c;
    // 自己寫轉二進位，這題寫過。
 	string la = two(a), lb = two(b); 
 	
 	cout << la << " " << lb << '\n';
 	for (int i = 8 - c ; i < 8 ; i++) {
 	    char ch = la[i];
 	    la[i] = lb[i];
 	    lb[i] = ch;
 	}
 	cout << la << " " << lb << '\n';

----

<h3 style='color:#C4C400'> 用位元運算 </h3>

int s1, s1, D;
cin >> s1 >> s2 >> D;
// 自己寫轉二進位，這題寫過。
cout << two(a) << " " << two(a) << "\n";

int ind_copy = s1;
// 交叉感染，使用位元運算轉換
s1 = ( ((s1 >> D) << D) | ((s2 >> D) << D) ^ s2 ); 
s2 = ( ((s2 >> D) << D) |  ((ind_copy >> D) << D) ^ ind_copy ); 

cout << two(s1) << " " << two(s2) << "\n";

----

<h3 style='color:#C4C400'> HB02 </h3>

https://ncuma-oj.math.ncu.edu.tw/problem/HB02

----

int n;
string s2;
cin >> n >> s2;
string s = s2;
reverse(s2.begin(),s2.end());
if (s < s2) 
  cout << ((n % 2 == 0) ? s : (s + s2)) << endl;
else if (s > s2)
  cout << ((n % 2 != 0) ? s2 : (s2 + s)) << endl;
else
  cout << s2 << endl;

----

<h3 style='color:#C4C400'> HB03 </h3>

https://ncuma-oj.math.ncu.edu.tw/problem/HB03

----

// 輸入以及 cnt判斷有幾個 1 
int now_cnt = 0, ans = 0;
while (now_cnt < cnt) {
    ans ++;
    int next_y = 0;
    for (int x = 0 ; x < n ; x++) {
        for (int y =  next_y ; y < m ; y++) {
            if (a[x][y] == 1) {
                next_y = y;
                now_cnt ++;
                a[x][y] = 0;
            }
        }
    }
}
cout << ans << '\n';

---

<h2 style='color:#C4C400'> 前綴和 </h2>

(Partial sum)

----

Partial sum 數列前 k 項和。

給定一個數列$(a_i)_{i\in \mathbb{N}}$
定義 $S_k = \sum^k_{i=1}{a_i}$
則數列在區間 [a b] 的值為 $S_b - S_{a-1}$

----

<h3 style='color:#C4C400'> 要做什麼?? </h3>

當一個問題詢問很多關於區間的問題，如果直接算

for (int i = 0 ; i < n ; i++) {
    cin >> a >> b;
    int ans = 0;
    for (int j = a ; j <= b ; j++) {
        ans += arr[j];
    }
    cout << ans << '\n';
}

----

<h3 style='color:#C4C400'> 當詢問次數很多 </h3>

則每次都需要花費區間 b - a + 1 這麼多次，假設每次都是問 1 ~ n 就需要花費 n 次，加上詢問次數 Q 這樣總共需要 Qn 次。

但是如果使用前綴和，我們需要花 n 次來建立 partial sum 陣列，但是我們每次詢問都只要花費一次減法 $S_b - S_{a-1}$ 就好了。
所以這樣總共只需要 q + n 次

----

<h3 style='color:#C4C400'> 注意 </h3>

因為 $S_b - S_{a-1}$ 我們在建造 partail sum 需要 index 從 1 開始，不然會跑到 -1 陣列會出事。

// input arr[n]
int p_sum[n+5] = {0}; // 多 + 幾個
for (int i = 0 ; i < n ; i++) {
    // 注意這邊我們讓 p_sum 從 i + 1 開始
    p_sum[i+1] = p_sum[i] + arr[i]; 
}
for (int i = 0 ; i < q ; i++) {
    cin >> a >> b; // 如果詢問是從 1 ~ n 如果不是記得 + 1
    cout << "區間和為" << p_sum[b] - p_sum[a-1] << endl;
    // cout << "區間和為" << p_sum[b+1] - p_sum[a] << endl; 
}

----

<h3 style='color:#C4C400'> 練習 </h3>

- C001

----


---

<h2 style='color:#C4C400'> function </h2>

----

<h3 style='color:#C4C400'> 例子 </h3>

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

void hello() {
    cout << "hello world\n";
}

int main(void) {
    hello();
}

----

<h3 style='color:#C4C400'> 引入變數 </h3>

void two_sum (int a, int b) {
    cout << a + b << '\n';
}
int main(void) {
    int x1, x2;
    cin >> x1 >> x2;
    two_sum (a, b);
}

----

<h3 style='color:#C4C400'> 回傳不同型態 </h3>

return

- void 不回傳
- int\char\string .... 回傳該型態

void nothing() {
    cout << "nothing" << '\n';
    return;
}

int two_sum (int a, int b) {
    return a + b;
}

int main(void) {
    int x1, x2;
    cin >> x1 >> x2;
    cout << two_sum(x1,x2) << '\n';
    nothing();
}

----

<h3 style='color:#C4C400'> 函式的呼叫 </h3>

int two_sum (int a, int b) {
    return a + b;
}

int main(void) {
    cout << two_sum(5,3);
}

----

<h3 style='color:#C4C400'> 前後定義的問題 </h3>

int main(void) {
    int x1, x2;
    cin >> x1 >> x2;
    cout << two_sum(x1,x2);
}

int two_sum (int a, int b) {
    return a + b;
}


----

<h3 style='color:#C4C400'> 解決方法 </h3>

- 定義在前面
- 跟變數一樣 先宣告

int two_sum (int a, int b);

int main(void) {
    int x1, x2;
    cin >> x1 >> x2;
    cout << two_sum(x1,x2);
}

int two_sum (int a, int b) {
    return a + b;
}

----

<h3 style='color:#C4C400'> 我喜歡的寫法 </h3>

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

void solve() {
    // do
}

int main(void) {
    int t = 1;
    // cin >> t;
    while (t--) solve();
}

----

<h3 style='color:#C4C400'> 我喜歡的寫法 EOF 版本 </h3>

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

void solve(int t) {
    // do
}

int main(void) {
    int t; // 看題目輸入什麼型態
    while (cin >> t) solve(t);
}

----

<h3 style='color:#C4C400'> why </h3>

- 假設今天我們在好幾層迴圈的時候，得到答案想要離開 我們可能需要這樣寫

bool check = false;
for (int i = 0 ; i < n ; i++) {
    for (int j = 0 ; j < m ; j++) {
        for (int k = 0 ; k < p ; k++) {
            if (...) {
                cout << ans << '\n';
                check = true;
                break;
            }
        }
        if (check) break;
    }
    if (check) break;
}

----

<h3 style='color:#C4C400'> 可以直接 return </h3>

for (int i = 0 ; i < n ; i++) {
    for (int j = 0 ; j < m ; j++) {
        for (int k = 0 ; k < p ; k++) {
            if (...) {
                cout << ans << '\n';
                return;
            }
        }
    }
}

---

<h2 style='color:#C4C400'> 區域、全域變數 </h2>

----

<h3 style='color:#C4C400'> 區域變數 </h3>

起始於變數宣告，結束於宣告敘述所在的區塊的大右括號。

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

int func(int a, int b) {
	int c = 5;
	return c*(a+b); // abc都屬於func的區域變數 (和main的abc不衝突)
};
                                           
int main(void){
	int a, b; //屬於main函式的區域變數
	cin >> a >> b;
	cout << func(a,b) << '\n'; 
	for (int i = 0 ; i < 3 ; i++) {
		int x; //出了for迴圈之後，x就結束了
		cin >> x;
		cout << x << '\n';
	}
}

----

<h3 style='color:#C4C400'> 全域變數 </h3>

- 宣告在所有區塊和類別之外的變數
- 不可宣告同名的全域變數
- 若沒有給定初始值，會自動給0

----

<h3 style='color:#C4C400'> 全域變數 </h3>

#include <bits/stdc++.h>
using namespace std;
int arr[10000000]; //全域變數，所以沒有給定初始值會自動給0

int main(void){
	int str[100000]; //這邊是區域變數，沒有給定初始值就不會有
}

----

<h3 style='color:#C4C400'> 注意事項 </h3>

- 定義名稱不要重複
- 陣列大小區域大概 (2e6) 全域大概可以開到 (5e7)
- 全域變數會自動給 0 但區域變數不會!!

----

<h3 style='color:#C4C400'> 練習題 </h3>

- B005
- C002

----