# **APCS 題解**
作者: Hank Hu
# #前言(~~作者的一些廢話~~)
紀錄於2022/4/24
這是我第一次使用HackMD，做的不好看還請見諒:3。
動機是突然想把一些APCS的題目做紀錄下來。方便自己複習，也可以提供給別人學習，寫扣的算是興趣吧。雖然我也很爛QAQ。希望對程式有興趣的人能繼續奮鬥下去。因此我把這份題解寫成類似引導的方式，希望讀到這份的人可以不要只是抄Code，而是認真理解演算法和搞懂題目。
順帶一提，會不定期更新。
還有有些內容沒更新上去的部分我會盡量快速完成，還請多多包容。ex:連結沒辦法點...。
更: 紀錄於2022/9/2，因學測緣故，沒那麼常寫code，有需要更多的題解或催更可以mail我，我會盡力的TAT。
hu.0106.text@gmail.com
:::warning
值得一提的是 : Zerojudge測資蠻弱的，所以有些Code可能沒那麼好，但在ZJ上過了。請見諒。習慣一些演算法使用1 base記得看細節。
:::
:::danger
建議在main函式中加上這行增加執行速度:
**ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);**
若加上則切忌不可以和printf和scanf混用。
題目沒有照難易度排序。有些觀念會重複提到。
建議先學習一些運算子符號ex: $"?:"$, $"<<"$ , $">>"$...。
還有了解時間複雜度基本觀念、分析。
:::
話不多說，開始吧!
# ZJ f581 圓環出口
## 1.題目敘述:
https://zerojudge.tw/ShowProblem?problemid=f581
## 2.解題想法:
1. 爆搜: 每次做任務都一個一個跑下去。但一定會吃TLE :(。
2. 優化: 只用找到每次做完任務停留的點就好，若終點為x，現在為now。
表示x-now所有經過的點數總和>=任務所需點數。
#### 問題(1):如何找到區間x-now的和。
:::success
:::spoiler Hint
\
前綴和。
[ 外部連結(英文)](https://darrenyao.com/usacobook/cpp.pdf#page=60)
第60頁，哭啊有時候點連結會跑掉。
:::
#### 問題(2):那如果需要重頭走呢? 如何解決圓環的問題?
:::success
:::spoiler Hint
\
開兩倍長度的array。(索引值)1~2n
為什麼可以這樣做呢?
因為題目提到說:點數總和不超過任務所需點數。
做完如果位置>n再回到位置-n的地方。
:::
#### 問題(3):那我要怎麼知道哪個地方要當終點呢?
::: success
::: spoiler Hint
\
二分搜。
範圍(now~now+n)
:::warning
注意範例程式碼的寫法下界需-1。
:::
## 3.程式碼範例
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = a;i<=b;i++)
using namespace std;
int dp[400010];
int p[400010];
int now = 1;
void BS(int pos, int l, int r , int v) {
while(l!=r-1) {
int m = (l+r)/2;
if(p[m]-p[pos-1]<v) l = m;
else r = m;
}
now = r;
}
void solve() {
int n,m;cin >> n >> m;
FOR(i,1,n) {
cin >> dp[i];
dp[n+i] = dp[i];
}
FOR(i,1,2*n+1) {
p[i] = p[i-1] + dp[i];
}
vector<int> v(m);
FOR(i,0,m-1) cin >> v[i];
for(int it : v) {
BS(now,now-1,now+n,it);
now++;
if(now>n) now-=n;
}
cout << now-1 << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
# ZJ e289 美麗的彩帶
## 1.題目敘述:
https://zerojudge.tw/ShowProblem?problemid=e289
## 2.解題想法:
1. 爆搜: 枚舉每個長度為m的區間，然後每次都掃過一遍看是不是有m種顏色。時間複雜度為$O(n^2)$，一定會吃TLE :(。
2. 優化: 假設我現在在$\ [l,m]$區間，下一次要檢查$\ [l+1,m+1]$區間，那我需要變更的只有，把左界l改成l+1，右界m改成m+1，意旨刪除$arr[l]$ , $arr[r]$,且更新$arr[l+1]$, $arr[r+1]$即可。
可以思考一下要如何做到存區間顏色數和更新左右界線。
::: success
::: spoiler Hint
\
Two Pointer && Map(連結是英文的)
Two Pointer([外部連結](https://darrenyao.com/usacobook/cpp.pdf#page=71))
Map([外部連結](https://darrenyao.com/usacobook/cpp.pdf#page=18))
:::
::: info
::: spoiler Solution
維護l,r，每次更新把arr[r]位置的值加到map如果map[arr[r]] == 1就顏色種類+1，當達到l ~ r區間長度為m時，把原本arr[l]的顏色刪掉，再加上arr[l+1]的顏色，假設map[arr[l]] == 0代表顏色種類-1，而arr[l+1]在做r的時候已經加過了記得不要重複加到。
:::warning
注意題目的顏色值域A~i~是到10^150^，要開string不然會超出long long int 上限。
:::
## 3.程式碼範例
::: spoiler **點擊展開Code**
``` cpp=
#include<bits/stdc++.h>
#define FOR(j,a,b) for(int j = a;j<=b;j++)
using namespace std;
void solve() {
int n,m;cin >> m >> n;
vector<string> v(n);
FOR(i,0,n-1) cin >> v[i];
map<string,int> cnt;
int l = 0,r=0,type=0,ans=0;
while(l<n&&r<n) {
if(r-l==m) {
cnt[v[l]]--;
if(cnt[v[l]]==0) type--;
l++;
}
cnt[v[r]]++;
if(cnt[v[r]] == 1) type++;
r++;
if(type==m) ans++;
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
# ZJ b967 血緣關係
## 0.前置觀念:
Tree Algorithm && DFS
[外部連結](https://www.youtube.com/watch?v=XEzd5yZLpoM&ab_channel=sprout-tw)
通常用E表示點edge
用V表示邊vertices
## 1.題目敘述:
https://zerojudge.tw/ShowProblem?problemid=b967
## 2.解題想法:
1. 爆搜: 對每個點DFS找最長距離。時間複雜度為$O((V+E)^2)$，一定吃TLE : (。
2. 優化: 會觀察到若A可以到B, B可以到C, A->C最遠距離會等於A->B的最遠距離+B->C的最遠距離。可以想想如何找到B?
註:這題是裸題所以沒有很多觀念，可以Google搜尋樹上最遠距離或是樹直徑。
:::success
::: spoiler Hint 1
\
B為樹根，且樹有一個特性，任意點都可以當根。意旨拉起任意點，都會形成一棵樹。
:::
::: info
:::spoiler Solution 1
\
樹DP，對節點找子樹最遠點和子樹第二遠點，然後一值併到根。然後輸出兩點距離即可。
:::
:::success
::: spoiler Hint 2
\
先找左邊或右邊最遠，再找對那個點來說最遠的距離。
:::
:::info
:::spoiler Solution 2
\
樹上DFS 2次，第一次找最深的點x，第二次找以x為根的最深點。
:::
## 3.程式碼範例
### (1) 樹DP版:
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define vi vector<int>
#define FOR(i,a,b) for(int i = a;i<=b;i++)
using namespace std;
const int N = 1e5+10;
vi e[N];
int d_max[N],d_sec[N],ans = 0;
void dfs(int u, int par) {
for(int chi:e[u]) {
if(chi!=par) {
dfs(chi,u);
int now = d_max[chi]+1;
if(now>d_max[u]) {
d_sec[u] = d_max[u];
d_max[u] = now;
}
else if(now>d_sec[u]){
d_sec[u] = now;
}
}
}
ans = max(ans,d_max[u]+d_sec[u]);
}
void solve(int n) {
FOR(i,1,n-1) {
int par,chi;cin >> par >> chi;
e[par].pb(chi);
e[chi].pb(par);
}
dfs(0,0);
cout << ans << '\n';
FOR(i,0,n) {
while(e[i].size()) e[i].clear();
d_max[i] = 0;
d_sec[i] = 0;
ans = 0;
}
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
while(cin >> n) solve(n);
}
```
:::
### (2) 兩次DFS版:
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define FOR(j,a,b) for(int j = a;j<=b;j++)
#define pb push_back
using namespace std;
const int N = 1e5+10;
vector<int> e[N];
int subtree[N],root = 0;
void dfs(int u, int par) {
for(int chi:e[u]) {
if(chi!=par) {
subtree[chi] = subtree[u]+1;
root = (subtree[root]>subtree[chi])?root:chi;
//上面那行看不懂可以google"?:"運算子
dfs(chi,u);
}
}
}
void solve(int n) {
FOR(i,1,n-1) {
int a,b;cin >> a >> b;
e[a].pb(b);
e[b].pb(a);
}
dfs(0,0);
FOR(i,0,n) subtree[i] = 0;
dfs(root,root);
cout << subtree[root] << '\n';
// initial
FOR(i,0,n-1) {
while(!e[i].empty()) e[i].clear();
subtree[i] = 0;
}
root = 0;
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
while(cin>>n) solve(n);
}
```
:::
# ZJ c575 基地台
## 1.題目敘述:
https://zerojudge.tw/ShowProblem?problemid=c575
## 2.解題想法:
1. 爆搜: 直徑從1開始，依序檢查每個點蓋基地台有沒有蓋到全部範圍。一定吃TLE :(。
2. 優化: 如果直徑R不行，那代表R-1一定不行，如果直徑R可以，那R+1可不可以? 答案是一定可以。所以只要找到最一開始的R，如果不行就找更大的R，可以就找更小的R。
### 問題(1): 最一開始的R要選多少。
:::success
:::spoiler Hint
\
**二分搜。**
R最小是1，最大是基地台最大的位置-最小的位置。且因為R可以放K個代表R+1也可以放<=K個，R不行放K個，那代表R-1一定不行放K個。R對K具有單調性，可以二分搜(R小則K大，R大則K小)。
:::warning
注意範例程式碼的寫法下界需-1。
:::
### 問題(2): 如何知道要放多少個基地台。
:::success
::: spoiler Hint
\
**Greedy**(?)
先從最小開始放(R/2的位置)，如果現在位置>上一個放的+R，更新現在位置。代表多放一個基地台。
::: warning
註:now的位置一定要+k<第一個城市位置不然無法更新。
:::
## 3.程式碼範例
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define FOR(j,a,b) for(int j = a;j<=b;j++)
using namespace std;
vector<int> v;
int n,k;
bool check(int m) {
int now = -1e9, put = 0;
FOR(i,0,n-1) {
if(now+m>=v[i]) continue;
now = v[i];
put++;
}
return put<=k;
}
int Binary_Search(int l, int r) {
while(l!=r-1) {
int m = (l+r)/2;
if(check(m)) r = m;
else l = m;
}
return r;
}
void solve() {
cin >> n >> k;
v.resize(n);
FOR(i,0,n-1) cin >> v[i];
sort(v.begin(),v.end());
int l = 1;
int r = v[n-1] - v[0];
cout << Binary_Search(l-1,r) << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
# ZJ f315 低地距離
## 0.前置觀念:
BIT or called Fenwick Tree|| Segment Tree
當初看YT和自學的，外部連結能給的很少 QWQ。
建議先理解觀念，有些程式碼不是那麼乾淨參考就好。還有BIT要查蠻多資料才能知道怎麼寫的喔。
[推一個wiwiho的www](https://hackmd.io/@wiwiho/cp-note/%2F%40wiwiho%2FCPN-binary-indexed-tree)
[BIT](https://www.youtube.com/watch?v=CWDQJGaN1gY&ab_channel=TusharRoy-CodingMadeSimple)
[線段樹](https://www.youtube.com/watch?v=e_bK-dgPvfM) (雖然中國的用語有差異但至少是中文owo)
PS:線段樹也可以去看資訊之芽。
[線段樹(一)](https://www.youtube.com/watch?v=GLuT4zKzdjc&ab_channel=sprout-tw)
[線段樹(二)](https://www.youtube.com/watch?v=5DAIKf61xLs&ab_channel=sprout-tw)
## 1.題目敘述:
https://zerojudge.tw/ShowProblem?problemid=f315
## 2.解題想法:
1. 爆搜: 找到每個數值的區間然後跑一遍，看區間內有多少比它小的數值，但必定吃TLE : (。
2. 優化: 關鍵是我需要找到的只有在這段$[l,r]$區間比我小的值而已，所以不如初始一個數值都為0的陣列，從最小的值開始找到最大的值，然後每次找完把當前的位置更新上去。意旨當前位置的陣列值+1($arr[l]+=1$ , $arr[r]+=1$)，然後就會變成查詢區間和。
**問題(1): 我要怎麼從最小的開始放，Sort嗎?**
::: success
::: spoiler Hint
\
因為值為$1$~$n$所以可以開n長度的pair陣列，first紀錄左邊的位置，second紀錄右邊的位置。
:::
**問題(2): 查詢區間何要怎麼做呢? 用前面提到的前綴和沒辦法線性時間更新值阿，還有更好的做法嗎。**
::: success
::: spoiler Hint
這時候就該線段樹or BIT出場了!，可以做到$O(logN)$時間的查詢和更新值。前綴和查詢是$O(1)$，但更新值是$O(n)$，會TLE所以步行用。先看完前置觀念再去解題吧!。
:::
::: warning
注意要開long long int因為答案會超出int上限。
:::
:::danger
::: spoiler 一些細節
\
**BIT和線段樹各有優缺點，但通常這種同時可以用BIT和線段樹的題目，個人習慣寫BIT。因為寫BIT比刻一顆線段樹簡單很多，所需時間也少，我刻一顆線段樹大概要15 ~ 20分鐘，但是BIT只用2 ~ 3分鐘而已XD。BIT空間複雜度也比線段樹小(線段樹要開4倍)。比較不會因為題目數值範圍被卡到陣列長度uwu。**
:::
## 3.程式碼範例
### (1)線段樹版本 
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define int long long
#define FOR(j,a,b) for(int j = a;j<=b;j++)
#define F first
#define S second
using namespace std;
const int N = 2e5+10;
struct segment_tree{
int t[4*N];
int que(int ql, int qr, int l, int r, int n) {
if(ql<=l&&r<=qr) {
return t[n];
}
int m = (l+r)/2;
if(qr<=m) return que(ql,qr,l,m,n*2);
else if(ql>m) return que(ql,qr,m+1,r,n*2+1);
else return que(ql,qr,l,m,n*2) + que(ql,qr,m+1,r,n*2+1);
}
void upd(int p, int v, int l, int r, int n) {
if(l==r) {
t[n] = v;
return;
}
int m = (l+r)/2;
if(p<=m) upd(p,v,l,m,n*2);
else upd(p,v,m+1,r,n*2+1);
t[n] = t[n*2] + t[n*2+1];
}
}seg_tree;
void solve() {
int n, ans = 0;cin >> n;
pair<int,int> arr[n+2];
FOR(i,1,2*n) {
int a;cin >> a;
if(arr[a].F==0) arr[a].F=i;
else arr[a].S=i;
}
FOR(i,1,n) {
int sum = seg_tree.que(arr[i].F,arr[i].S,1,2*n,1);
ans += sum;
seg_tree.upd(arr[i].F,1,1,2*n,1);
seg_tree.upd(arr[i].S,1,1,2*n,1);
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
### (2)BIT版本 
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define FOR(j,a,b) for(int j = a;j<=b;j++)
#define int long long
#define F first
#define S second
using namespace std;
const int N = 1e5+10;
pair<int,int> arr[N];
struct bit{
int t[2*N];
void upd(int p, int v) {
for(;p<=2*N;p+=(p&-p)) t[p]+=v;
}
int query(int p) {
int res = 0;
for(;p>0;p-=(p&-p)) res+=t[p];
return res;
}
}bit;
void solve() {
int n, ans = 0;cin >> n;
FOR(i,1,2*n) {
int a;cin >> a;
if(arr[a].F==0) arr[a].F=i;
else arr[a].S=i;
}
FOR(i,1,n) {
int sum = bit.query(arr[i].S) - bit.query(arr[i].F-1);
ans += sum;
bit.upd(arr[i].F,1);
bit.upd(arr[i].S,1);
}
cout << ans << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
# ZJ h084 牆上海報
## 1.題目敘述:
https://zerojudge.tw/ShowProblem?problemid=h084
## 2.解題想法:
1.觀察題目: 會發現可以貼海報的高度最高就是所有牆的裡最高的，最小則是1。所以我可以直接爆搜嗎? 答案顯然是否。因為時間複雜度會到$O(n·h_i)$
2.優化: 想一下，假設我現在檢查的高度是$H$，如果$H$不行，那$H-1$可以嗎?，$H+1$可以嗎?答案是$H+1$肯定不行，而$H-1$可能可以。那如果$H$可以，那$H-1$可以嗎?，$H+1$可以嗎?答案是$H+1$可能可以，而$H-1$肯定可以。各位可以思考一下為什麼。
**問題(1): 如何有效枚舉H高度。**
:::success
::: spoiler Hint
\
有單調性的東西，最好用的當然是二分搜!
:::
**問題(2): 如何檢查這高度能不能放。**
:::success
:::spoiler Hint
\
直接檢查就好了，看每段>=H的區間長，然後放到不能放海報為止。時間複雜度是$O(N)$，乘上二分搜時間複雜度$O(logH_i)$，總時間複雜度是$O(NlogH_i)$。並不會TLE。
:::
::: danger
::: spoiler 注意事項，ZJ卡90%再來看www。
\
這題二分搜上界要+1，會跟前面二分搜的題不一樣，算是h對k函數的小特性(?，不然答案是r的時候會出錯，輸出r-1，但在Zerojudge上會90%，測資是真的蠻弱的www。
:::
## 3.程式碼範例
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define vi vector<int>
#define all(p) p.begin(),p.end()
#define FOR(j,a,b) for(int j = a;j<=b;j++)
using namespace std;
const int N = 4e5+10;
vi v;
vi post;
int n,k;
bool check(int m) {
int put = 0,now = 0;
for(int i:v) {
if(i<m) {
now = 0;
continue;
}
now++;
while(put<k&&now>=post[put]) {
now-=post[put];
put++;
}
}
return put<k;
}
int BS(int l, int r) {
while(l!=r-1) {
int m = (l+r)/2;
if(check(m)) r = m;
else l = m;
}
return l;
}
void solve() {
int mxh = 0;
cin >> n >> k;
v.resize(n);
post.resize(k);
FOR(i,0,n-1) cin >> v[i],mxh = max(mxh,v[i]);
FOR(i,0,k-1) cin >> post[i];
cout << BS(1,mxh+1) << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
# ZJ g277 幸運數字
## 1.題目敘述:
https://zerojudge.tw/ShowProblem?problemid=g277
## 2.解題想法:
1.觀察: 很明顯這題就是，給定一個陣列，然後要你找區間最小值和區間和。那我們分成2部分思考。
問題(1): 如何查找區間和。
:::success
::: spoiler Hint
可以用到前面提過的前綴和的概念!
:::
問題(2): 如何查找區間最小值。
:::success
::: spoiler Hint
\
因為不會更新新的值上去，所以照小到大sort就好了!
或是也可以用一些RMQ演算法維護。
:::
::: warning
::: spoiler 一些細節。
\
記得開long long int因為前綴和可能會超出int上限!
:::
## 3.程式碼範例
::: danger
::: spoiler 一些小提醒。
\
這題重點就是**不帶修改**的查詢區間和和區間最小值。所以不要想說一定要用難的演算法。如果你不想用pair存位置，或是用線段樹寫這題。因為值域到$10^7$所以可以嘗試開一個長度$10^7$的陣列然後存每個值的位置，或是用map。用map的話時間會稍稍慢一點，但空間會小很多。
上面是Map，下面是$10^7$陣列。
:::
### **(1) Sort+前綴和版**
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define all(p) p.begin(),p.end()
#define FOR(j,a,b) for(int j = a;j<=b;j++)
#define int long long
#define F first
#define S second
using namespace std;
const int N = 3e5+2;
int pre[N];
void solve() {
int n;cin >> n;
vector<int> org(n+1);
vector<pair<int,int>> v(n+1);
FOR(i,1,n) {
cin >> v[i].F;
v[i].S = i;
org[i] = v[i].F;
}
FOR(i,1,n) pre[i] = pre[i-1] + v[i].F;
sort(all(v));
int l = 1,r = n;
FOR(i,1,n) {
if(l<=v[i].S&&v[i].S<=r) {
if(pre[r]-pre[v[i].S]<pre[v[i].S-1]-pre[l-1]) r = v[i].S-1;
else l = v[i].S+1;
}
}
cout << org[r] << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
### **(2) 線段樹版** 建議真的想不到再刻qq。
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define all(p) p.begin(),p.end()
#define FOR(j,a,b) for(int j = a;j<=b;j++)
#define int long long
#define F first
#define S second
using namespace std;
const int N = 3e5+10;
struct SegmentTree
{
int arr[N], t[4*N], s[4*N];
void build_tree(int l, int r, int n) {
if(l==r) {
t[n] = arr[l];
s[n] = arr[l];
return;
}
int m = (l+r)/2;
build_tree(l,m,2*n);
build_tree(m+1,r,2*n+1);
t[n] = t[2*n] + t[2*n+1];
s[n] = min(s[2*n],s[2*n+1]);
}
int que_sum(int ql, int qr ,int l ,int r ,int n) {
if(qr<ql) return 0;
if(ql<=l&&r<=qr) return t[n];
int m = (l+r)/2;
if(qr<=m) return que_sum(ql,qr,l,m,2*n);
else if(ql>m) return que_sum(ql,qr,m+1,r,(2*n)+1);
else return que_sum(ql,qr,l,m,2*n) + que_sum(ql,qr,m+1,r,(2*n)+1);
}
int que_min(int ql, int qr ,int l ,int r ,int n) {
if(ql<=l&&r<=qr) return s[n];
int m = (l+r)/2;
if(qr<=m) return que_min(ql,qr,l,m,2*n);
else if(ql>m) return que_min(ql,qr,m+1,r,(2*n)+1);
else return min(que_min(ql,qr,l,m,2*n),que_min(ql,qr,m+1,r,(2*n)+1));
}
}seg;
void solve() {
int n;cin >> n;
map<int,int> pos;
FOR(i,1,n) {
int x;cin >> x;
seg.arr[i] = x;
pos[x] = i;
}
seg.build_tree(1,n,1);
int l =1,r = n;
while(l!=r) {
int v = seg.que_min(l,r,1,n,1);
int p = pos[v];
int l_sum = seg.que_sum(l,p-1,1,n,1);
int r_sum = seg.que_sum(p+1,r,1,n,1);
if(l_sum>r_sum) r = p-1;
else l = p+1;
}
cout << seg.arr[l] << '\n';
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
### (3) 笛卡兒樹$O(n)$作法 (作者真的不會寫QQ)
# ZJ f608 飛黃騰達
## 0.前置觀念:
[LIS](https://web.ntnu.edu.tw/~algo/Subsequence.html#1)
## 1.題目敘述:
https://zerojudge.tw/ShowProblem?problemid=f608
## 2.解題想法:
**1.觀察性質:** 只能往右和上走，代表下次取到的珠子，x座標和y座標一定大於等於現在的x,y座標。然後能取越多越好。有沒有覺得這跟甚麼演算法很像。
:::success
:::spoiler Hint
\
沒錯就是非嚴格遞增的LIS(longest increasing subsequence)
:::
::: info
::: spoiler Solution
\
這時候你可能會問，可是題目有2個維度ㄟ?-?，那就先sort過其中一個座標，然後就可以變單維度的LIS了阿。先對x座標或y座標做sort都可以得出最佳解，這跟題目給的非嚴格遞增的性質有關，各位可以想想看為什麼。
然後這題有兩種做法，一種是開一個陣列紀錄最長LIS。另一種是用BIT維護目前數字可以接在多少數字後面。
**需要注意的是如果用第一種方法，請注意第18行，判斷是否為空的條件需要在判斷是否大於back數字的條件的前面。否則會因為vector為空出現RE。因為是非嚴格遞增，所以要用upper_bound，如果用BIT，則query要查訊自己位置而不是位置-1。**
:::
## 3.程式碼範例
### (1) LIS
::: spoiler **點擊展開Code** 
```cpp=
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = a;i<=b;i++)
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(),(x).end()
using namespace std;
void solve() {
int n;cin >> n;
vector<pair<int,int>> v;
FOR(i,0,n-1) {
int x,y;cin >> x >> y;
v.pb({x,y});
}
sort(all(v));
vector<int> lis;
FOR(i,0,n-1) {
if(lis.empty()||v[i].S>=lis.back()) lis.pb(v[i].S);
else *upper_bound(all(lis),v[i].S) = v[i].S;
}
cout << lis.size() << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
### (2) LIS(BIT) 待更
# ZJ h029(f163) 貨物分配
## 1.題目敘述:
https://zerojudge.tw/ShowProblem?problemid=h029
https://zerojudge.tw/ShowProblem?problemid=f163 (測資較強)
## 2.解題想法:
## 3.程式碼範例
::: spoiler **點擊展開Code**
```cpp=
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i = a;i<=b;i++)
using namespace std;
const int N = 1e6+10;
int w[2*N],right_node[2*N],left_node[2*N],output = 0;
void build(int now) {
if(left_node[now]!=0) build(left_node[now]);
if(right_node[now]!=0) build(right_node[now]);
w[now] += w[left_node[now]] + w[right_node[now]];
}
void put(int now ,int value) {
output = now;
if(left_node[now]!=0&&w[left_node[now]]<=w[right_node[now]]) put(left_node[now],value);
else if(right_node[now]!=0) put(right_node[now],value);
w[now] += value;
}
void solve() {
int n,m;cin >> n >> m;
vector<int> goods(m);
FOR(i,n,2*n-1) cin >> w[i];
FOR(i,0,m-1) cin >> goods[i];
FOR(i,1,n-1) {
int now,l,r;cin >> now >> l >> r;
right_node[now] = r;
left_node[now] = l;
}
build(1); // 1 base
FOR(i,0,m-1) {
put(1,goods[i]);
cout << output << ' ';
}
cout << '\n';
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
solve();
}
```
:::
Sign in with Wallet
Connect another wallet