AtCoder Beginner Contest 360 （ A~D）

A - A Healthy Breakfast

https://atcoder.jp/contests/abc360/tasks/abc360_a
水题

题意：只要R在M左侧即可

思路：

因为只要三位，所以只需要判断R在第一位或M在最后一位，有重复的情况

#include<iostream>
#include<cmath>
#include<algorithm>

using namespace std;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

	string s;
	cin >> s;

	if (s[0] == 'R')
	{
		cout << "Yes" << endl;
		return 0;
	}
	else if (s[2] == 'M')
	{
		cout << "Yes" << endl;
	}
	else
		cout << "No" << endl;

	return 0;
}

B - Vertical Reading

https://atcoder.jp/contests/abc360/tasks/abc360_b

题意：

给你两个由小写英文字母组成的字符串S和T。判断是否存在一对整数c和w，使1≤c≤w<∣S∣，且满足以下条件。这里，∣S∣表示字符串S的长度，注意w必须小于∣S∣。如果S从开始每w个字符分开，则长度至少为c的子字符串的第c个字符按顺序的连接等于T。

思路：

字符串

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string s, t;
    cin >> s >> t;
    
    bool flag = false;

    for (int i = 1; i < s.size(); i++)
    {
        vector<string> sub;
        for (int j = 0; j < s.size(); j += i)
        {
            sub.push_back(s.substr(j, i));
        }
        for (int j = 0; j < i; j++)
        {
            string ans;
            for (auto& x : sub)
            {
                if (j < x.size())
                    ans += x[j];
            }
            if (ans == t)
                flag = true;
        }
    }

    if (flag)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

补一下，暴力枚举

#include<iostream>

using namespace std;

string s, t;

void solve()
{
    cin >> s >> t;
    for (int i = 1; i < s.size(); i ++ )
    {
        for (int j = 0; j < i; j ++ )
        {
            string str;
            for (int k = j, cnt = 0; k < s.size(); k += i)
            {
                str += s[k];
            }
            
            if (str == t)
            {
                cout << "Yes" << endl;
                return;
            }
        }
    }
    cout << "No" << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    solve();

    return 0;
}

C - Move It

https://atcoder.jp/contests/abc360/tasks/abc360_c

题意：

一共有N个编号为1 ~ N的箱子，N个编号为1 ~ N的物品。物品i(1≤i≤N)在第i个箱子中，重量为W i。您可以重复执行零次或多次选择一个项目并将其移动到另一个框的操作。如果要移动的物品的重量为w，则操作的成本为w。求出使每个箱子只装一件物品所需的最小总成本。

思路：

#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int n;
int a[N], w[N];
int sum[N], mx[N];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++)
    {
        cin >> w[i];
        sum[a[i]] += w[i];
        mx[a[i]] = max(mx[a[i]], w[i]);
    }

    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        ans += sum[i] - mx[i];
    }

    cout << ans << endl;

    return 0;
}

D - Ghost Ants

二分可以
想法： 利用相对速度，将一只蚂蚁视为禁止不动，另一只蚂蚁会以两倍的速度向静止蚂蚁移动，然后利用二分
总体就是，先判断方向，然后进行二分

E - Random Swaps of Balls

期望dp