C++ 基礎III

複習

for





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

while

用法如下：









// 
while (a > b) {
    
}

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

很多條件 (continue/break)





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;
}

離開當前的迴圈?

以下錯誤寫法










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;

正確寫法













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;

題目的各種輸入方式

t筆輸入











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

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

輸入直到讀到某個值

例如讀到 -1 為止







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

輸入直到 EOF

EOF = end of file




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

輸出 n 個數字用空白隔開

要求: 尾巴不能有空白











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';

陣列宣告




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個

使用








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';

多維陣列

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






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}};

注意事項

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

string











#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';
}

酷酷的標頭檔 (懶人)


#include <bits/stdc++.h>

包含

輸入輸出優化

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





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

檢討題目

HB01

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

純字串寫法












 	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';

用位元運算











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";

HB02

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;

HB03

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';

前綴和

(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}\)

要做什麼??

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








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';
}

當詢問次數很多

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

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

注意

因為 \(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; 
}

練習

C001

function

例子










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

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

int main(void) {
    hello();
}

引入變數








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

回傳不同型態

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();
}

函式的呼叫







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

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

前後定義的問題











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

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

解決方法

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











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;
}

我喜歡的寫法












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

void solve() {
    // do
}

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

我喜歡的寫法 EOF 版本











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

void solve(int t) {
    // do
}

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

why

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














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;
}

可以直接 return










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;
            }
        }
    }
}

區域、全域變數

區域變數

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


















#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';
	}
}

全域變數

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

全域變數







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

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

注意事項

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

練習題

B005
C002

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`	在筆記中貼入程式碼
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.