# 資訊讀書會[0]
### 我們在幹嘛 OW0)?
`By FHVirus`
----
### 我們在幹嘛？
- 打競賽
- ~~裝弱~~
- ~~打音遊~~
- ~~吃拉麵~~
---
## 資訊競賽？
### 那是啥？能吃嗎 OW0)?
----
## 可以。
### 很好吃的。等等再解釋。
感謝 03t 沒有授權的提供梗。
----
## 有什麼比賽？
- 資訊學科能力競賽（主線１）
- 資訊奧林匹亞（主線２）
- ISSC
- NPSC
- HP Codewars (好吃支線)
- YTP 少年~~大括號換行~~圖靈計畫（超好吃支線）
- CodeForces, LeetCode 等線上比賽...
- 還有一大堆
----
## 資訊學科能力競賽（主線１）
- 今天早上的校內賽
- 十月初（吧）的北市賽
- 十一月底（吧）的全國賽
一樣感謝 03t 沒有授權的提供資料。
----
## 國際資訊奧林匹亞（主線２）
- 明年一月的海選、初選
- 大概是三月的 TOI 入營考
- 然後有 TOI 二階
- 最後是國手
- 再來就 IOI 2021 了
- ~~以上所有東西這堂的講師都沒有參與過，我弱~~
- 也有其他的奧林匹亞（ex. APIO）
----
## 其它支線
- 全部不報白不報！
- CF 能打就打！
- 記得組隊報名 HP CodeWars
---
# 一些你會用到的東西
----
## OJ 們
寫題目用的，能刷多少就刷多少
- TIOJ
- CodeForces
- OJDL
- ~~雞掰客服Kattis~~
- ~~毒瘤輸出UVa~~
----
## 學習資源
- 演算法筆記
- CF 上的 blog
- 資讀歷屆講義
- 學長
- OmeletWithoutEgg.github.io
- ~~StackOverflow~~
---
## 讀書會？
- 模擬競賽（品質待驗，~~希望不要出題者假解~~）
- 講理論之外也要實作。
以後會盡量讓大家在讀書會實作，這樣比較好找人 debug。
----
## さ！
大概介紹完了，來個隨堂小考吧 OW<)_b
----
### problems[0]
這份程式的目標是要「輸入一個整數 x，輸出 x ~ 0 的所有整數。」請問哪裡有誤？
```cpp=1
#include<iostream>
using namespace std;
int main(){
int x;
cin >> x;
while(x >= 0){
cout << x << endl;
x = x - 1;
}
return 0;
}
// 用大常輸出好不舒服
```
----
### answer[0]
x < 0 的時候會爛掉！
----
### problems[1]
這份程式的目標是要「輸入一個正整數 x，輸出費氏數列第 1 ~ x 項。」請問哪裡有誤？
```cpp=1
#include<iostream>
using namespace std;
int main(){
int x;
cin >> x;
int fibonacci[x];
for(int i = 0; i < x; ++i)
fibonacci[i] =
fibonacci[i-1] +
fibonacci[i-2]
;
for(int i = 0; i < x; ++i)
cout << fibonacci[i] << endl;
return 0;
}
// 用大常輸出好不舒服
```
----
### answer[1]
首先，Line 9 ~ 12 是沒錯的！
C++ 接受怪換行！
所以你也可以：
```cpp=1
#include<iostream>
using
namespace
std ;
int main() {
int x ;
cin >> x ;
while(x >= 0) {
cout << x << endl ;
x = x - 1 ;}
return 0 ;}
```
----
### answer[1]
答案是沒有起始狀態！
以及陣列取到負的索引值！
以上都是常見的錯誤喔～
平常要小心呢 OW0;)A
----
## 再來兩題！
會比較難一點喔 >W<)/
----
### hardProblem[0]
在c++，a, b, c, d何者運算後的結果是 3（所有數字都是 int 類別) ?
```cpp=1
int x = 5; int a = (--x*2 - 6);
int b = ((1<<31 - 1) / (1<<30 - 1) >> 1 + 2);
int c = (4 + 3 & 11 - 128 >> 5);
int d = (1 ^ 3 & 4 - 2);
// 感謝 8e7 沒有授權提供
```
----
### hardAnswer[0]
是 d 喔 OW0)_b
----
### hardProblem[1]
A, B 兩種陣列取值的方式何者正確？
```cpp=1
int a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
// A
cout << a[2];
// B
cout << 2[a];
```
----
### hardAnswer[0]
兩者皆可喔 OW0)_b
至於為什麼～～～～
----
### 最後最後...
哪個先學？
- Kosaraju / Dijkstra ?
- Fenwick Tree / Treap ?
- FFT / 背包DP ?
還有，TIOJ 1818
---
# 好啦！
# 正式開始上課囉！
---
## 基礎題目以及複雜度
不包含離散數學，請安心食用。
----
### 簡單題
輸入一個正整數 $n$
以及一個長度為 $n$ 的正整數序列 $a$
求 $max\{a_1, a_2, ... a_n\}$
----
### 很簡單吧！
整個跑一次，邊跑邊紀錄最大值⋯⋯
```cpp=1
int n;
cin >> n;
int a[n];
for(int i = 0; i < n; ++i)
cin >> a[i];
int mx = 0;
for(int i = 0; i < n; ++i)
mx = max(mx, a[i]);
cout << mx << endl;
```
----
### 「你知道你有多高嗎？」——某個很好的地科老師
同理，「你知道你的程式理論上多快嗎？」
或是，「你知道要怎麼表示你的程式理論上多快嗎？」
----
### $ザ。BIG\ O。ノテション！$
答案是—— $BIG\ O()$ 函數！
$O()$ 可以用來表示
「隨著題目給訂的數字成長，
程式（理論上）要跑的時間會怎麼成長。」
----
### $ザ。BIG\ O。ノテション！$
例題中，
程式要跑的時間（理論上）會隨著 $n$ 線性成長，
$RunTime \propto n$，
所以複雜度就是 $O(n)$ ！
----
### 沒那麼簡單題
輸入兩個正整數 $n, k$
以及一個長度為 $n$ 的正整數序列 $a$
求有多少組 $(i, j)$
使得 $a_i + a_j == k$
----
### ナイーブ
```cpp=1
int n, k;
cin >> n >> k;
int a[n], ans = 0;
for(int i = 0; i < n; ++i)
cin >> a[i];
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
if(a[i] + a[j] == k)
ans = ans + 1;
cout << ans << endl;
```
----
### $ザ。BIG\ O。ノテション！$
剛剛的複雜度是多少呢？
對每一個 $i$ 會跑所有的 $j$ 共 $n$ 個，
又有 $n$ 個 $i$ ......
所以，複雜度就是 $O(n*n) = O(n^2)$ ！
----
### My Code Runs
### As Slow As a
## turTLE
`要怎麼知道時間會不會爆掉呢？`
----
把題目的 $n$ 範圍帶進
你剛剛得到的 $O(f(n))$，
就會得到一個數字，
代表電腦（理論上）要跑的步驟數量級。
----
正常的 OJ 每秒可以跑 $10^8$ ，
所以再看看 Time Limit 就知道會不會過囉！
----
不過有時候你的複雜度是好的，
但還是 TLE 了 QWQ
這種情況原因有兩種：
- 你~~品庠~~寫錯了
- 你的「常數」太大了
----
### 常數？
如果說複雜度代表你要跑幾個步驟，
那常數就代表你每個步驟要執行多久，
實際執行時間差不多就是「複雜度*常數」。
遇到常數過大 TLE 的時候：
- 換一種演算法
- ~~找 FHVirus~~
----
### 回到例題
輸入兩個正整數 $n, k$
以及一個長度為 $n$ 的正整數序列 $a$
求有多少組 $(i, j)$
使得 $a_i + a_j == k$
### $n \leq 10^3$
----
用剛剛的方法估估看⋯⋯
$O(n^2) \approx 10^6 < 10^8$
可以過！
----
如果⋯⋯
~~兒童劇團~~
### $n \leq 10^6,\ 0 \leq a_i\ ,\ k \leq 5*10^5$
----
再估估看⋯⋯
$O(n^2) \approx 10^{12} > 10^8$
不會過 QWQ
----
### 怎麼辦？
這是本學期第一個難題呦。
解決了之後才正式開始呦。
----
### 解
```cpp=1
#include<iostream>
using namespace std;
const int N = 1e6;
int n, k, a[N], cnt[N+1], ans;
int main(){
cin >> n >> k;
for(int i = 0; i < n; ++i){
cin >> a[i];
cnt[a[i]]++;
}
for(int i = 0; i < n; ++i){
ans += cnt[k - a[i]];
}
cout << ans << endl;
}
```
---
今天要講的是⋯⋯
## \基礎STL/
---
## Vector
好東西
---
## vector 是啥？
- 長度不定的陣列
- 可以從後面拿掉東西
- 做一些神奇的操作
- 空間有時小一點
----
```cpp=1
#include<vector>
using namespace std;
vector<int> a;
vector<int> b(10);
vector<int> c(10, 7122);
```
----
```cpp=1
int n;
vector<int> a;
cin >> n;
a.resize(n);
for(int i = 0; i < n; ++i)
cin >> a[i];
```
----
```cpp=1
int n, in;
vector<int> a;
for(int i = 0; i < n; ++i){
cin >> in;
a.push_back(in);
}
```
----
```cpp=1
vector<int> a;
a.empty();
a.size();
a.push_back();
a.pop_back();
```
----
```cpp=1
for(int i = 0; i < a.size(); ++i)
cout << a[i] << ' ';
for(int i: a)
cout << i << ' ';
```
---
## Pair
\在一起/\在一起/\在一起/
----
```cpp=1
#include<utility>
pair<int, int> p;
p = {1, 2};
pair<int, char> pic;
pic = {7122, 'c'};
```
----
這可以幹嘛？
存二維座標
---
## Sort
乖乖排好～～
----
```cpp=1
int a[10] = {9, 1, 6, 3, 7, 2, 8, 5, 4, 0};
sort(a, a + 10);
for(int i = 0; i < 10; ++i)
cout << a[i] << ' ';
// 0 1 2 3 4 5 6 7 8 9
```
----
如果要反過來排，怎麼辦？
----
```cpp=1
bool cmp(int a, int b){
return a > b;
}
int a[10] = {9, 1, 6, 3, 7, 2, 8, 5, 4, 0};
sort(a, a + 10, cmp);
for(int i = 0; i < 10; ++i)
cout << a[i] << ' ';
// 9 8 7 6 5 4 3 2 1 0
```
{"metaMigratedAt":"2023-06-15T12:26:32.071Z","metaMigratedFrom":"YAML","title":"資訊讀書會[0]","breaks":true,"slideOptions":"{\"theme\":\"white\"}","contributors":"[{\"id\":\"04d32f9a-57cc-45cd-8549-086ea8ee6d8a\",\"add\":6312,\"del\":185}]"}