# 期初熱身
## [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
Sign in with Wallet
Connect another wallet