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

Educational Codeforces Round 93 (Rated for Div. 2) A-D 题解

程序员文章站 2022-06-04 08:09:54
...

A. Bad Triangle

题目链接

题目原文

Educational Codeforces Round 93 (Rated for Div. 2) A-D 题解

题目大意

给出n条边,每条边有一个长度,求问是否存在3条边不能构成三角形。

解题思路

最开始看错题了,以为是是否存在3条边能构成三角形,结果又一次10分钟没切掉A.

直接判断最小的两条边边长之和是否小于等于最长的边的边长即可。

解法

如上。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T,n,a[maxn],b[maxn];
int main()
{
 	#ifdef lemon
//	freopen("A.txt","r",stdin);
	#endif
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);bool flag=false;
		for(int i=1;i<=n;i++) scanf("%d",&a[i]);
		for(int i=2;i<n;i++) if(a[1]+a[i]<=a[n])
		{
			printf("1 %d %d\n",i,n);
			flag=true;
			break;
		}
		if(!flag) printf("-1\n");
	}
	return 0;
}

B. Substring Removal Game

题目链接

题目原文

Educational Codeforces Round 93 (Rated for Div. 2) A-D 题解

题目大意

Alice和Bob玩游戏,Alice先手。游戏规则如下:每次玩家可以选择任意相同且连续的数字从数组里删除,玩家得分为删除的这串数字中1的个数。现在Alice和Bob都采取最佳策略,求问Alice的最大可能得分是多少。

解题思路

分析:没人愿意选连续的一串0,不仅得0分,而且如果将两个1之间的所有0全部选完了之后另一个人就可以获得更多的分;就算只选一部分连续的0也是没有意义的。所以两个人执行最优策略一定是都选连续的1,并且肯定要从最长的连续的1开始选。

解法

统计连续的1的长度并从大到小排序为a1,a2,a3aka_1,a_2,a_3 \dots a_k,那么Alice的得分即为a1  +a3  +a5  +a_1\;+a_3\;+a_5\;+\dots

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int T;
char str[maxn];
int a[maxn];
int main()
{
 	#ifdef lemon
	freopen("B.txt","r",stdin);
	#endif
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s",str+1);
		int n=strlen(str+1);
		a[0]=0;
		for(int i=1;i<=n;i++)
		{
			if(str[i]=='1')
			{
				int cnt=0;
				while(i<=n&&str[i]=='1')
				{
					cnt++;
					i++;
				}
				a[++a[0]]=cnt;
				i--;
			}
		}
		sort(a+1,a+a[0]+1);
		int ans=0;
		for(int i=a[0];i>0;i-=2) ans+=a[i];
		printf("%d\n",ans);
	}
	return 0;
}

C. Good Subarrays

题目链接

题目原文

Educational Codeforces Round 93 (Rated for Div. 2) A-D 题解

题目大意

给出一串数,求区间长度等于区间和的区间个数。

解题思路

将所有数都-1,那么问题转换为了求区间和为0的区间个数。

解法

开一个map记录区间长度为i的数量,然后记录每个前缀和的出现次数。如果枚举到一个位置时前缀和已经出现过了,那么说明这个位置到 上一个位置、到之前所有前缀和等于这个位置前缀和的位置 之间,区间和为0,那么答案加上这些区间个数就行。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int maxn=200005;
int T,n,a[maxn];
long long s[maxn],ans=0;
map<long long,long long> mp;
int main()
{
 	#ifdef lemon
	freopen("D.txt","r",stdin);
	#endif
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);mp.clear();ans=0;
		for(int i=1;i<=n;i++) scanf("%1d",&a[i]),a[i]--;
		mp[0]=1;
		for(int i=1;i<=n;i++)
		{
			s[i]=s[i-1]+a[i];
			if(mp[s[i]]) ans+=mp[s[i]];
			mp[s[i]]++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

D. Colored Rectangles

题目链接

题目原文

Educational Codeforces Round 93 (Rated for Div. 2) A-D 题解

题目大意

给出三种颜色的若干棍棍,每次可以选择两种不同颜色的棍棍,将他们的长度相乘加到答案上,不能重复选,求能得到的最大答案是多少。

解题思路

最开始想的是贪心,每次都取最长的两组棍棍相乘,然后顺利通过了样例,交上去WA了。最开始还以为自己贪心细节写错了,后来发现贪心的实现没有问题,那就证明了这道题贪心是错的。然后一看数据范围,只有200,于是想到dp。

解法

f[i][j][k]表示第一种颜色选了i根,第二种颜色选了j根,第三种颜色选了k根得到的最大答案是多少。转移的话就枚举上一次选了哪两根来转移就好。选的顺序是从长到短,这个可以很容易证明 (略)

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005;
int n,k,m,a[maxn],b[maxn],c[maxn];
long long f[205][205][205];
int main()
{
 	#ifdef lemon
	freopen("C.txt","r",stdin);
	#endif
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++) scanf("%d",&b[i]);
	for(int i=1;i<=k;i++) scanf("%d",&c[i]);
	sort(a+1,a+n+1,greater<int>());
	sort(b+1,b+m+1,greater<int>());
	sort(c+1,c+k+1,greater<int>());
	long long ans=0;
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			for(int p=0;p<=k;p++)
			{
				if((i-1>=0)&&(j-1>=0)) f[i][j][p]=max(f[i][j][p],f[i-1][j-1][p]+a[i]*b[j]);
				if((p-1>=0)&&(j-1>=0)) f[i][j][p]=max(f[i][j][p],f[i][j-1][p-1]+b[j]*c[p]);
				if((i-1>=0)&&(p-1>=0)) f[i][j][p]=max(f[i][j][p],f[i-1][j][p-1]+a[i]*c[p]);
//				printf("%d %d %d %lld\n",a[i],b[j],c[p],f[i][j][p]);
				ans=max(ans,f[i][j][p]);
			}
		}
	}
	printf("%lld\n",ans);
	return 0;
}