---
# System prepended metadata

title: problem
tags: [learn]

---


25/9/13
[F - Visible Buildings](https://atcoder.jp/contests/abc385/tasks/abc385_f):卡精度題，若用$O(n)$解法就不會遇到?

25/9/14
[F - Count Arrays](https://atcoder.jp/contests/abc387/tasks/abc387_f):觀察+基環樹

25/9/23
[D. Segments Covering](https://codeforces.com/contest/2125/problem/D):痾就機率dp，可我不會

25/10/4
[E. Distance to Different](https://codeforces.com/contest/1989/problem/E):🉐dp

25/10/6
[E. Ancient Tree](https://codeforces.com/contest/2127/problem/E):要虛樹，可我不會，改天再來學，但我會啟發式合併

25/10/8
[D. Price Tags](https://codeforces.com/contest/2144/problem/D):竟還叫gpt5幫忙debug

25/10/12 
~~我會vim了(h, j, k, l)，但寫code的速度卻比vs code慢~~
複習以前所學
[非嚴格次小生成樹](https://zerojudge.tw/ShowProblem?problemid=c495)
:::spoiler code
```cpp=1
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll

const int mxN=1e5;

vector<pair<int, int>> adj[mxN];
int mx[21][mxN], p[mxN], jmp[21][mxN], dep[mxN];

int find(int x) {
	if(x^p[x]) {
		return p[x]=find(p[x]);
	}
	return x;	
}

bool unite(int a, int b) {
	int x=find(a), y=find(b);
	if(x^y) {
		p[x]=y;
		return 1;
	}
	return 0;
}

int lca(int a, int b) {
	if(dep[a]<dep[b]) swap(a, b);
	int diff=dep[a]-dep[b];
	for(int i=20; ~i; i--) {
		if(diff>>i&1) {
			a=jmp[i][a];
		}
	}
	if(a==b) return a;
	for(int i=20; ~i; i--) {
		if(jmp[i][a]!=jmp[i][b]) {
			a=jmp[i][a];
			b=jmp[i][b];
		}
	}
	return jmp[0][a];
}

void dfs(int v, int fa) {
	dep[v]=(~fa?dep[fa]:-1)+1;
	jmp[0][v]=fa;
	for(int i=1; i<=20; i++) {
		if(jmp[i-1][v]==-1) break;
		jmp[i][v]=jmp[i-1][jmp[i-1][v]];
		mx[i][v]=max(mx[i-1][v], mx[i-1][jmp[i-1][v]]);
	}
	for(auto [u, w] : adj[v]) {
		if(u==fa) continue;
		mx[0][u]=w;
		dfs(u, v);
	}
}

int f(int a, int b) {
	int res=0;
	int c=lca(a, b);
	int diff=dep[a]-dep[c];
	for(int i=20; ~i; i--) {
		if(diff>>i&1) {
			res=max(res, mx[i][a]);
			a=jmp[i][a];
		}
	}	
	diff=dep[b]-dep[c];
	for(int i=20; ~i; i--) {
		if(diff>>i&1) {
			res=max(res, mx[i][b]);
			b=jmp[i][b];
		}
	}	
	return res;
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin>>n>>m;
	iota(p, p+n, 0);
	vector<array<int, 3>> edge;
	vector<bool> e(m);
	for(int i=0; i<m; i++) {
		int a, b, w; cin>>a>>b>>w;
		--a, --b;
		edge.push_back({w, a, b});
	}
	sort(edge.begin(), edge.end());
	int cnt=0, idx=0;
	int sum=0;
	while(cnt<n-1) {
		auto [w, x, y]=edge[idx];
		if(unite(x, y)) {
			cnt++;
			adj[x].push_back({y, w});
			adj[y].push_back({x, w});
			e[idx]=1;
			sum+=w;
		}
		idx++;
	}
	memset(jmp, -1, sizeof(jmp));
	dfs(0, -1);
	int ans=1e18;
	for(int i=0; i<m; i++) {
		if(!e[i]) {
			ans=min(ans, sum-f(edge[i][1], edge[i][2])+edge[i][0]);
		}
	}
	cout<<sum<<' '<<ans<<"\n";
	return 0;
}

```
:::
[嚴格次小生成樹](https://loj.ac/p/10133)
::: spoiler code
```cpp=1
//小心維護mx1
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define int ll

const int mxN=1e5;

vector<pair<int, int>> adj[mxN];
int mx[21][mxN], mx1[21][mxN], p[mxN], jmp[21][mxN], dep[mxN];

int find(int x) {
	if(x^p[x]) {
		return p[x]=find(p[x]);
	}
	return x;	
}

bool unite(int a, int b) {
	int x=find(a), y=find(b);
	if(x^y) {
		p[x]=y;
		return 1;
	}
	return 0;
}

int lca(int a, int b) {
	if(dep[a]<dep[b]) swap(a, b);
	int diff=dep[a]-dep[b];
	for(int i=20; ~i; i--) {
		if(diff>>i&1) {
			a=jmp[i][a];
		}
	}
	if(a==b) return a;
	for(int i=20; ~i; i--) {
		if(jmp[i][a]!=jmp[i][b]) {
			a=jmp[i][a];
			b=jmp[i][b];
		}
	}
	return jmp[0][a];
}

void dfs(int v, int fa) {
	dep[v]=(~fa?dep[fa]:-1)+1;
	jmp[0][v]=fa;
	for(int i=1; i<=20; i++) {
		if(jmp[i-1][v]==-1) break;
		jmp[i][v]=jmp[i-1][jmp[i-1][v]];
		mx[i][v]=max(mx[i-1][v], mx[i-1][jmp[i-1][v]]);
		if(mx[i-1][v]==mx[i-1][jmp[i-1][v]]) {
			mx1[i][v]=max(mx1[i-1][v], mx1[i-1][jmp[i-1][v]]);
		} else {
			if(mx[i][v]==mx[i-1][v]) {
				mx1[i][v]=mx[i-1][jmp[i-1][v]];
			} else {
				mx1[i][v]=mx[i-1][v];
			}
		}
	}
	for(auto [u, w] : adj[v]) {
		if(u==fa) continue;
		mx[0][u]=w;
		dfs(u, v);
	}
}

int f(int a, int b, int w) {
	int res=0;
	int c=lca(a, b);
	int diff=dep[a]-dep[c];
	for(int i=20; ~i; i--) {
		if(diff>>i&1) {
			res=max(res, (w!=mx[i][a]?mx[i][a]:mx1[i][a]));
			a=jmp[i][a];
		}
	}	
	diff=dep[b]-dep[c];
	for(int i=20; ~i; i--) {
		if(diff>>i&1) {
			res=max(res, (w!=mx[i][b]?mx[i][b]:mx1[i][b]));
			b=jmp[i][b];
		}
	}	
	return res;
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int n, m; cin>>n>>m;
	iota(p, p+n, 0);
	vector<array<int, 3>> edge;
	vector<bool> e(m);
	for(int i=0; i<m; i++) {
		int a, b, w; cin>>a>>b>>w;
		--a, --b;
		edge.push_back({w, a, b});
	}
	sort(edge.begin(), edge.end());
	int cnt=0, idx=0;
	int sum=0;
	while(cnt<n-1) {
		auto [w, x, y]=edge[idx];
		if(unite(x, y)) {
			cnt++;
			adj[x].push_back({y, w});
			adj[y].push_back({x, w});
			e[idx]=1;
			sum+=w;
		}
		idx++;
	}
	memset(jmp, -1, sizeof(jmp));
	dfs(0, -1);
	int ans=1e18;
	for(int i=0; i<m; i++) {
		if(!e[i]) {
			ans=min(ans, sum-f(edge[i][1], edge[i][2], edge[i][0])+edge[i][0]); 
		}
	}
	cout<<ans<<"\n";
	return 0;
}
```
:::

25/10/24
[E. Anton and Permutation](https://codeforces.com/contest/785/problem/E):經典分塊題，可惡bug好煩，先擺著

25/10/28
[F - Loud Cicada](https://atcoder.jp/contests/abc423/tasks/abc423_f):數學題，好像要用到二項式反演，但我會容斥，最後跟它好像有異曲同工之妙?

25/10/30
[G - Fine Triplets](https://atcoder.jp/contests/abc392/tasks/abc392_g):模板題，但值得注意```while(len<=2*mx) len*=2```要取等號，因為當兩個數都等於$mx$時數組會越界，~~CSES沒卡我~~

25/11/02
[F - Dangerous Sugoroku](https://atcoder.jp/contests/abc388/tasks/abc388_f):這題我沒想到，其實就只用到矩陣快速冪而已，看完題解後我就直覺地做，跑了1秒多過了，題解還在搞優化，雖然快了不少，但我沒理解，改天再看看吧，~~因該不會看反正都過了~~

25/11/04
[E. New Year and Castle Construction](https://codeforces.com/contest/1284/problem/E):亂找的，但好像是計算幾何，先放在這，我要去補眠了

25/11/08
[F - Variety Split Hard](https://atcoder.jp/contests/abc397/tasks/abc397_f):水題?純粹我遇到第二次[類似題](https://atcoder.jp/contests/dp/tasks/dp_w)還想不到要從供獻下手

25/11/9
[F - Jump Traveling](https://atcoder.jp/contests/abc414/tasks/abc414_f):觀察+bfs

25/11/10
[APIO 2007 Zoo](https://cses.fi/237/list/):狀壓dp，然後我不會，先放在這

[P3403 跳楼机](https://www.luogu.com.cn/problem/P3403):複習同餘最短路，注意h要先減1

25/11/11
[E - Reflection on Grid](https://atcoder.jp/contests/abc431/tasks/abc431_e):類似Jump Traveling，然後狀態不要懶得開

25/11/13
[Two Stack Sorting](http://cses.fi/problemset/task/2402)

25/11/17
[C - Nearest vectors](https://codeforces.com/contest/598/problem/C):又是計算幾何

25/11/22
[F - Double Sum 3](https://atcoder.jp/contests/abc390/tasks/abc390_f):又是供獻老梗，可惜我沒解開qq

25/11/23
[E. Best Subsequence](https://codeforces.com/contest/2026/problem/E):想不到這題要用網路流

25/11/25
[G - Leaf Color](https://atcoder.jp/contests/abc340/tasks/abc340_g):這題嗆我不會dp和找bug

25/12/09
[F - Two Sequence Queries](https://atcoder.jp/contests/abc357/tasks/abc357_f):線段樹模板題，但我真的找不到bug😢
[ 987 . 最大子正方形和](https://oj.ntucpc.org/contests/25/problems/987):巨水?

25/12/10
[Ex - 01? Queries](https://atcoder.jp/contests/abc246/tasks/abc246_h):ctrl c ctrl v，dp+快速冪，~~我好懶~~

25/12/14
[IOI13_CAVE](https://oj.uz/problem/view/IOI13_cave):譴責不會二分搜

25/12/20
[E. A, B, AB and BA](https://codeforces.com/contest/2069/problem/E):我不會貪心

25/12/22
[G. Xor-MST](https://codeforces.com/contest/888/problem/G):複習boruvka，另外第一次被卡，unordered_map常數真的很大 

25/12/25
[G - Alone](https://atcoder.jp/contests/abc346/tasks/abc346_g):線段樹應用，然後我的code寫爛沒考慮到極端的情況，導致一直wa一筆測資
[Feast (NOI19_feast)](https://oj.uz/problem/view/NOI19_feast):複習alien優化

25/12/28
[NOI18_knapsack](https://oj.uz/problem/view/NOI18_knapsack):從5月困擾我到現在才ac的題，記得當時就以為只是多重背包水題，然後傳上去只有73，複雜度是$O(N \log K)$，但注意到本題$S<=2000$，往$S$沒有很大想一下，均攤後，複雜度可降到$O(S^2 \log S)$

25/12/29
[F - Exhausted?](https://atcoder.jp/contests/arc076/tasks/arc076_d):hall theorem

25/12/31
[C. Watching Fireworks is Fun](https://codeforces.com/contest/372/problem/C):Happy New Year! 單調dp(順便複習單調優化多重背包問題，~~有點通靈，我比賽時一定想不到~~)

25/1/1
[Game (IOI13_game)](https://oj.uz/problem/view/IOI13_game):這題我是用二維線段樹加動態開點做，然後就MLE了，只拿到63，後來，空間優化我實在想不到，看了wiwiho的[code](https://oj.uz/submission/423041)後，我才發現可以用懶標，感性理解一下，均攤空間(有這講法嗎?)，就會發現優化了很大的空間，然後就過了(外傳:因為這題，我從偽指標使用者(因為若用此方法，只能拿到80，雖然大陸好像用了四分樹解決，但我不會)，所以我就轉為了指標使用者XD)

25/1/4
[部落衝突 2](https://toj.tfcis.org/oj/pro/1059/):南一中的複賽題，精神ac一下，有兩種做法，離線(用lca)或在線(用hld)
[G - Mediator](https://atcoder.jp/contests/abc350/tasks/abc350_g):分塊輕重點
[J. First Non-Bipartite Edge](https://codeforces.com/edu/course/2/lesson/7/2/practice/contest/289391/problem/J):二分圖判定(水)，用dsu

25/1/6
[Snake Escaping](https://oj.uz/problem/view/JOI18_snake_escaping):先擺著，我只想到22分的暴力，滿分解要用到sos dp(超集合&子集合)

25/1/13
[D - Non-Ancestor Matching](https://atcoder.jp/contests/arc205/tasks/arc205_d):我code寫爛的題
25/1/15
[APIO 2007 backup](https://cses.fi/237/task/B/):又是code寫爛的題，只好叫gemini 3幫我debug QAQ
[D - Switch Seats](https://atcoder.jp/contests/abc399/tasks/abc399_d):又是code寫爛的題，先放著反正也才900

25/1/23
好久沒更新~
[E. Fair Share](https://codeforces.com/problemset/problem/1634/E):想不到歐拉迴路如何套在此題上，看題解精神一下，簡單說一下，就是發現數字出現次數若為奇數則無解，否則必存在解，將每組看成點放在集合A，並將點連向每組中的數值，跑一下歐拉迴路，就好了

25/2/6
[Meteors (POI11_met)](https://oj.uz/problem/view/POI11_met):問LLM了解整體二分思想(我賽中一定想不到XD)