---
# System prepended metadata

title: 期初熱身

---

# 期初熱身

## [pA. 三角形](https://codeforces.com/group/fvYhunqegc/contest/317604/problem/A)
::: spoiler 想法
兩邊長的和不大於第三邊
:::
::: spoiler AC code
時間複雜度：$O(t)$
``` cpp= 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        int a, b, c;
        cin >> a >> b >> c;
        if(a < b + c && b < a + c && c < a + b) {
            cout << "YES\n";
        } else {
            cout << "NO\n";
        }
    }
    
}
```
``` cpp= 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        vector<int> v(3);
        for(int &in : v) cin >> in;
        sort(v.begin(), v.end());
        cout << (v[0] + v[1] > v[2] ? "YES" : "NO") << endl;
    }
    
}
```

:::warning
可能的失誤
1. 沒有照輸出格式輸出（行尾要記得換行）
2. 判斷不夠完整
:::

## [pB. 區間和](https://codeforces.com/group/fvYhunqegc/contest/317604/problem/B)

:::spoiler 想法
每次詢問一個一個加起來，$a_l+a_{l+1}+...+a_{r}$
:::
:::spoiler subtask 1
``` cpp=
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 50;
int a[maxn];
int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    // 詢問 O(nQ)
    int q; 
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        int sum = 0;
        for(int i = l; i <= r; i++) sum += a[i];
        cout << sum << endl;
    }
}
```
每次詢問時間複雜度：$O(n)$
詢問q次時間複雜度:$O(nQ)$
- subtask 1範圍
    $1 ≤ n ≤ 10^4$
    $1 ≤ Q ≤ 10^4$
    $n \times Q=10^{8}$，一秒可以執行完。
- subtask 2範圍
    $1 ≤ n ≤ 2 × 10^5$
    $1 ≤ Q ≤ 2 × 10^5$
    $n \times Q=10^{10}$，一秒跑步完，會超時。
:::



:::spoiler 想法2
1. 預處理前綴和，減少每次查詢需要的計算。
2. 開long long!!!
:::
:::spoiler AC code
``` cpp=
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 50;
int a[maxn];
long long prefix_sum[maxn] = {};

int main() {
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    for(int i = 1; i <= n; i++) prefix_sum[i] = prefix_sum[i-1] + a[i];
    
    // 詢問
    int q; 
    cin >> q;
    while(q--) {
        int l, r;
        cin >> l >> r;
        cout << prefix_sum[r] - prefix_sum[l-1] << endl;
    }
}
```
預處理前綴和時間複雜度：$O(n)$
每次詢問時間複雜度：$O(1)$
詢問q次時間複雜度：$O(Q)$
總時間複雜度：$O(n+Q)$
:::warning
真的很多人沒有開long long，一開始我驗題也忘記了...
考慮$2 × 10^5$大小的陣列，裡面每個數字都是$10^6$，詢問全部的總和會等於$2 \times 10^{11} > 2 \times 10^9$，超出int儲存範圍。

一個小作弊的方法會是：
```cpp=
#include <bits/stdc++.h>
using namespace stdl

#define int long long
signed main() { // main回傳型別不能是long long，這邊改成signed

}
```
這樣就可以把所有int變成long long了。
:::

## [pC. 最小公倍數(LCM)](https://codeforces.com/group/fvYhunqegc/contest/317604/problem/C)
:::spoiler 想法
$a, b$的最小公倍數＝$a \times b$ / ($a, b$的最大公因數)
$lcm(a, b)$＝$\frac{a \times b}{gcd(a, b)}$
:::
:::spoiler AC code
### 遞迴版本
``` cpp=
#include <bits/stdc++.h>
using namespace std;

#define int long long

int gcd(int a, int b) { 
    if (a == 0) return b; 
    else return gcd(b % a, a); 
}

signed main() {
    int t;
    cin >> t;
    while(t--) {
        int a, b;
        cin >> a >> b;
        cout << a * b / gcd(a, b) << endl;
    }
}
```

### 迴圈版本
``` cpp=
#include <bits/stdc++.h>
using namespace std;

#define int long long

int gcd(int a, int b) {
    while (b) {
        a %= b;
        swap (a, b);
    }
    return a;
}

signed main() {
    int t;
    cin >> t;
    while(t--) {
        int a, b;
        cin >> a >> b;
        cout << a * b / gcd(a, b);
    }
}
```

### 內建函式版本
``` cpp=
#include <bits/stdc++.h>
using namespace std;

#define int long long

signed main() {
    int t;
    cin >> t;
    while(t--) {
        int a, b;
        cin >> a >> b;
        cout << a * b / __gcd(a, b);
    }
}
```
:::warning
一樣記得要開long long!!!

:::

## [pD. 求求爬樓梯](https://codeforces.com/group/fvYhunqegc/contest/317604/problem/D)
:::spoiler 想法
發現關係式
$a_0=1$
$a_1=1$
$a_n=a_{n-1}+a_{n-2}$, for all $n > 1$
:::
:::spoiler subtask 1
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;

int f(int x) {
    if(x == 0 || x == 1) return 1;
    return (f(x - 1) + f(x - 2)) % mod;
}
int main() {
    int t;
    cin >> t;
    while(t--) {
        int x;
        cin >> x;
        cout << f(x) << endl;
    }
}
```
每次詢問時間複雜度：$O(2^n)$
總時間複雜度：$O(2^n t)$

:::

:::spoiler subtast 2
改用buttom up的方式求答案。
```cpp=
#include <bits/stdc++.h>
using namespace std;
 
const int mod = 1e9 + 7;
 
void solve() {
	int n;
	cin >> n;
	vector<int> v(n+1, 1);
	for(int i = 2; i <= n; i++) v[i] = (v[i-1]+v[i-2]) % mod;
	cout << v[n] << endl;
}
 
signed main() {
	int t;
	cin >> t;
	while(t--) solve();
} 
```
每次詢問時間複雜度：$O(n)$
總時間複雜度：$O(n t)$
:::
:::spoiler subtast 3

### top-down 記憶化搜尋
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int maxn = 1e6 + 60;

vector<int> dp(maxn, -1);

int f(int x) {
    if(dp[x] != -1) return dp[x];
    
    return dp[x] = (f(x - 1) + f(x - 2)) % mod;
}
signed main() {
    dp[0] = dp[1] = 1;
    
    int t;
    cin >> t;
    while(t--) {
        int x;
        cin >> x;
        cout << f(x) << endl;
    }
}
```
### buttom-up 先打好表
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int mod = 1e9 + 7;
const int maxn = 1e6 + 50;

vector<int> v(maxn, 1);
void init() {
    for(int i = 2; i < maxn; i++) {
        v[i] = (v[i-1]+v[i-2]) % mod;
    }
}

signed main() {
	init(); 
    
	int t;
	cin >> t;
	while(t--) {
		int in;
		cin >> in;
		cout << v[in] << endl;
	}
} 
```
建表時間複雜度：$O(n)$
查詢時間複雜度：$O(1)$
總時間複雜度：$O(n)$
:::

:::spoiler AC code
矩陣快速幂!!!
還記得$2^n$可以用分治法做到$O(logn)$嗎？
費氏數列可以轉換成這個形式：
$f(n)=f(n-1)+f(n-2)$
$f(n-1)=f(n-1)$

寫成矩陣的形式：
$\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix}=\begin{bmatrix} 1&1\\1&0 \end{bmatrix}\begin{bmatrix} f(n-1) \\ f(n-2) \end{bmatrix}$

也就是說：
$\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix}=\begin{bmatrix} 1&1\\1&0 \end{bmatrix}\begin{bmatrix} f(n-1) \\ f(n-2) \end{bmatrix}$
$\begin{bmatrix} f(n-1) \\ f(n-2) \end{bmatrix}=\begin{bmatrix} 1&1\\1&0 \end{bmatrix}\begin{bmatrix} f(n-2) \\ f(n-3) \end{bmatrix}$

$\begin{bmatrix} f(n) \\ f(n-1) \end{bmatrix}=\begin{bmatrix} 1&1\\1&0 \end{bmatrix}^{n-1}\begin{bmatrix} f(1) \\ f(0) \end{bmatrix}=\begin{bmatrix} 1&1\\1&0 \end{bmatrix}^{n-1}\begin{bmatrix} 1 \\ 1 \end{bmatrix}$

這個東西$\begin{bmatrix} 1&1\\1&0 \end{bmatrix}^{n-1}$我們就可以用快速幂的方式（也就是計算$2^n$的方式）算出來，就可以在$O(logn)$求出$f(n)$的值了。
```cpp=
// code from chshsaber(modify by rorarola)
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int mod = 1e9+7;

struct matrix{	
	ll arr[3][3];
	void Clear() {
		memset(arr, 0, sizeof(arr));
	}
	void init() {
		Clear();
		for(int i=1;i<=2;i++) {
			arr[i][i] = 1;
		}
	}
	void one() {
		arr[1][1] = 1; arr[1][2] = 1;
		arr[2][1] = 1; arr[2][2] = 0;
	}
};
matrix pow(matrix a,matrix b) {
	matrix tmp;
	tmp.Clear();
	for(int i=1; i<=2; i++) {
		for(int j=1; j<=2; j++) {
			for(int k=1; k<=2; k++) {
				tmp.arr[i][j] = (tmp.arr[i][j] + a.arr[i][k] * b.arr[k][j]) % mod;
			}
		}
	}
	return tmp;
}
matrix fast_pow(int k) {
	matrix tmp, A;
	A.one();
	tmp.init();
	while(k) {
		if(k & 1) 
			tmp = pow(tmp , A);
		A = pow(A ,A);
		k = (k>>1);
	}
	return tmp;
}
int main(){
	int T;
	cin>>T;
	while(T--){
		int k;
		cin >> k;
		matrix fin = fast_pow(k-1);
		cout << (fin.arr[1][1] + fin.arr[1][2]) % mod << "\n"; 
	}
}
```
:::

## [pE. 旅遊](https://codeforces.com/group/fvYhunqegc/contest/317604/problem/E)

:::spoiler 想法
從一開始的所在的城市開始進行dfs遍歷，如果邊的權重>k就不繼續向下走訪
:::
:::spoiler subtask 1
用二維陣列儲圖
:::
:::spoiler AC code
```cpp=
// code from chshsaber(modify by rorarola)
#include <bits/stdc++.h>
using namespace std;

#define pb push_back
#define X first
#define Y second

const int maxn=3e5+5;
 
vector<pair<int, int> > G[maxn];
bool visit[maxn];
int k,ans=0;
 
void dfs(int now){
	for(auto v:G[now]){
		if( (!visit[v.X]) && k>=v.Y){
			visit[v.X]=1;
			ans++;
			dfs(v.X);
		}
	} 
}
 
signed main(){
	int n,m,x;
	cin>>n>>m;
	while(m--){
		int a,b,c;
		cin>>a>>b>>c;
		G[a].pb({b,c});
		G[b].pb({a,c});
	}
	
	cin>>x>>k;
	visit[x]=1;
	ans++;
	dfs(x);
	
	cout<<ans<<"\n";
}
```
:::warning
有些人只差一點點，比如說題目是給1-index，寫的時候沒注意到寫成0-index了。
[線上畫圖的好工具](https://csacademy.com/app/graph_editor/)
:::

## [pF. 區間Max](https://codeforces.com/group/fvYhunqegc/contest/317604/problem/F)
:::spoiler 想法
Naïve想法：
每次詢問區間最大值遍歷一次找答案
:::
:::spoiler subtask 1
```cpp=
#include <bits/stdc++.h>
using namespace std;
 
signed main() {
	int n;
	cin >> n;
	vector<int> v(n+1);
	for(int i = 1; i <= n; i++) cin >> v[i];
	int q;
	cin >> q;
	while(q--) {
		int cmd, l, r;
		cin >> cmd;
		if(cmd == 1) {
			cin >> l >> r;
			cout << *max_element(v.begin()+l, v.begin()+r+1) << endl;
		} else {
			int idx, val;
			cin >> idx >> val;
			v[idx] = val;
		}
	}
	
} 
```
:::

:::spoiler AC code
### 根號算法
```cpp=
#include <bits/stdc++.h>
using namespace std;

const int maxn = 3e5 + 50;
constexpr int len = sqrt(maxn) + 1;
vector<int> a(maxn), b(maxn);

int max_v(int l, int r, vector<int> &v) {
    return *max_element(v.begin() + l, v.begin() + r);
}

void update(int idx, int val) {
	a[idx] = val;
    int c_idx = idx / len;
	b[c_idx] = max_v(c_idx * len, (c_idx + 1) * len, a);
} 

int query(int l, int r) {
    int c_l = l / len, c_r = r / len;
    if (r - l + 1 <= len * 2) { // 距離比兩格還小
        return max_v(l, r+1, a);
    }
    else {
        /*
        [------ c_l -----][-----c_l+1-----][][][][][-----c_r---------]
        [. . . l, l+r . .][(c_l+1)*len . .][][][][][c_r*len . . r . .]
        */
        int seg1 = max_v(l, (c_l + 1) * len, a);
        int seg2 = max_v(c_l + 1, c_r, b);
        int seg3 = max_v(c_r * len, r + 1, a);
        return max({seg1, seg2, seg3});
    }
}

signed main() {
	ios::sync_with_stdio(0);
    cin.tie(0);
	int n;
	cin >> n;
	
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		update(i, a[i]);
	}
	
	int q;
	cin >> q;
	while(q--) {
		int cmd;
		cin >> cmd;
		if(cmd == 1) {
            int l, r;
			cin >> l >> r;
			cout << query(l, r) << '\n';
		} else {
			int idx, val;
			cin >> idx >> val;
			update(idx, val);
			
		}
	}
	
} 
```
更新時間複雜度：$O(\sqrt{n})$
查詢時間複雜度：$O(\sqrt{n})$
總時間複雜度：$O((n+t)\sqrt{n})$

### 線段樹
```cpp=
// code from chzhong
#include<bits/stdc++.h>
using namespace std;
#define IOS {ios::sync_with_stdio(false); cin.tie(0);}
#define int long long

struct S_T{
	int _tree[1200005] = {};
	
	void update(int pos, int l, int r, int idx, int val){
		if(l == r) _tree[pos] = val;
		else{
			int m = (l + r) >> 1;
			if(idx <= m) update(pos * 2, l, m, idx, val);
			else update (pos * 2 + 1, m + 1, r, idx, val);
			_tree[pos] = max(_tree[pos * 2], _tree[pos * 2 + 1]);
		}
	}
	
	int find_max(int pos, int l, int r, int ask_l, int ask_r){
		if(ask_l <= l && r <= ask_r) return _tree[pos];
		int m = (l + r) >> 1, max_num = 0;
		if(ask_l <= m) max_num = max(max_num, find_max(pos * 2, l, m, ask_l, ask_r));
		if(m + 1 <= ask_r) max_num = max(max_num, find_max(pos * 2 + 1, m + 1, r, ask_l, ask_r));
		return max_num;
	}
}tree;

signed main(){
	IOS;
	int n, t, a, b, c, k;
	cin >> n;
	for(int i = 1; i <= n; i++){
		cin >> k;
		tree.update(1, 1, n, i, k);
	}
	cin >> t;
	while(t--){
		cin >> a >> b >> c;
		if(a == 1){
			cout << tree.find_max(1, 1, n, b, c) << endl;
		}
		else if(a == 2){
			tree.update(1, 1, n, b, c);
		}
	}
}

```
更新時間複雜度：$O(logn)$
查詢時間複雜度：$O(logn)$
總時間複雜度：$O((n+t)logn)$

:::warning
教線段樹的時候忘記講到，線段樹的記憶體要開陣列大小的4倍大，不知道為什麼再找人（比如說我）問一下。
:::
## [pG. 疫情](https://codeforces.com/group/fvYhunqegc/contest/317604/problem/G)
:::spoiler 想法
一層一層的擴散，正好是bfs的概念。
:::

:::spoiler AC code
```cpp=
// code from chshsaber
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define X first
#define Y second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define All(x) x.begin() , x.end()
#define mem(aa,x) memset(aa,x,sizeof aa)
#define pb push_back
#define lower_bit(i) i&(-i)
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
const int maxn=3e5+5;
 
vi G[maxn];
int ans[maxn];
 
main(){IOS
	int n,m,k;
	queue<int> q;
	cin>>n>>m>>k;
	
	while(m--){
		int a,b;
		cin>>a>>b;
		G[a].pb(b);
		G[b].pb(a);
	} 
	mem(ans,-1);
	while(k--){
		int num;
		cin>>num;
		ans[num]=0;
		q.push(num);
	}
	
	while(q.size()){
		int now=q.front();
		q.pop();
		for(auto v:G[now]){
			if(ans[v]==-1){
				ans[v]=ans[now]+1;
				q.push(v);
			}
		}
	}
	
	rep(i,1,n) cout<<ans[i]<<" ";
	cout<<"\n";
}
```
時間複雜度：每個點被走訪到就不會再走訪第二次了，所以會是$O(n)$

## [pH. N元方程式](https://codeforces.com/group/vE9XxvRczp/contest/315272/problem/pH)

:::spoiler 想法
看到這個題目，可以聯想到上課講過的硬幣問題，忘記的再去翻一下講義呦～
:::
:::spoiler subtask 1
直接枚舉
```cpp=
// code from no_ideas
#include <iostream>
using namespace std;
int main(){
	long long int t, k, tmp, count;
	cin>>t;
	while(t--){
		count = 0;
		cin>>k;
		tmp = k;
		for(int i=0; i<k+1; i++)
			for(int j=0; j<k/13+1; j++)
				for(int l=0; l<k/43+1; l++)
					for(int m=0; m<k/139+1; m++)
						for(int n=0; n<k/260+1; n++)
							for(int o=0; o<k/1309+1; o++)
								for(int p=0; p<k/2597+1; p++)
									if(tmp - p*2597 - o*1309 - n*260 - m*139 - l*43 - j*13 - i == 0)
										count++;
		cout<<count<<endl;
	}
	return 0;
}
時間複雜度：這邊可以直接用手算會枚舉多少次。
```
:::
:::spoiler subtask 2
有用到動態規劃，可惜忘記打表
```cpp=
// code from bonginn
// code from bonginn
#include <iostream>  
using namespace std;  
  
int main()  
{  
    int n;  
    cin >> n;  
    int a[7] = {1,13,43,139,260,1309,2597};  
    int c;
    while(n--){
        long long b[300005] = {0};  
        b[0] = 1;
        cin >> c;
        for(int i=0;i<7;i++)
            for(int j=a[i];j<=c;j++)  
                b[j] += b[j-a[i]];  
        cout << b[c] << "\n";
    } 
    
 }  

```
時間複雜度：O(kt)
:::
:::spoiler AC code
```cpp=
// code from chzhong
#include<bits/stdc++.h>
using namespace std;
#define IOS {ios::sync_with_stdio(false); cin.tie(0);}
#define int long long
 
int x[7] = {1, 13, 43, 139, 260, 1309, 2597};
int t, h, a[8][300005] = {};
 
signed main(){
    IOS;
    for(int i = 1; i <= 7; i++){
        for(int j = 1; j <= 300000; j++){
            if(x[i - 1] <= j){
                if(j == x[i - 1]) a[i][j] = 1;
                a[i][j] += a[i][j - x[i - 1]] + a[i - 1][j];
            }
            else a[i][j] = a[i - 1][j];
        }
    }
    cin >> t;
    while(t--){
        cin >> h;
        cout << a[7][h] << endl;
    }
}

```
時間複雜度：O(k+t)
:::

## [pH. N元方程式](https://codeforces.com/group/fvYhunqegc/contest/317604/problem/H)
:::spoiler 題解
參考dp，背包問題的部分。
:::

---
總結：
謝謝楊秉宇幫忙出題，他好電orz