AtCoder Beginner Contest 214

目录

AtCoder Beginner Contest 214

C - Distribution

题目

有\(N\)个人,第\(i\)个人会在\(T_i\)时刻从Takahashi手上拿到宝石.若第\(i\)个人在\(t_i\)时刻(不一定等于\(T_i\))拿到宝石,他会在\(t_i+S_i\)时刻将宝石给\((i-1)%n+1\)个人.

给定\(N,S,T\)问每个人拿到宝石的最早时间.

AtCoder Beginner Contest 214

思路

先把\(T_i\)和对应的\(i\)捆绑起来,扔进按\(T\)从小到大排序的小根堆,每次从小根堆中取出\(t_i\)和\(i\),则\(ans_i=t_i\),将\(t_i+S_i\)和\((i-1)\%n+1\)扔进堆里即可.

代码

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

const int N = 200010;
int n;
int s[N] , t[N];
int ans[N];
struct node {
	int t , id;
	bool operator < (const node &a) const {
		return t > a.t;
	}
};
node make(int t , int id) {
	node tmp;
	tmp.t = t , tmp.id = id;
	return tmp;
}
priority_queue <node> q;
int main() {
	n = read();
	for(int i = 1 ; i <= n ; i++)
		s[i] = read();
	for(int j = 1 ; j <= n ; j++) {
		t[j] = read();
		q.push(make(t[j] , j));
	}
	while(!q.empty()) {
		node k = q.top();
		q.pop();
		if(ans[k.id] != 0)
			continue;
		ans[k.id] = k.t;
		q.push(make(k.t + s[k.id] , k.id % n + 1));
	}
	
	for(int i = 1 ; i <= n ; i++)
		printf("%d\n" , ans[i]);
	return 0;
}

D - Sum of Maximum Weights

题目

给定一颗树,有\(N\)个结点,定义\(f(u,v)\)为\(u\),\(v\)​路径上边权的最大值,求\(\sum_{i=1}^{N-1}\sum_{j=i+1}^Nf(i,j)\)​.

AtCoder Beginner Contest 214

思路

把边按照边权从小到大排序,并按顺序遍历所有边,对于每条边,它对答案的贡献为

\[w_i\cdot size_{u_i}\cdot size_{v_i} \]

\(size\)为点所属并查集的大小,计算答案后,合并\(i,j\)所在并查集.

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>

int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

typedef long long lint;
const int N = 200010;
int n;

struct EDGE {
	int u , v;
	lint w;
}ed[N];
bool cmp(EDGE x , EDGE y) {
	return x.w < y.w;
}

lint size[N];
int fa[N];
int findroot(int x) {
	return fa[x] == x ? x : (fa[x] = findroot(fa[x]));
}
void uni(int x , int y) {
	x = findroot(x) , y = findroot(y);
	if(x == y)
		return ;
	size[x] += size[y];
	fa[y] = x;
}

int main() {
	n = read();
	for(int i = 1 ; i < n ; i++)
		ed[i].u = read() , ed[i].v = read() , ed[i].w = read();
	
	for(int i = 1 ; i <= n ; i++)
		fa[i] = i , size[i] = 1;
	std::sort(ed + 1 , ed + n , cmp);
	lint ans = 0;
	for(int i = 1 ; i < n ; i++) {
		int x = findroot(ed[i].u) , y = findroot(ed[i].v);
		ans += ed[i].w * size[x] * size[y];
		uni(x , y);
	}
	std::cout << ans;
	return 0;
}

E - Packing Under Range Regulations

题目

有\(10^9\)个盒子编号\(1\)到\(10^9\),每个盒子可以放一个球,第\(i\)个球可以放在编号\(l_i\)到\(r_i\)的盒子中.给定\(l,r\),问:是否每个球都能放在盒子中.

AtCoder Beginner Contest 214

思路

把每个球按照\(l\)从小到大排序,假设当前需要用编号为\(p\)的盒子,且编号为\(1\)到\(p-1\)的盒子已经不可用,有\(j\)个还没有放入任何一个盒子的小球,且它们都可以放在\(p\)盒子中.

我们肯定要先把\(r\)小的先放到盒子里,因为前面的盒子已经不可用,\(r\)​大的还有可能放进后面的盒子.

因此,我们的贪心就出来了,详见代码.

居然被一些奇奇怪怪的小错误卡了半天.

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
int read() {
	int re = 0;
	char c = getchar();
	bool negt = false;
	while(c < '0' || c > '9')
		negt |= (c == '-') , c = getchar();
	while(c >= '0' && c <= '9')
		re = (re << 1) + (re << 3) + c - '0' , c = getchar();
	return negt ? -re : re;
}

typedef long long lint;
const int N = 2000010;
int n;

struct BALL {
	int l , r;
	bool operator < (const BALL &b) const{
		return r > b.r;
	}
}ball[N];
bool cmp(BALL a , BALL b) {
	return a.l < b.l;
}

priority_queue <BALL> q;
int main() {
	int T = read();
	while(T--) {
		while(q.size())q.pop();
		n = 0;
		
		n = read();
		for(int i = 1 ; i <= n ; i++)
			ball[i].l = read() , ball[i].r = read();
		
		sort(ball + 1 , ball + n + 1 , cmp);//左端点排序
		bool ans = true;
		int box = ball[1].l , p = 1;
		while(p <= n || !q.empty()) {
			while(ball[p].l <= box && p <= n)//可以放进编号为box的小球放入堆内,堆维护最小r
				q.push(ball[p]), ++p;
			
			if(q.empty()) {//跳过无用盒子
				box = ball[p].l;
				continue;
			}
			BALL b = q.top();//尝试将小球b放入编号为box的盒子
			q.pop();
			if(b.r < box) {//放不了
				ans = false;
				break;
			}
			++box;
		}
		puts(ans ? "Yes" : "No");
	}
	return 0;
}

F - Substrings

题目

有一个字符串\(S\),你可以确定一个序列\(a_1,a_2,\cdots a_k\),满足\(\forall i\in[1,k)\quad ,a_i<a_{i+1}-1\),且\(k>0\).定义字符串\(T=S_{a_1}S_{a_2}S_{a_3}\cdots S_{a_k}\).

问有多少个不同的\(T\)

AtCoder Beginner Contest 214

思路

考虑\(a_i<a_{i+1}\)的情况怎么做.

设\(f_i\)​表示在从前\(i\)​个中选择若干字符,其中必选\(i\)​,按原本顺序能构不同的字符串的个数.则有:

\[f_i=\sum_{j=k}^{i-1}f_j \]

其中,\(\forall x\in(k,i),S_x\neq S_i\)​,且\(S_k=S_i,k<i\)​,若不存在\(S_k=S_i\)​ \(k=0\).

特殊地,\(f_0=1\),表示空串.

由于\(T\)不能为空,答案就是\(\sum_{i=1}^nf_i\).

回到这题.

\(a_i<a_{i+1}-1\).

其实变化多少,只要让\(i-j>2\)时才累加\(f_j\)即可,但是这样你会发现\(i=1\)时并不会累加\(f_0\),这不是我们想要的结果,所以,为了方便,我们让\(f_{-1}=0\).

代码

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long
using namespace std;
const int N = 200010;
const int mod = (int)1e9+7;

int __f[N] , *f = __f + 3;
char s[N];
int n;
signed main() {
	scanf("%s" , s + 1);
	n = strlen(s + 1);
	
	f[-1] = 1;
	for(int i = 1 ; i <= n ; i++) {
		for(int j = i - 1 ; true ; --j) {
			if(i - j >= 2)
				f[i] += f[j];
			if(s[i] == s[j])
				f[i] += f[j - 1];
			if(j == -1 || s[j] == s[i])
				break;
		}
		f[i] %= mod;
	}
	int ans = 0;
	for(int i = 1 ; i <= n ; i++)
		ans += f[i];
	cout << ans % mod;
	return 0;
} 
上一篇:AtCoder Beginner Contest 216题解


下一篇:AtCoder Beginner Contest 216 D - Pair of Balls