{%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>
```cpp=
int n = 100;
for(int i = 0 ; i < n ; i++){
int x;
cin >> x;
}
```
----
<h2 style='color:#C4C400'> while </h2>
用法如下：
```cpp=
//
while (a > b) {
}
// 無窮迴圈
while (true){
}
```
----
<h3 style='color:#C4C400'> 很多條件 (continue/break) </h3>
```cpp=
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>
以下錯誤寫法
```cpp=
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>
```cpp=
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>
```cpp=
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 為止
```cpp=
int t;
cin >> t;
while (true) {
if (t == -1) break;
// do
cin >> t;
}
```
----
<h3 style='color:#C4C400'> 輸入直到 EOF </h3>
EOF = end of file
```cpp=
int t;
while (cin >> t) {
// do
}
```
----
<h3 style='color:#C4C400'> 輸出 n 個數字用空白隔開 </h3>
要求: 尾巴不能有空白
```cpp=
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>
```cpp=
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>
```cpp=
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>
陣列是可以有多個維度的，例如：
```cpp=
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>
```cpp=
#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>
```cpp=
#include <bits/stdc++.h>
```
包含
----
<h3 style='color:#C4C400'> 輸入輸出優化 </h3>
檢定不會用到，但我提一下
請注意: 不要使用 endl 會導致使用 flush 而無法加快，請使用 '\n'
```cpp=
#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>
```cpp=
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>
```cpp=
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
----
```cpp=
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
----
```cpp=
// 輸入以及 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>
當一個問題詢問很多關於區間的問題，如果直接算
```cpp=
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 陣列會出事。
```cpp=
// 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>
```cpp=
#include <bits/stdc++.h>
using namespace std;
void hello() {
cout << "hello world\n";
}
int main(void) {
hello();
}
```
----
<h3 style='color:#C4C400'> 引入變數 </h3>
```cpp=
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 .... 回傳該型態
```cpp=
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>
```cpp=
int two_sum (int a, int b) {
return a + b;
}
int main(void) {
cout << two_sum(5,3);
}
```
----
<h3 style='color:#C4C400'> 前後定義的問題 </h3>
```cpp=
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>
- 定義在前面
- 跟變數一樣 先宣告
```cpp=
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>
```cpp=
#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>
```cpp=
#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>
- 假設今天我們在好幾層迴圈的時候，得到答案想要離開 我們可能需要這樣寫
```cpp=
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>
```cpp=
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>
起始於變數宣告，結束於宣告敘述所在的區塊的大右括號。
```cpp=
#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>
```cpp=
#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
----
{"title":"C++ 基礎III + 前綴和 DFS BFS","description":"C++ 基礎III + DFS BFS","contributors":"[{\"id\":\"b4bc52a4-04a8-4c6d-920a-32b9ab31a7f9\",\"add\":12578,\"del\":2375},{\"id\":\"d5b90de4-9b8e-4a36-a782-226db16cf725\",\"add\":4,\"del\":4}]"}