Codeforces Round #754 (Div. 2)

 2021/11/16 traing 

今天vp了一场,发现问题还是挺大的

A. A.M. Deviation

题目大意:给定三个数字a,b,c;可以更改abc中任意两个数字,一个加1一个减1,求最终我们可以获得的最小值

解题思路:分析之后发现只有+3和-3两个操作,所以如果我们%3 == 0的时候可以直接输出0,那么%3 != 0的时候可以输出1

#include <bits/stdc++.h>
using namespace std;
int T,n;
int a,b,c;
void solve()
{
	scanf("%d %d %d",&a,&b,&c);
	int mul = a + c - 2 * b;
	mul %= 3;
	mul += 3;
	mul %= 3;
	printf("%d\n",min(mul,3 - mul)); 
}
int main()
{
	T = 1;
	scanf("%d",&T);
	while(T--)
	{
		solve();
	}
	return 0;
}
Codeforces Round #754 (Div. 2)

B.Reverse Sort

题目大意:给定一个01串,在每一个子串中可以相对反转,最终获得一个排序过后的01串

解题思路:找到所有位置和本来不符合的01串的位置,然后我们把这些位置记录下来之后直接输出即可

#include <bits/stdc++.h>
using namespace std;
int T,n;
string str;
string pre;
vector<int> G;
void solve()
{
	G.clear();
	cin >> n;
	cin >> str;
	int cnt = 0;
	for(int i = 0;i < str.length();++i)
	{
		if(str[i] == '0') cnt++;
	}
	pre = "";
	for(int i = 0;i < str.length();++i)
	{
		if(i <= cnt - 1) pre += "0";
		else pre += "1";
	}
	for(int i = 0;i < str.length();++i)
	{
		if(str[i] != pre[i]) G.emplace_back(i + 1);
	}
	if(G.size() == 0)
	{
		cout << "0"<<"\n";
	}
	else
	{
		cout << "1" <<"\n";
		cout << G.size() <<" ";
		for(auto h : G)
		{
			cout << h <<" ";
		}
		cout << "\n";
	}
}
int main()
{
	T = 1;
	scanf("%d",&T);
	while(T--)
	{
		solve();
	}
	return 0;
}
Codeforces Round #754 (Div. 2)

C Dominant Character

题目大意:给定一个字符串,字符串中仅包含‘a’,‘b’,‘c’,我们需要严格找到一个字串使得字串长度大于等于2,并且a的数量要严格大于bc,寻找一个最小字串,如果找不到这个字串则输出-1

解题思路:首先我们通过分析可以发现,形似'aa','aba','aca','abca'‘acba’这些串可以是直接符合答案的,但是如果有‘abba'这样子的字串,后面在加上'cca',还可以构成一个类似的字串,所以最后我们只需要存储A的位置然后遍历之后就可以写出来了,在写的时候注意边界判断的问题,在这一个问题上面错了好多次

#include <bits/stdc++.h>
#define FAST std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
int T,n;
string str;
string pre;
vector<int> G;
int num[10];
void solve()
{
	G.clear();
	cin >> n;
	cin >> str;
	for(int i = 0;i < str.length();++i)
	{
		if(str[i] == 'a')
		{
			G.emplace_back(i);
		}
	}
	int ans = 0x3f3f3f3f;
	for(int i = 1;i < G.size();++i)
	{
		if(G[i] - G[i - 1] <= 2)
		{
			ans = min(ans,G[i] - G[i - 1] + 1);
		}
		else if(G[i] - G[i - 1] == 3)
		{
			if(str[G[i - 1] + 1] != str[G[i - 1] + 2]) ans = min(ans,4);
			else
			{
				if(i != G.size() - 1 && G[i + 1] - G[i] == 3 && str[G[i + 1] - 1] != str[G[i - 1] + 1])
				{
					ans = min(ans,7);
				}
			}
 		}
	}
	if(ans == 0x3f3f3f3f) ans = -1;
	cout << ans <<"\n";
}
int main()
{
	//FAST
	T = 1;
	cin >> T;
	while(T--)
	{
		solve();
	}
	return 0;
}
Codeforces Round #754 (Div. 2)

还有一种更加简便的写法

#include <bits/stdc++.h>
#define FAST std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
int T,n;
string str;
string pre;
vector<int> G;
int num[10];
string com[] = {"aa","aba","aca","abca","acba","abbacca","accabba"};
void solve()
{
	cin >> n;
	cin >> str;
	for(auto f:com)
	{
		if(str.find(f) != str.npos)
		{
			cout << f.length()<<"\n";
			return;
		}
	}
	cout << "-1" <<"\n";
}
int main()
{
	//FAST
	T = 1;
	cin >> T;
	while(T--)
	{
		solve();
	}
	return 0;
}
Codeforces Round #754 (Div. 2)


上一篇:Codeforces 赛时没想出来的思维题集


下一篇:Codeforces Round #755 div.1 AB(第一把div1被锤记)