---
# System prepended metadata

title: 經典題目講解 & 小技巧

---

# 經典題目講解 & 小技巧

## 圖論

[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
