https://atcoder.jp/contests/abc243

A - Shampoo

对总和取模，然后再比较取模后的数在哪个区间。

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second

using namespace std;

const int N = 2e5 + 10;
typedef pair<int, int> PII;

int v, a, b, c;

int main()
{
    cin >> v >> a >> b >> c;

    b += a; c += b;

    int t = v % c;
    if(t >= 0 && t < a) puts("F");
    else if(t < b) puts("M");
    else puts("T");

    return 0;
}

B - Hit and Blow

暴力枚举

数据范围为1000，每个数扫描一遍复杂度为O($n^2$)，能过。

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second

using namespace std;

const int N = 2e5 + 10;
typedef pair<int, int> PII;

int t, n;
int a[N], b[N];

int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> a[i];
    for(int i = 0; i < n; i ++) cin >> b[i];

    int res1 = 0, res2 = 0;
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
        {
            if(a[i] == b[j])
            {
                if(i == j) res1 ++;
                else res2 ++;
                break;
            }
        }

    cout << res1 << endl << res2 << endl;

    return 0;
}

C - Collision 2

贪心

贪心策略：对于每一个y轴上的区间，总取左端点为指向右边最小值，右端点为x指向左边的最大值，如果左端点和右端点同时存在且右端点大左端点，说明找到一组可以碰头的解。复杂度最高为对y轴排序用的O(nlogn)。

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second

using namespace std;

const int N = 2e5 + 10, INF = 2e9;
typedef pair<int, int> PII;
typedef pair<int, PII> PIP;

int t, n;
PIP g[N];
PII res[N]; //y轴区间
string s;

bool cmp(const PIP a, const PIP b)
{
    if(a.y.x != b.y.x) return a.y.x < b.y.x;
    return a.x < b.x;
}

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++) scanf("%d%d", &g[i].x, &g[i].y.x);
    cin >> s;

    for(int i = 0; i < n; i ++)
        if(s[i] == 'R') g[i + 1].y.y = 1;
        else g[i + 1].y.y = -1;

    sort(g + 1, g + n + 1, cmp);

    for(int i = 0; i <= n; i ++) res[i].x = -1, res[i].y = INF;  //初始化

    int idx = 0;
    g[0].y.x = -1;
    bool flag = false;
    for(int i = 1; i <= n; i ++)
    {
        if(g[i].y.x != g[i - 1].y.x) idx ++;
        if((res[idx].y == INF || res[idx].y < g[i].x) && g[i].y.y == -1)  //左端点
            res[idx].y = g[i].x;
        if((res[idx].x == -1 || res[idx].x > g[i].x) && g[i].y.y == 1)  //右端点
            res[idx].x = g[i].x;

        if(res[idx].x != -1 && res[idx].y != INF && res[idx].x < res[idx].y)
        {
            flag = true;
            break;
        }
    }

    if(flag) puts("Yes");
    else puts("No");

    return 0;
}

D - Moves on Binary Tree

完全二叉树 + 栈

数据还没超出限制时按题目要求模拟完全二叉树节点的上浮和下沉操作即可，而当数据超出$10^{18}$的限制之后，就需要用到栈，遇到下沉操作则入栈，如果遇到上浮操作时栈不为空，出栈抵消即可。

#include <bits/stdc++.h>
#define ll long long
#define x first
#define y second

using namespace std;

const ll N = 2e5 + 10, INF = 1e18;
typedef pair<int, int> PII;

int n;
stack<char> q;
string s;
ll x;

int main()
{
    cin >> n >> x >> s;

    for(int i = 0; i < n; i ++)
    {
        if(s[i] == 'U')
        {
            if(x == 1) continue;
            if(q.size())
            {
                q.pop();
                continue;
            }
            x >>= 1;
        }
        else if(s[i] == 'L')
        {
            if((x << 1) > INF)
            {
                q.push('L');
                continue;
            }
            x = x << 1;
        }
        else
        {
            if((x << 1 | 1) > INF)
            {
                q.push('R');
                continue;
            }
            x = x << 1 | 1;
        }
    }

    cout << x << endl;

    return 0;
}

第四题到最后五分钟才想出用栈，最后两分钟才a掉。看来是刷题太少，见的题型不够多，思维还比较局限。