欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #631 div2 [萌新题解 只有三个题]

程序员文章站 2022-06-02 22:13:58
...

萌新的第一次cf ~打的巨烂无比 第二天来整理下
放一下原题和别人的题解!
原题目及作者答案
巨佬1的题解
巨佬2的题解
以下萌新的题解:
A. Dreamoon and Ranking Collection
题意:给出一个人参加n场比赛的所有排名,假设他再参加x场比赛可以取得v,v表示1~v的所有排名他都取得过,求最大的v。
话说读题读了好久qwqq
开一个桶排序 模拟就好啦!

#include<cstdio>
#include<cstring>

int n,x,t,rank,ans,book[505];

int main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&x);
		memset(book,0,sizeof(book));
		for(int i = 1; i <= n; ++i){
			scanf("%d",&rank);
			book[rank]++;
		}
		for(ans = 1; ans <= 250; ++ans){
			if(!book[ans]){
				if(!x)	break;
				else	x--;
			}else	continue;	
		}
		printf("%d\n",ans - 1);
	}
	return 0;
}

P.S.第一遍写的时候抽风 book数组只开了105……导致错误。至少应该开到200+呀!
B. Dreamoon Likes Permutations
题意:给一个连续的序列,共n个数。求从中间某个位置划分,前面l1个数字是序列1-l1的排列;后面n - l1 = l2个数字是1-l2的排列。
P.S.做的时候想了好久……也没有发现哪里是错的。明明都过了QWQ
思路就是正向/反向的看,因为答案无非0 1 2. 用桶排序两次。
要注意一个细节! 如果是123123这种,正反向都会得到3,但是答案只算一次!

PP.S 答案的思路更简单~ 找最大的那个数字maxx,一定是两个划分:maxx与n - maxx
然后分别检查这两种即可!

#include<cstdio>
#include<vector>
#include<utility>
#include<cstring>
using namespace std;

const int maxn = 200005;
int book[maxn],t,n,maxx,box[maxn];
vector<pair<int, int> > ans;

bool check(int x){
	for(int i = 1; i <= x; ++i)	box[i] = 0;
	for(int i = 1; i <= x; ++i)	box[book[i]]++;
	for(int i = 1; i <= x; ++i)	if(!box[i])	return 0;
	for(int i = 1; i <= n - x; ++i)	box[i] = 0;
	for(int i = x + 1; i <= n; ++i)	box[book[i]]++;
	for(int i = 1; i <= n - x; ++i)	if(!box[i])	return 0;
	return 1;
} 

int main(){
	scanf("%d",&t);
	while(t--){
		ans.clear();
		scanf("%d",&n);
		maxx = -1;
		for(int i = 1; i <= n; ++i){
			scanf("%d",&book[i]);
			if(book[i] > maxx)	maxx = book[i];
		}
		if(check(maxx))	ans.push_back(make_pair(maxx, n - maxx));
		if(check(n - maxx) && maxx * 2 != n)	ans.push_back(make_pair(n - maxx, maxx));
		printf("%d\n",ans.size());
		for(int i = 0; i < ans.size(); ++i)
			printf("%d %d\n",ans[i].first, ans[i].second);
	}
	return 0;
}

O(n)的复杂度!
C. Dreamoon Likes Coloring
这个题好秀的样子
题意:有m种颜色,涂一个长度为n的方块,每种颜色涂连续Li块(初始从1到n - li + 1选一个数,个数为li块),构造出使得所有方块都被涂色且每种颜色至少涂了一个方块的方法,方块上的颜色只记录最后一次涂的颜色(可以覆盖)。

感觉没思路好吧!Codeforces Round #631 div2 [萌新题解 只有三个题]
处理这两种情况后,就是可以的情况了。最后把后面的依次往后移就可以!
while(里要写>0),大于0必不可少哦!否则负数的bool值也是1.

#include<cstdio>
#define ll long long

const int maxn = 100005;
int n,m,x,book[maxn],ans[maxn];
ll sum;

void over(){puts("-1");}
void solve(){
	int i = m,rn = n;
	while(rn - i - book[i] + 1 > 0){
		ans[i] = rn - book[i] + 1;
		rn -= book[i];
		i--;
	}	
	for(int i = 1; i <= m; ++i)
		printf("%d ",ans[i]);
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1; i <= m; ++i){
		scanf("%d",&book[i]);
		sum += book[i];
	}
	//check right
	if(sum < n){	
		over();
		return 0;
	}
	for(int i = 1; i <= m; ++i){
		ans[i] = i;
		if(i > n - book[i] + 1){
			over();
			return 0;
		}
	}
	solve();
	return 0;
}
相关标签: acm竞赛