---
tags: 進階班
---

# 競程觀念(技巧)

## 前言

在打比賽的時候，以下小技巧可以讓你的成績更好喔！

---

## 組隊比賽的成員

通常都是三人一隊，你需要：

1. **一個程式設計師**

很明顯吧，各位打的是程式比賽欸，他必須要有以下能力：

不管他的隊友用人類語言講了甚麼，他都必須把它轉成程式。

e.g. 我要三層迴圈，而且有時候要從第一層然後直接跳到第三層，

第二層不能執行......

類似這種無理的要求，程式設計師都要寫出來。

2. **一個數學家**

舉凡時間複雜度、數論都必須用到數學家，

通常一場比賽都會有一題數論題，

而數學家就把所有比賽時間砸去那題就對了！

砸出來，他就是這場比賽的 MVP！

3. **一個靈媒**

講得「道地」一點，就是一個乩童

他必須去解動態規劃的題目，

想出來，把方法告訴程式設計師，

他就是這場比賽的 MVP！

\
如果數學家或靈媒沒解出任何題目，**沒關係，這很正常**

而程式設計師就要聽著隊友無理的要求寫程式就對了，還要去解各類演算法題

當然，如果程式設計師解出了很多演算法題，他也可以成為這場比賽的 MVP。

---

## 水題的特別策略

通常一場比賽會有一題水題，

所有隊員應該賽前先分配好誰要「看」哪幾題的題敘，

看到水題的那一刻，請隊中解水題最快的人來解

(如果因為全場都只會一題，這時候比 `penalty`，你們這隊就會贏)

### 實用技巧：尾刀

在高強度的程式比賽中，通常你是沒辦法搶首殺的，

而且題目都不是裸題，因此有時候很難判斷哪題很水。

這時可以跟著計分板前排的人解題，因為通常他們解出的第一題都比較水，甚至是全場最水。

這個技巧不只用在第一題，到第二題、第三題通常都有用

但如果真的卡太久或是沒想法，那還是先挖別題試解吧。

---

## 時間複雜度

當你看到一個題目，除了算法寫對，你必須計算會不會 `TLE`。

像是 `sort` 的題目用 `bubble sort` 通常都不會過。(時間複雜度為$O(N^2)$)

通常需要 $O(NlgN)$ 的算法，例如內建 `sort`。

### 怎麼算時間複雜度？？？

1. 迴圈

多層迴圈，把你每個迴圈跑的次數乘起來就對了

2. 很奇怪的遞迴法

試著想：它比較接近哪一種跑法？

二分法 $\rightarrow O(lgN)$

線性 $\rightarrow O(N)$

費式數列 $\rightarrow O(\phi^N)$ ($\phi = \cfrac {1+\sqrt{5}}{2}$，黃金比例)

3. 其他

通常只會出現 $O(\sqrt{n}), O(\ln n)$，想想看比較像哪種

\
太難算的就不勉強了，請估算 :poop: (e.g. 建質數表的複雜度)，不然就背起來!!!

\
在算完這些複雜度後，請把變數全都帶進去，計算程式最多大約要跑幾次，

通常時限一秒大約可以換算成 $3\times 10^8$ 次運算

\
p.s. 有時基於常數，運算速度可能比你想像中還慢，因此以 $10^8$ 以內當作一個好標準

各位自己在解題網站出題的時候，拜託，時限請盡量壓超過：標程時間 + $max(0.3s,$ 標程時間 $\times 0.5)$，避免被卡常數的問題

---

## IO優化

很多種，記以下這種就好

`cin.tie(nullptr), ios_base::sync_with_stdio(false);`

---

## 寫更簡潔的程式

### define

#define all(x) x.begin(), x.end();
sort(all(vec)); // sort all the vector

### using

using LL = long long;
LL n; //n is the long long type

### template

namespace abb {
using LL = long long;
template<class T> using V = vector<T>;
template<class T> using P = pair<T, T>;
template<class T> using V2d = vector<vector<T>>;
};
using namespace abb;

V<int> v; //vector<int> v;
V<string> str; //vector<string> str;
V2d<LL> vec; //vector<vector<long long>> vec;

## 黃色鴨鴨法

這是一種 `debug` 的方法

很簡單，想像你面前有一隻黃色小鴨，現在，請你一行一行地向鴨鴨解釋你的程式碼在做甚麼

聽起來很基本，但這方法可以找出大量的邏輯錯誤，

練久了很有用處喔！

例題 (求第 $n$ 項的費式數列)：

:::spoiler `code`

int main() {
	int n;
	int arr[n];
	while(cin >> n){
		arr[0] = 1, arr[1] = 1;
		for(int i = 2; i < n; i++) 
			arr[i] = arr[i - 1] + arr[i - 2];
		cout << arr[n - 1] << '\n';
	}
	return 0;
}

:::

當你很歡樂地講解給黃色鴨鴨聽，到第 $3$ 行：

欸？我的 $n$ 沒設初始值欸 $\Rightarrow$ 第一個錯誤

到第 $5$ 行時，你會發現：若 $n = 1$，那 `arr[1]` 不就 `RE` 了嗎？ $\Rightarrow$ 第二個問題

總結：黃色鴨鴨法用的熟悉可以解決很多問題，要學習跳脫主觀思考，客觀地面對你的 `code`

## 學習資料&刷題網站
https://hackmd.io/@yjk930805/share