比赛链接:https://codeforc.es/contest/1722

在学校里,一直没时间参赛。

在D题上出现了比较大的问题。把题拆开来考虑结果导致有些麻烦。
前三题中规中矩吧,基本一次过,题并不是很难

A题:大意是有个人叫Timur,对于他名字的任意排列都是对的。求输出的字符串是否正确。直接map存

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
map<char,int>mp;
void solve()
{
	mp.clear();
	int n;
	cin>>n;
	string a;
	cin>>a;
	if(n!=5) cout<<"NO"<<endl;
	else {
		for(int i=0;i<n;i++)
			mp[a[i]]=1;
		if(mp['T']==1&&mp['i']==1&&mp['m']==1&&mp['r']==1&&mp['u']==1)
			cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

 

B题:大意是给出2行n列的字符串,也就是两个串。每个字符有三种颜色,RG, or B,,其中G和B不能被识别。因为眼盲,所以求出这个人看这两个字符串是否是一样的。

直接两两比较每一个字符,如果存在一个r,那么另一个必定要是r,否则直接no

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void solve()
{
	int n;
	cin>>n;
	string a,b;
	cin>>a>>b;
	int i=0;
	for(;i<a.size();i++)
	{
		if(a[i]=='R'&&b[i]!='R'||b[i]=='R'&&a[i]!='R')
			break;
	}
	if(i<a.size())	cout<<"NO"<<endl;
	else cout<<"YES"<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

 

C题:大意是有三个人,每个人给出n个字符串。如果有一个字符串出现了一次,那个人+3分,出现了两次,两人分别+1分,出现了3次不加分。

思路:直接map存储每个字符串出现的次数,这里最开始想用set结果set.count()并不能很好的识别字符串出现的数量,所以用map来存的。

code:

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
vector<string> ve[4];
map<string,int> mp;
void solve()
{
	for(int i=0;i<4;i++) ve[i].clear();
	mp.clear();

	int n;
	cin>>n;
	for(int i=1;i<=3;i++)
	{
		for(int j=0;j<n;j++)
		{
			string c;
			cin>>c;
			ve[i].push_back(c);
            mp[c]++;
		}
	}
	int num[4]={};
	for(int i=1;i<=3;i++)
	{
		for(int j=0;j<ve[i].size();j++)
		{
			if(mp[ve[i][j]]==1) num[i]+=3;
            else if(mp[ve[i][j]]==2) num[i]+=1;
		}
	}
	for(int i=1;i<=3;i++)
		printf("%d%c",num[i],i==3?'\n':' ');
}
int main()
{
//	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

 

D题:大意是给出一个字符串,每个元素都是L或者R,如果是L它的值就是它左边元素的数量,如果是R,它的值就是它右边元素的数量。你可以通过操作N次改变使得和s最大,每次k对应1-n,输出每一次的最大和s。

思路:很明显的一个贪心题,如果它在左边,那么它为R才能值最大,右边亦然。贪心的看待每一个逆向L或R,离边界越近的优先改变。ve存储它离边界的距离,然后直接计算出另一侧。这个题最开始的操作并不是很好,把题的左右拆开然后用的双指针做的。其实可以把右边靠右的边界转换为左边靠左的边界,然后直接排序来做。网上的答案比我写的更精简一些,计算上更加简洁。

my code:

 

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize(2)
#define ll long long
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}
void solve()
{
	int n;
	cin>>n;
	string a;
	cin>>a;
	ll sum = 0;
	vector<int> ve;
	for(int i=0;i<a.size();i++)
		if(a[i]=='L') sum+=i;
		else if(a[i]=='R') sum+=n-i-1;

	if(n%2)
	{
		for(int i=0;i<n/2;i++)
			if(a[i]=='L') ve.push_back(i);
		for(int i=n/2+1;i<n;i++)
			if(a[i]=='R') ve.push_back(n-i-1);
	}else
	{
		for(int i=0;i<n/2;i++)
			if(a[i]=='L') ve.push_back(i);
		for(int i=n/2;i<n;i++)
			if(a[i]=='R') ve.push_back(n-i-1);
	}
	
	sort(ve.begin(),ve.end());

	int p=0;
	for(int i=1;i<=n;i++)
	{
		if(p<ve.size()) 
			sum-=ve[p],sum+=(n-ve[p]-1);
		p++;
		cout<<sum<<' ';
	}
	cout<<endl;
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
}

Internet code:

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
	        cin>>n;
		string s;
		cin>>s;
		int d[n];
		long long c=0;
		for(int i=0;i<n;i++){
			if(s[i]=='L')d[i]=i;
			else d[i]=n-1-i;
			c+=d[i];
		}
		sort(d,d+n);
		for(int i=0;i<n;++i){
			if(n-1-2*d[i]>0)c+=n-1-2*d[i];
			cout<<c<<" ";
		}
		cout<<endl;
	
	}}