# 經典題目講解 & 小技巧
## 圖論
[ABC208D](https://atcoder.jp/contests/abc208/tasks/abc208_d)
```
這題乍看之下可能很floyd，但可能還是很多人不知道該怎麼做
那我們可以回來想想看floyd的原理是什麼
很簡單，最外層的迴圈代表的其實就是目前可以用到的邊的量
其實只要懂得floyd的原理就很好理解了
```
```cpp=
#include <bits/stdc++.h>
using namespace std;
const int maxn = 4e2 + 5 ;
const int mod = 1e9 + 7 ;
const int INF = 1e9 + 9 ;
const double eps = 1e-7 ;
int dp[maxn][maxn];
signed main()
{
int n,m,ans=0;
cin>>n>>m;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
dp[i][j]=INF;
}
}
for(int i=1;i<=n;i++) dp[i][i]=0;
while(m--) {
int u,v,w;
cin>>u>>v>>w;
dp[u][v]=mixx(w,dp[u][v]);
}
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
for(int k=1;k<=n;k++) {
dp[j][k]=min({dp[j][k],dp[j][i]+dp[i][k]});
ans+=dp[j][k]==INF?0:dp[j][k];
}
}
}
cout<<ans;
}
```
[TIOJ 1340](https://tioj.ck.tp.edu.tw/problems/1340)
```
這題乍看之下沒有什麼頭緒，不過我們很快就可以發現數字移動的範圍不大
我們嘗試把可轉移的數字建一條邊。
那我們要如何處理題目的要求 -- 最小值最大 ? 我們可能會想說可以透過外掛二分搜控制最小值，
並且每次都找一次最大生成樹，樹上的路徑就是答案
但這樣太麻煩了，不僅要重寫一次最大生成樹，複雜度也會多一個logn。
有一個性質是：我們知道最大生成樹 == 最大瓶頸生成樹。
什麼意思呢 ? 就是兩個點要找最大邊的話，那就找最大瓶頸生成樹即可。
要怎麼處理樹上兩點的最大邊 ? 只要利用 LCA 即可
```
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define tup tuple<int,int,int>
#define g0 get<0>(i)
#define g1 get<1>(i)
#define g2 get<2>(i)
#define f first
#define s second
#define lowbit(x) (x&-x)
#define endl '\n'
using namespace std;
const int maxn = 1e5 + 5 ;
vector< tup >edge;
vector< pii >adj[maxn];
int pa[maxn],siz[maxn],depth[maxn];
int up[maxn][20],minn[maxn][20];
int n,q;
inline int findset(int x){return pa[x]==x?x:pa[x]=findset(pa[x]);}
bool cmp(tup i1,tup i2){return get<2>(i1)>get<2>(i2);}
void init()
{
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j+=i)
{
if(j-i>0) edge.pb({j,j-i,i});
if(j+i<=n) edge.pb({j,j+i,i});
}
}
void Dfs(int x,int p,int level,int value)
{
depth[x]=++level;
up[x][1]=p;
minn[x][1]=value;
for(auto i:adj[x]) if(i.f!=p) Dfs(i.f,x,level,i.s);
}
void solve()
{
for(int i=1;i<=n;i++) pa[i]=i,siz[i]=1;
sort(edge.begin(),edge.end(),cmp);
for(auto i:edge)
{
int u=findset(g0),v=findset(g1),w=g2;
if(u==v) continue;
if(siz[u]>siz[v])
{
pa[v]=u;
siz[u]+=siz[v];
adj[g0].pb({g1,w});
adj[g1].pb({g0,w});
}
else
{
pa[u]=v;
siz[v]+=siz[u];
adj[g0].pb({g1,w});
adj[g1].pb({g0,w});
}
}
}
void Doubled()
{
for(int c=2;c<=17;c++)
for(int b=1;b<=n;b++)
{
up[b][c]=up[up[b][c-1]][c-1];
minn[b][c]=min(minn[b][c-1],minn[up[b][c-1]][c-1]);
}
}
int print(int u,int v)
{
if(depth[u]>depth[v]) swap(u,v);
int l=depth[v]-depth[u],c=1,lowest=1e18;
while(l)
{
if(l&1) lowest=min(lowest,minn[v][c]),v=up[v][c];
l>>=1;
c++;
}
if(u==v) return lowest;
for(int b=19;b>0;b--)
{
if(!up[u][b]||up[u][b]==up[v][b]) continue;
lowest=min({lowest,minn[v][b],minn[u][b]});
u=up[u][b];
v=up[v][b];
}
if(u!=v) lowest=min({lowest,minn[v][1],minn[u][1]});
return lowest;
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n>>q;
init();
solve();
Dfs(1,0,0,-1);
Doubled();
while(q--)
{
int a,b;
cin>>a>>b;
cout<<print(a,b)<<endl;
}
}
```
:::
http://mdcpp.mingdao.edu.tw/contest/24/problem/C
```
這題應該不難了解到說倒著做會比較好。
是要怎麼倒著做呢 ? 簡單來說，我們會發現若是正著做的話，我們會需要面臨到刪除許多邊的問題。
我們知道一般的並查集是無法完成刪邊的動作的。
那我們會需要換一個方法，我們只要先把會被刪掉的邊先刪掉，那這就會是最後的情況。
我們只需要接下來慢慢一個接著一個把邊接回去，藉由並查集指向點權最大的邊即可。
```
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define tup tuple<int,int,int>
#define g0 get<0>(i)
#define g1 get<1>(i)
#define g2 get<2>(i)
#define f first
#define s second
#define lowbit(x) (x&-x)
#define endl '\n'
#define mid ((l+r)>>1)
#define md ((l+r)/2)
#define i1 (i<<1)
#define i2 (i1+1)
#define Hash(x,y) (maxn*x+y)
#define iofaster ios::sync_with_stdio(0);cin.tie(0)
#define fr(a) freopen((a),"r",stdin)
#define fw(a) freopen((a),"w",stdout)
#define maxx(a,b) (a>b?a:b)
#define mixx(a,b) (a>b?b:a)
#define mset(a,b) memset(a,b,sizeof(a))
#define all(x) x.begin(),x.end()
#define int long long
#define double long double
using namespace std;
const int maxn = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int INF = 1e9 + 9 ;
const double eps = 1e-7 ;
set<pii>st;
int w[maxn],pa[maxn];
int findset(int x) {
return x==pa[x]?x:pa[x]=findset(pa[x]);
}
void uni(int a,int b) {
int ap=findset(a);
int bp=findset(b);
if(ap==bp) return ;
if(w[ap]>w[bp]) {
pa[bp]=ap;
}
else if(w[ap]<w[bp]) {
pa[ap]=bp;
}
else {
if(ap<bp) pa[bp]=ap;
else pa[ap]=bp;
}
}
signed main()
{
iofaster;
int n,m,q;
cin>>n>>m>>q;
for(int i=1;i<=n;i++) cin>>w[i];
for(int i=1;i<=n;i++) pa[i]=i;
while(m--) {
int a,b;
cin>>a>>b;
st.insert({a,b});
st.insert({b,a});
}
vector<tup>query;
vector<int>ans;
while(q--) {
int t,a,b;
cin>>t;
if(t==0) {
cin>>a>>b;
st.erase({a,b});
st.erase({b,a});
}
else cin>>a;
query.pb({t,a,b});
}
reverse(all(query));
for(auto [u,v]:st) {
uni(u,v);
}
for(auto [t,a,b]:query) {
if(t==0) {
uni(a,b);
}
else {
int p=findset(a);
if(w[p]==w[a]) ans.pb(0);
else ans.pb(p);
}
}
reverse(all(ans));
for(auto i:ans) cout<<i<<endl;
}
```
:::
## 並查集
[ABC214D](https://atcoder.jp/contests/abc214/tasks/abc214_d)
```
透過觀察可以發現，本題的答案就是一個邊往外延伸出去，遇到比他大的邊就停止，看經過了多少邊。
但我們可能不知道要如何執行上面的動作 ? 沒錯，他很難執行，我們需要換個想法。
提示 1 : 排序
提示 2 : 並查集
我們可以發現，假如我們嘗試先把小的邊連起來，那代表當個連通塊的邊一定會比較小，就可以直接算有幾個點符合了 !
Unbelievable !
```
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define tup tuple<int,int,int>
#define g0 get<0>(i)
#define g1 get<1>(i)
#define g2 get<2>(i)
#define f first
#define s second
#define lowbit(x) (x&-x)
#define endl '\n'
#define mid ((l+r)>>1)
#define i1 (i<<1)
#define i2 (i1+1)
#define Hash(x,y) (maxn*x+y)
#define iofaster ios::sync_with_stdio(0);cin.tie(0)
#define fr(a) freopen((a),"r",stdin)
#define fw(a) freopen((a),"w",stdout)
#define int long long
using namespace std;
const int maxn = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int INF = 1e9 + 9 ;
int pa[maxn],sz[maxn];
vector<tup>edge;
int findset(int x) {
return x==pa[x]?x:pa[x]=findset(pa[x]);
}
signed main()
{
int n,ans=0;
cin>>n;
for(int i=0;i<n-1;i++) {
int u,v,w;
cin>>u>>v>>w;
edge.pb({w,u,v});
}
sort(edge.begin(),edge.end());
for(int i=1;i<=n;i++) pa[i]=i,sz[i]=1;
for(auto [w,u,v]:edge) {
u=findset(u),v=findset(v);
ans+=w*sz[u]*sz[v];
if(sz[u]>sz[v]) pa[v]=u,sz[u]+=sz[v];
else pa[u]=v,sz[v]+=sz[u];
}
cout<<ans;
}
```
:::
[ABC228D](https://atcoder.jp/contests/abc228/tasks/abc228_d)
```
簡單來說，題目就是要求你要透過一個點持續的往右找到 -1 的點就停下來改值。
我們需要一個方法能夠持續往右，但直接搜索太慢了
我們可以把已經有值的點連成一個連通塊，
在回答詢問時，若此點還是 -1，我們就修改此點，將左右兩點若是也已經被修改的話就連起來
反之，若此點不是 -1，我們就可以尋找此點連通塊的最右方，就是我們要的位置
註：這題或許可以用 set 做，我不太確定
```
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define tup tuple<int,int,int>
#define g0 get<0>(i)
#define g1 get<1>(i)
#define g2 get<2>(i)
#define f first
#define s second
#define lowbit(x) (x&-x)
#define endl '\n'
#define mid ((l+r)>>1)
#define i1 (i<<1)
#define i2 (i1+1)
#define Hash(x,y) (maxn*x+y)
#define iofaster ios::sync_with_stdio(0);cin.tie(0)
#define fr(a) freopen((a),"r",stdin)
#define fw(a) freopen((a),"w",stdout)
#define maxx(a,b) (a>b?a:b)
#define mixx(a,b) (a>b?b:a)
#define mset(a,b) memset(a,b,sizeof(a))
#define all(x) x.begin(),x.end()
#define int long long
using namespace std;
const int maxn = 2e6 + 5 ;
const int mod = 1e9 + 7 ;
const int INF = 1e9 + 9 ;
int pa[maxn],arr[maxn];
int n=(1<<20),q;
int findset(int x) {
return x==pa[x]?x:pa[x]=findset(pa[x]);
}
void uni(int a,int b) {
if(a<0) a+=n;
if(b<0) b+=n;
a%=n,b%=n;
if(arr[a]==-1 or arr[b]==-1) return ;
a=findset(a),b=findset(b);
if(a==b) return ;
pa[a]=b;
}
signed main()
{
//iofaster;
mset(arr,-1);
for(int i=0;i<n;i++) pa[i]=i;
cin>>q;
while(q--) {
int t,x;
cin>>t>>x;
int h=x%n;
int nt=findset(h);
//cout<<h<<' '<<nt<<endl;
if(t==1) {
if(nt==h and arr[nt]==-1) {
arr[nt]=x;
uni(h-1,h);
uni(h,h+1);
}
else {
nt++;
nt%=n;
arr[nt%n]=x;
uni(nt-1,nt);
uni(nt,nt+1);
}
}
else {
cout<<arr[h]<<endl;
}
}
}
```
:::
## 數學
[TOI 2018 D](https://tioj.ck.tp.edu.tw/problems/2052)
[題解](https://hackmd.io/@iceylemon157/rkTeB9fgw#/3/22)
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
using namespace std;
int ans=0;
int d[100];
int c[2000+10][2000+10];
inline void cal(int md) {
int sum=0,x=1;
for(int i=0;i<70;i++) {
x=(x*c[sum+d[i]][sum])%md;
sum+=d[i];
}
ans=(ans+x)%md;
}
inline void init(int md) {
for(int i=0;i<=2000;i++) {
c[i][0]=1;
for(int j=1;j<=i;j++) {
c[i][j]=(c[i-1][j-1]+c[i-1][j]);
int x=c[i-1][j-1]+c[i-1][j];
c[i][j]=x%md;
}
}
}
vector<int>v[1000];
int used[2000+10];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int md;
string str;
cin>>md>>str;
init(md);
string st=str;
sort(st.begin(),st.end());
for(int i=0;i<st.size();i++) d[st[i]-'A']++,v[st[i]-'A'].push_back(i);
for(int p=0;p<str.size();p++) {
for(int i=0;i<st.size();i++) {
if(used[i] or (i!=0 and st[i]==st[i-1])) continue;
if(st[i]!=str[p]) {
d[st[i]-'A']--;
cal(md);
d[st[i]-'A']++;
}
else break;
}
used[v[str[p]-'A'].back()]=1;
v[str[p]-'A'].pop_back();
d[str[p]-'A']--;
}
cout<<ans;
}
```
:::
## 線段樹
[CF EDU](https://codeforces.com/edu/course/2/lesson/4/3/practice/contest/274545/problem/C)
```
這題表面上很難想到，我們可以透過一點分析
我們想要藉由同個數之間的範圍加起來算出答案，可以怎麼做 ?
1. 假如已經兩個都出現但只有尾出現，需算出 0
2. 假如已經兩個都出現且在範圍內，需算出 1
3. 假如只有1個出現，需算出 0
我們可以透過當他還沒出現兩次時，前面的數都還是 0
被觸發的時候，前面是 0 ， 後面是 1
就可以發現答案算出來了 !
詳細請同學自行證明
```
:::spoiler Code
```cpp=
#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int,int>
#define tup tuple<int,int,int>
#define g0 get<0>(i)
#define g1 get<1>(i)
#define g2 get<2>(i)
#define f first
#define s second
#define lowbit(x) (x&-x)
#define endl '\n'
#define mid ((l+r)>>1)
#define i1 (i<<1)
#define i2 (i1+1)
#define Hash(x,y) (maxn*x+y)
#define iofaster ios::sync_with_stdio(0);cin.tie(0)
#define fr(a) freopen((a),"r",stdin)
#define fw(a) freopen((a),"w",stdout)
#define maxx(a,b) (a>b?a:b)
#define mixx(a,b) (a>b?b:a)
#define mset(a,b) memset(a,b,sizeof(a))
#define all(x) x.begin(),x.end()
using namespace std;
const int maxn = 2e5 + 5 ;
const int mod = 1e9 + 7 ;
const int INF = 1e9 + 9 ;
int pos[maxn],val[4*maxn],ans[maxn];
void modify(int l,int r,int p,int i) {
if(l==r) {
val[i]++;
return ;
}
if(p<=mid) modify(l,mid,p,i1);
else modify(mid+1,r,p,i2);
val[i]=val[i1]+val[i2];
}
int query(int l,int r,int L,int R,int i) {
if(L<=l and R>=r) {
return val[i];
}
int sum=0;
if(L<=mid) sum+=query(l,mid,L,R,i1);
if(R>mid) sum+=query(mid+1,r,L,R,i2);
return sum;
}
signed main()
{
iofaster;
int n;
cin>>n;
for(int i=0;i<2*n;i++) {
int a;
cin>>a;
if(pos[a]) {
modify(1,n*2,pos[a],1);
ans[a]=query(1,n*2,pos[a]+1,2*n,1);
}
else {
pos[a]=i+1;
}
}
for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
}
```
:::
## 小技巧 ( 可以自己想想看 )
- 差分
http://mdcpp.mingdao.edu.tw/contest/24/problem/A
https://zerojudge.tw/ShowProblem?problemid=g597
- 單調隊列
http://mdcpp.mingdao.edu.tw/contest/24/problem/B
Sign in with Wallet
Connect another wallet