AtCoder Beginner Contest 360_(atcoder beginner contest 360)题解

A - A Healthy Breakfast

题目大意：给一个长度为3的由R,S,M组成的字符串，如果R在M的左边输出Yes,否则输出No。

思路：直接判断就行。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	string s;
	cin>>s;
	int flag=0;
	for(int i=0;i<3;i++){
		if(s[i]=='R'){
			flag=1;
		}else if(s[i]=='M'&&flag==1){
			flag=2;
		}
	}
	if(flag==2)cout<<"Yes"<<endl;
	else cout<<"No"<<endl;
	return 0;
}

B - Vertical Reading

题目大意：需要找到两个整数 c 和 w，使得 1≤c≤w<∣S∣，并且满足以下条件：如果将字符串 S 从开始处每隔 w 个字符分割开，那么将这些子串中长度至少为 c 的子串的第 c 个字符按顺序连接起来，得到的连接结果是字符串 T。这里， ∣S∣ 表示字符串 S 的长度。注意， w 必须小于 ∣S∣。

思路：直接暴力查找，在符合条件的w中不断搜索符合情况的c。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	string S,T;
	cin>>S>>T;
	int n1=S.length(),n2=T.length(),flag=0;
	for(int i=1;i<n1;i++){
		if(n1/i>n2)continue;
		else if(n1/i<n2&&n1%i==0)continue;
		else{
			if(n1/i==n2){
				//cout<<i<<endl;
				for(int j=n1%i-1;j<i;j++){
					if(S[j]==T[0]){
						//cout<<j<<endl;
						flag=0;
						for(int p=1;p<n2;p++){
							if(S[p*i+j]!=T[p]){
								flag=1;
								break;
							}
						}
						if(flag==0){
							cout<<"Yes"<<endl;
							return 0;
						}
					}
				}
			}else{
				//cout<<i<<endl;
				int n=n1%i;
				for(int j=0;j<n;j++){
					if(S[j]==T[0]){
						flag=0;
						for(int p=1;p<n2;p++){
							if(S[p*i+j]!=T[p]){
								flag=1;
								break;
							}
						}
						if(flag==0){
							cout<<"Yes"<<endl;
							return 0;
						}
					}
				}
			}
		}
	}
	cout<<"No"<<endl; 
	return 0;
}

C - Move It

题目大意：有 N 个箱子，编号为 1 到 N，还有 N 个物品，编号为 1 到 N。物品 i （1≤i≤N）在箱子 Ai 中，重量为 Wi 。你可以反复执行选择一个物品并将其移动到另一个箱子零次或多次的操作。如果被移动的物品的重量是 w，则该操作的成本为 w。找出使每个箱子恰好包含一个物品所需的最小总成本。

思路：对于Ai，如果存在Aj==Ai(i!=j)，则在所有都要等于Ai的物品中，除了最大的重量外，其他都算作成本。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,int>mp;
int a[100007],b[100007];
int main()
{
	int n;
	cin>>n;
	int x;
	for(int i=0;i<n;i++){
		cin>>a[i];
		b[a[i]]++;
	}
	ll ans=0;
	for(int i=0;i<n;i++){
		cin>>x;
		if(b[a[i]]>1){
			if(mp[a[i]]==0)mp[a[i]]=x;
			else{
				ans+=min(mp[a[i]],x);
				mp[a[i]]=max(mp[a[i]],x);
			}
		}
	}
	cout<<ans<<endl;
	return 0;
}

D - Ghost Ants

题目大意：

有N只蚂蚁位于一个数轴上（位置都不同），标号为1到N。蚂蚁i（1≤i≤N）从坐标X_i开始，面向正向或负向。蚂蚁面向的方向由长度为N的二进制字符串S表示，若S_i为0，则蚂蚁i面向负向；若S_i为1，则面向正向。当前时间为0，蚂蚁们以每单位时间1个单位的速度在各自的方向上移动，直到时间（T+0.1）。如果多个蚂蚁到达相同的坐标，它们将互相穿过，而不改变方向或速度。在时间（T+0.1）后，所有蚂蚁停止移动。找出在时间（T+0.1）之前，蚂蚁i和j（1≤i<j≤N）互相穿过的蚂蚁对（i,j）的数量。

思路：将向正向和负向的坐标分别存在两个不同的数组a,b上，对两个数组从小到大排序，然后循环负向的数组，采用双指针p1,p2,找到比负向的数组小0到2*t的正向数组里的元素数量，然后相加。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll X,a[200007],b[200007];
int main()
{
	ll n,t;
	cin>>n>>t;
	string s;
	cin>>s;
	int t1=0,t2=0;
	for(int i=0;i<n;i++){
		cin>>X;
		if(s[i]=='0'){
			a[t1++]=X;
		}else{
			b[t2++]=X;
		}
	}
	sort(a,a+t1);
	sort(b,b+t2);
	t*=2;
	int p1=0,p2=0;
	ll ans=0;
	for(int i=0;i<t1;i++){
		while(p1<t2&&a[i]>b[p1]){
			p1++;
		}
		while(p2<t2&&a[i]-b[p2]>t){
			p2++;
		}
		if(p1>p2)ans+=p1-p2;
		//cout<<ans<<endl;
	}
	cout<<ans<<endl;
	return 0;
}

思路也不好讲，看不懂思路，大家可以看看代码，第四题是在截止后3分钟写好的，又是差几分钟......