Contestant. Rank 720. Unrated.

划水，打卡，三题，结束（（

A. Walking Boy

题意

给定一个升序排序的数组 \(a\)，\(a_i \in [0, 1440]\)，在数组第一位插入 \(0\)，最后一位插入 \(1440\)，输出是否有两个相邻数的差值大于等于 \(120\)。

思路

如题。

时间复杂度：\(O(n)\)

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int a[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t, n;
    cin >> t;
    while(t --){
        cin >> n;
        for(int i=1;i<=n;i++){
            cin >> a[i];
            a[i] = min(a[i], 1440ll);
        }
        int cnt = 0;
        a[n + 1] = 1440;
        for(int i=1;i<=n + 1;i++) cnt += (a[i] - a[i - 1]) / 120;
        cout << (cnt >= 2 ? "YES\n" : "NO\n");
    }
}

你怕是不想让我看懂（

H. Beppa and SwerChat

题意

给定两个时间段的好友列表，列表按照最后一条消息的时间降序排序。输出至少有多少人在两个时间段内发了消息。

思路

很显然，若发送了消息，那么这个人是从当前位置移动到第一个位置的。

或者更具体地说，我们从后往前遍历 \(b\) 数组，那么只需找到第一对相邻的数，满足在 \(a\) 数组的位置不符合要求即可。

当然，我们可以记录 \(a\) 中元素对应的下标来使查询复杂度降到 \(O(1)\)。

时间复杂度：\(O(n)\)

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int a[N], b[N];

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t;
    cin >> t;
    while(t --){
        int n;
        cin >> n;
        for(int i=0;i<n;i++){
            int cur;
            cin >> cur;
            a[cur] = i;
        }
        for(int i=1;i<=n;i++) cin >> b[i];
        int cnt = n;
        for(int i=n;i>=1;i--){
            cnt --;
            if(a[b[i - 1]] > a[b[i]]) break;
        }
        cout << cnt << '\n';
    }
}

捏码，怎么就WA了

L. Controllers

题意

给定一个由 \(+, -\) 符号组成的字符串，对于 \(t\) 组询问，给定两个数 \(a, b\)，输出是否存在 \(a, b\) 的一个序列，使其带入表达式后值为 \(0\)。

思路

显然，我们有两个选择可以让最后的值为 \(0\)：

选择任意数，\(+-\) 任意次后答案一定是 \(0\)；
将 \(a, b\) 进行配对，用最小公倍数找出合法配对，进行“抵消”。

我们不妨统计 \(+-\) 的个数，记 \(pl\) 为个数的最小值，\(mi\) 为个数的最大值，并令 \(a\) 为 \(\max(a, b)\)，\(b\) 为 \(\min(a, b)\)；然后，我们计算出 \(lcm(a, b)\)，那么 \(lcm / a\) 个个数较少的符号和 \(lcm / b\) 个个数较多的符号即可进行配对。

考虑到两种配对方法的个数较少，且无法确定需要配对几次，所以我们不妨直接枚举所有 \(a, b\) 的配对，找出是否存在一种配对，使剩余的两种符号个数相同。若相同，我们直接选择第一种配对方式配对即可。

时间复杂度：\(O(n)?\)

对应AC代码

#include<bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e5 + 10, inf = 0x3f3f3f3f, mod = 998244353;

int gcd(int a, int b) {
    while (b != 0) {
        int tmp = a;
        a = b;
        b = tmp % b;
    }
    return a;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, q;
    string op;
    cin >> n >> op >> q;
    int pl = 0;
    for(char e : op) if(e == '+') pl ++;
    int mi = n - pl;
    int tmp = min(pl, mi);
    mi = max(pl, mi);
    pl = tmp;
    while(q --){
        int a, b;
        cin >> a >> b;
        tmp = min(a, b);
        a = max(a, b);
        b = tmp;
        if(pl == mi){
            cout << "YES\n";
            continue;
        }
        int lcm = a * b / gcd(a, b);
        int pa = lcm / a, pb = lcm / b;
        int t = min(pl / pa, mi / pb);
        bool f = false;
        for(int i=1;i<=t;i++){
            if(pl - i * pa == mi - i * pb){
                f = true;
                break;
            }
        }
        cout << (f ? "YES\n" : "NO\n");
    }
}

人类的智慧（