[数据结构与算法]AtCoder ABC214 简单题解

好久没更新了。今天参加了一下 ABC，防止抑郁。

A - New Generation ABC

链接

https://atcoder.jp/contests/abc214/tasks/abc214_a

题解

签到水题。
给 ABC 竞赛的编号，问对应的竞赛有几个问题。

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;

const LL INF=4e18;
const int MAXN=1e6+10;

int main() {
#if 1
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#endif
	//freopen("00.in", "r", stdin);
	//freopen("00.out", "w", stdout);
	LL n;
	cin>>n;
	if (n<=125) {
		cout<<"4\n";
	} else if (n<=211) {
		cout<<"6\n";
	} else {
		cout<<"8\n";
	}
	
	return 0;
}

B - How many?

链接

https://atcoder.jp/contests/abc214/tasks/abc214_b

题解

找 $a+b+c\le S$ 同时 $a?b?c\le T$ 的三元组 $(a,b,c)$ 的个数。但是本题的数据范围是 $0\le S\le 100,0\le T\le 10000$。
因此，我们知道 $0\le a,b,c\le 100$。那么我们直接暴力枚举即可。

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;

const LL INF=4e18;
const int MAXN=1e6+10;

int main() {
#if 1
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#endif
	//freopen("00.in", "r", stdin);
	//freopen("00.out", "w", stdout);
	LL s,t;
	cin>>s>>t;
	
	LL ans=0;
	for (LL a=0; a<=100; a++) {
		for (LL b=0; b<=100; b++) {
			for (LL c=0; c<=100;c++) {
				if (a+b+c<=s && a*b*c<=t) {
					ans++;
				}
			}
		}
	}
	cout<<ans<<"\n";
	
	return 0;
}

C - Distribution

链接

https://atcoder.jp/contests/abc214/tasks/abc214_c

题解

$N$ 只鹤逆时针围成圈，高桥在 $T_i$ 的时间给第 $i$ 只鹤一个宝石，这只鹤过了 $S_i$ 的时间后，将宝石传递给下一只鹤。问每只鹤第一次拿到宝石的时间。
根据题意，我们知道第一次拿到宝石有两种可能：
1、高桥给的。对应的时间点为 $T_i$；
2、上只鹤传递过来。对应的时间为 $T_{i?1}+S_{i?1}$。
因此问题就是要确认最小的 $T_i$ 是哪个，然后我们从这个 $i$ 开始递推即可。

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;

const LL INF=4e18;
const int MAXN=2e5+10;
LL s[MAXN];
LL t[MAXN];
LL ans[MAXN]; 
 
int main() {
#if 0
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#endif
	//freopen("00.in", "r", stdin);
	//freopen("00.out", "w", stdout);
	LL n;
	cin>>n;
	for (LL i=1; i<=n; i++) {
		cin>>s[i];
	} 
	for (LL i=1; i<=n; i++) {
		cin>>t[i];
	}
	
	//第i个snuke拿到gem有两个可能
	//高桥给
	//上面的sunke给。
	LL mint=4e18;
	LL st;
	//找到第一个开始的时间 
	for (LL i=1; i<=n; i++) {
		if (mint>t[i]) {
			mint=t[i];
			st=i;
		}
	}
	ans[st]=t[st];
	for (LL i=st; i<=st+n-1; i++) {
		LL now=i>n?i-n:i;//现在的编号 
		LL nxt=now+1;//下一个编号
		if (nxt>n) {
			nxt-=n;
		} 
		ans[nxt]=min(t[nxt], ans[now]+s[now]);
	}

	for (LL i=1; i<=n; i++) {
		cout<<ans[i]<<"\n";
	}

	return 0;
}

D - Sum of Maximum Weights

链接

https://atcoder.jp/contests/abc214/tasks/abc214_d

题解

读完题目，就知道这是一个最短路径问题。最短路径可以使用并查集来完成。
本题基本上属于最短路径问题模板题。

AC 代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;

const LL INF=4e18;
//并查集 
const int MAXN=1e5+10;
struct EDGE {
	LL u,v,w;
} e[MAXN];
LL fa[MAXN];//父亲
LL sa[MAXN]; 
void init(LL n) {
	for (LL i=0; i<=n; i++) {
		fa[i]=i;
		sa[i]=1;
	}
}
LL find(LL x) {
	if (fa[x]!=x) {
		fa[x]=find(fa[x]);
	}
	return fa[x];
}
void join(LL x, LL y) {
	x=find(x);
	y=find(y);
	sa[y]+=sa[x];
	fa[x]=y;
}

bool mycmp(const EDGE &x, const EDGE &y) {
	return x.w<y.w;
}

int main() {
#if 1
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#endif
	//freopen("00.in", "r", stdin);
	//freopen("00.out", "w", stdout);
	LL n;
	cin>>n;
	init(n);//初始化并查集 
	for (LL i=1; i<n; i++) {
		cin>>e[i].u>>e[i].v>>e[i].w;
	}
	sort(e+1, e+n, mycmp);
	
	LL ans=0;
	for (LL i=1; i<n; i++) {
		ans+=sa[find(e[i].u)]*sa[find(e[i].v)]*e[i].w;
		join(e[i].u, e[i].v);
	}
	cout<<ans<<"\n";
	
	return 0;
}

E - Packing Under Range Regulations

链接

https://atcoder.jp/contests/abc214/tasks/abc214_e

题解

数据结构体，使用优先队列搞定。

AC代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;

const LL INF=4e18;
const int MAXN=2e5+10;
struct NODE {
	LL x, y;
	bool operator<(const struct NODE &xx) const {
		return x<xx.x;
	}
} a[MAXN];

int main() {
#if 1
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
#endif
	//freopen("00.in", "r", stdin);
	//freopen("00.out", "w", stdout);
	LL T;
	cin>>T;
	while (T--) {
		LL n;
		cin>>n;
		LL maxx=0;
		for (LL i=1; i<=n; i++) {
			cin>>a[i].x>>a[i].y;
			maxx=max(maxx, a[i].y);
		}
		sort(a+1, a+n+1);
		
		priority_queue<LL, vector<LL>, greater<LL> > Q;
		bool flag=true;
		for (LL i=1; i<=n && flag; i++) {
			for (LL j=a[i-1].x; j<a[i].x && Q.size(); j++) {
				LL fr = Q.top(); 
				Q.pop();
				if (fr < j) {
					flag = false; 
					break;
				}
			}
			Q.push(a[i].y);
		}
		for (LL i=a[n].x; i<=maxx+1 && Q.size(); i++) {
			LL fr = Q.top(); 
			Q.pop();
			if (fr < i) {
				flag = false; 
				break;
			}
		}
		
		if (flag) {
			cout<<"Yes\n";
		} else {
			cout<<"No\n";
		}
	}
	
	return 0;
}