Educational Codeforces Round 160 (Rated for Div. 2)题解

发布时间:2024年01月13日

Rating Increase(Problem - A - Codeforces)

题目大意:给定一串数字,要求拆成a,b两个数,不能有前导0,同时a<b。

思路:这道题如果想着尽量均分就会出bug,最好的思路是将第一位分给a,如果后面有0全部给a,从第一位不是0的数开始分给b,当然如果第一位是0,后面紧接着一位也是0,那么a就有前导0了,就不成立。按照这个思路就可以解出答案。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		string s;
		cin>>s;
		int l=s.size();
		int a=s[0]-'0',b=0,p=1;
		for(int i=1;i<l;i++)
		{
			if(s[i]=='0'&&p) 
			{
				if(a==0) break;
				else a=a*10+(s[i]-'0');
			}
			else
			{
				p=0;
				b=b*10+(s[i]-'0');
			}
		}
		if(a>=b||p) printf("-1\n");
		else printf("%d %d\n",a,b); 
	}
}

Swap and Delete(Problem - B - Codeforces

题目大意:给定一个字符串s,我们可以进行两种操作,第一种操作是删除任意一个字符,花费为1,第二种操作是交换任意两个字符,花费为0,若干次操作后,得到一个字符串t,要求t与s每一位都不相同的情况下最小花费是多少。

思路:要使花费最小,那么就要尽可能地进行交换操作,另外还要注意到,如果删除前面的字符,后面的即使交换成相异的了,也会因为删除导致的字符前移使之不成立,所以我们先统计出0和1的个数,然后从头开始进行交换操作,每操作一次,更新一下0和1的剩余个数,一旦有一个用完,那么直接退出,因为我们这里实际进行的操作是交换,也就是两两配对,后面剩下的全是1种字符,也没办法配对。最后目前得到的字符串的长度与原字符串长度的差值即为答案。

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int t;
	scanf("%d",&t);
	while(t--)
	{
		string s;
		cin>>s;
		int a=0,b=0;
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='0') a++;
			else b++;
		}
		string t;
		//这里不能直接s[i]='1',因为此时的字符串为空字串。
		for(int i=0;i<s.size();i++)
		{
			if(s[i]=='0'&&b) 
			{
				b--,t.push_back('1');
				continue;
			}
			if(s[i]=='1'&&a) 
			{
				a--,t.push_back('0');
				continue;
			} 
			break;
		}
		int c=s.size()-t.size();
		printf("%d\n",c);
	}
}

Game with Multiset(Problem - C - Codeforces

题目大意:现有一个多集,我们可以对其执行两种操作:

1.add x,向多集中添加2^x这个数

2.get w,从多集中找出一个子集(一定要连续),使这个子集的和为w,如果能找到就输出yes,否则输出no。

共有n次操作。

思路:这里既然提到了2^x,那么很明显要从二进制的角度来进行考虑。问题的关键是这个w怎么处理,实际上我们可以从高位开始看,也即i从29开始,x>>i,获得实际上是x第i位及之前的数,比如6=(110)2,6>>1=(11)2=3,而6刚好可以由3个2拼出来。所以我们只要从高位进行。如下运算即可:

x-=min(x>>i,cnt[i])<<i;

?这里x这题实际上没什么写的,最大的坑点在于对于这个子集的理解,比如放入的元素为(1,1,2,2,3,3,3),子集并非是(1,2,2,3)这种形式,而是(1,2,3)这种就可以算作子集,所以每个元素与元素只要是相邻的,放入多少个并不是得全部用完。而且不够的后面还能补。

#include<bits/stdc++.h>
using namespace std;
int cnt[40];
int main(){
	int n;
	cin>>n;
	while(n--)
	{
		int a,x;cin>>a>>x;
		if(a==1) cnt[x]++;
		else
		{
			for(int i=29;i>=0;i--)
				x-= min(x>>i,cnt[i])<<i;
			if(x==0)
				cout<<"YES\n";
			else
				cout<<"NO\n";
		}
	}
}

文章来源:https://blog.csdn.net/m0_74120503/article/details/135567157
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。