Codeforces Round #690 (Div. 3) A~E1题解

语言: CN / TW / HK

原文链接,球球不要爬我了

打着打着,学校停电了,gank了一波,应该是能写的更快的。

A 题目链接

题意

给你一个数组,按顺序输出最左、最右、次左、次右、次次左、次次右…

解题思路

水题,定义一左一右的两个指针去模拟就好了。

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
   
   
    char c=getchar();LL x=0,f=1;
    while(c<'0'||c>'9'){
   
   if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){
   
   x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=305;
LL t,n;
LL a[maxn],l,r;
int main()
{
   
   
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	t=read();
	while(t--){
   
   
		n=read();
		for(int i=1;i<=n;++i)
			a[i]=read();
		l=1,r=n;
		for(int i=1;i<=n;++i){
   
   
			if(i&1)
				printf("%lld ",a[l++]);
			else
				printf("%lld ",a[r--]);
		}
		printf("\n");
	}
	return 0;
}

B 题目链接

题意

给你一个数字串,你可以删除连续的一段,也可以不删除,问能否构成‘2020’。

解题思路

水题。最后要构成‘2020’,就要删除len-4长度的连续的串,枚举删除的位置,去判断剩余的4个数字是否能构成’2020’即可。

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
   
   
    char c=getchar();LL x=0,f=1;
    while(c<'0'||c>'9'){
   
   if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){
   
   x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=205;
char s[maxn];
LL t,n;
bool init(){
   
   
	LL len=strlen(s+1);
	if(len<4)
		return false;
	if(s[1]=='2'&&s[2]=='0'&&s[3]=='2'&&s[4]=='0')
		return true;
	if(s[1]=='2'&&s[2]=='0'&&s[3]=='2'&&s[len]=='0')
		return true;
	if(s[1]=='2'&&s[2]=='0'&&s[len-1]=='2'&&s[len]=='0')
		return true;
	if(s[1]=='2'&&s[len-2]=='0'&&s[len-1]=='2'&&s[len]=='0')
		return true;
	if(s[len-3]=='2'&&s[len-2]=='0'&&s[len-1]=='2'&&s[len]=='0')
		return true;
	return false;
}
int main()
{
   
   
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	t=read();
	while(t--){
   
   
		n=read();
		scanf("%s",s+1);
		if(init())
			printf("YES\n");
		else
			printf("NO\n");
	}
	return 0;
}

C 题目链接

题意

水题。给你一个正数x。找到一个最小的正整数,它的位数和等于x,并且所有数字都是不同的。

解题思路

很明显由1~9的数字最多构成45,要求最小,则可以将最大的数放在个位,次大的放在十位,以此类推。

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
   
   
    char c=getchar();LL x=0,f=1;
    while(c<'0'||c>'9'){
   
   if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){
   
   x=x*10+c-'0';c=getchar();}
    return x*f;
}
LL t,n;
LL get_ans(LL a){
   
   
	if(a>45)
		return -1;
	LL ans=0,cas=0;
	for(int i=9;i>=1;--i){
   
   
		if(a>=i){
   
   
			ans+=i*pow(10,cas++);
			a-=i;
		}
	}
	return ans;
}
int main()
{
   
   
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	t=read();
	while(t--){
   
   
		n=read();
		LL ans=get_ans(n);
		printf("%lld\n",ans);
	}
	return 0;
}

D 题目链接

题意

有一个数组,每次可以合并相邻的两个位置,求让数组内的所有的元素都是相等时,最小合并次数。

解题思路

要求所有元素都相等,sum为所有a[i]之和,则此时元素的值一定是sum的因子,然后去枚举因子p,将数组分为sum/p份,对于每一份来说,它们肯定是连续的一整段,去判断是否可以满足要求即可。因为最后是有sum/p份,所以合并次数为n-sum/p。

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
   
   
    char c=getchar();LL x=0,f=1;
    while(c<'0'||c>'9'){
   
   if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){
   
   x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=3005;
LL t,n,a[maxn],sum;
bool init(LL p){
   
   
	LL q=0;
	for(int i=1;i<=n;++i){
   
   
		q+=a[i];
		if(q>p)
			return false;
		if(q==p)
			q=0;
	}
	return true;
}
int main()
{
   
   
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	t=read();
	while(t--){
   
   
		n=read();
		for(int i=1;i<=n;++i)
			a[i]=read();
		sum=0;
		for(int i=1;i<=n;++i)
			sum+=a[i];
		for(int p=1;p<=sum;++p)
			if(sum%p==0&&init(p)){
   
   
				printf("%lld\n",n-sum/p);
				break;
			}
	}
	return 0;
}

E1 题目链接

题意

有n个数字,让你求有多少个三元组满足max(a[i],a[j],a[k])<=min(a[i],a[j],a[k]) (i<j<k)。

解题思路

每次枚举a[i],得到a[i],a[i]+1,a[i]+2的个数,每次从这三类数里头选出三个数字,肯定满足要求。方案数为:在a[i]中选择3个、在a[i]中选择2个且在a[i]+1中选择1个、在a[i]中选择2个且在a[i]+2中选择1个、在a[i]中选择1个且在a[i]+1中选择2个、在a[i]中选择1个且在a[i]+2中选择2个、在a[i]中选择1个且在a[i]+1中选择1个且在a[i]+2中选择1个。用排列组合去写。注意一点,由于T挺大的,直接memset会超时,没注意贡献一发罚时,先用map存一下用过哪些再去初始化。

代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cctype>
#include<iostream>
#include<algorithm>
//#include<chrono>
#include<vector>
#include<list>
#include<queue>
#include<string>
#include<set>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
#define LL long long
#define li i<<1
#define ri i<<1|1
using namespace std;
inline LL read()
{
   
   
    char c=getchar();LL x=0,f=1;
    while(c<'0'||c>'9'){
   
   if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){
   
   x=x*10+c-'0';c=getchar();}
    return x*f;
}
const int maxn=2e5+5;
LL t,n,m,k,conn[maxn+5],a;
LL C(LL n, LL r)     //返回C(n,r)
{
   
   
	if(n<r)
		return 0;
	LL sum = 1;
	for (LL i = 1; i <= r; i++)
		sum = sum*(n + 1 - i) / i;
	return sum;
}
map<int,int> use;
LL get_ans(LL pos){
   
   
	LL a=conn[pos],b=conn[pos+1],c=conn[pos+2];
	return C(a,3)+C(a,2)*C(b,1)+C(a,2)*C(c,1)+C(a,1)*C(b,2)+C(a,1)*C(c,2)+a*b*c;
}
int main()
{
   
   
	//freopen("in.txt", "r", stdin);
	//freopen("out.txt", "w", stdout);
	t=read();
	while(t--){
   
   
		for(auto it=use.begin();it!=use.end();++it){
   
   
			int fi=it->first;
			conn[fi]=0;
		}
		use.clear();
//		memset(conn,0,sizeof conn);
		n=read();
		m=3;
		k=2;
		for(int i=1;i<=n;++i){
   
   
			a=read();
			++conn[a];
			use[a]=1;
		}			
		LL ans=0;
		for(auto it=use.begin();it!=use.end();++it){
   
   
			int fi=it->first;
			ans+=get_ans(fi);
		}
		printf("%lld\n",ans);
	}
	return 0;
}

E2也是能写出来的,比赛时没想到,差一点,明天再来跟新。