Contestent. Rank 1674. Rating -30.

开局爽翻，越打越坐牢（

A. Yura's New Name

题意

给定一个由 "^" 和 "_" 构成的字符串，输出至少需要插入多少个 "^" 或 "_"，使字符串可被划分为若干个个 "^^" 和 "^_^"。

思路

首先，我们可以确定开头和结尾一定是 "^"，那么如果不是，统计数量。

其次，我们两个两个遍历，如果出现了两个 "_"，那么中间一定要插一个 "^"，连续的 "^" 我们不用管。

当然，我们需要特判一下只有一个 "^" 的情况（不难发现上面的做法恰好只漏了这个条件），这个情况只需补上一个 "^" 即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

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

void init(){}

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    if(n == 1 && s[0] == '^') {
        ans ++;
    }else {
        if (s[0] == '_') ans++;
        for (int i = 1; i < n; i++) {
            if (s[i - 1] == s[i] && s[i] == '_') ans++;
        }
        if (s[n - 1] == '_') ans++;
    }
    cout << ans << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

乱猜+签到

B. JoJo's Incredible Adventures

题意

给定一个长度为 \(n\) 的二进制字符串，依次循环将字符串右移一位，得到 \(n - 1\) 个新的字符串。

将所有字符串按照右移的位数升序从上往下排列，构成一个 \(n \times n\) 的矩阵。

输出矩阵中一个面积最大的矩形的面积，满足矩形内所有元素都是 \(1\)。

思路

首先，我们无法让断续的 \(1\) 构造出面积很大的矩形，因为中间有 \(0\)，不难发现就算只有一个 \(0\)，也会让面积大打折扣。

因此，我们贪心地认为：只有长度最长的连续 \(1\) 才能构造出面积最大的矩形。

我们通过打表找规律可以发现，这个矩形的面积是和上述连续 \(1\) 的长度有关的。

\(S = \frac{len + 1}{2}(\frac{len}{2} + 1)\)。

当然，我们需要特判一下只有 \(0\) 和只有 \(1\) 的情况，前者为 \(0\) 后者为 \(n \times n\)。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

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

void init(){}

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    bool have0 = false, have1 = false;
    for(char e : s) {
        if(e == '0') have0 = true;
        else have1 = true;
    }
    if(!have0) {
        cout << n * n << '\n';
        return;
    }
    if(!have1){
        cout << 0 << '\n';
        return;
    }
    s += s;
    n *= 2;
    int mx = 0, cur = 1;
    for(int i=1;i<n;i++){
        if(s[i] == '1' && s[i - 1] == '1') cur ++;
        else{
            mx = max(mx, cur);
            cur = 1;
        }
    }
    cout << ((mx + 1) / 2) * (mx / 2 + 1) << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

贪心？其实是乱猜（x

C. Constructive Problem

题意

给定一个序列，定义 \(MEX(a)\) 为 \(a\) 中未出现的最小非负整数。定义操作为选定一个连续区间，并将区间内的所有数都更改为同一个数。在操作只能执行一次的条件下，判断是否可以将 \(MEX'(a)\) 变为 \(MEX(a) + 1\)。

思路

首先，如果 \(MEX + 1\) 在原序列中只出现一次，那么直接把他改成 \(MEX\) 即可。

其次，如果 \(MEX + 1\) 未在原序列中出现，那么我们分两种情况考虑：

最大值大于 \(MEX + 1\)，那么我们直接把最大值换成 \(MEX\) 就好了；
最大值小于等于 \(MEX + 1\)，那么 \([0, MEX)\) 中至少得有一个数的数量大于 \(1\)，然后我们将这个多余的数换成 \(MEX\) 即可。

否则，我们就需要将最左边的 \(MEX + 1\) 和最右边的 \(MEX + 1\) 之间的所有数全都替换成 \(MEX\)。

替换需要满足一个条件，即替换后 \([0, MEX)\) 内的所有数仍然至少存在一个在序列内。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

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

void init(){}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n), cnt(n + 10);
    int mx = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (a[i] <= n + 1) cnt[a[i]]++;
        mx = max(mx, a[i]);
    }
    int mex = 0;
    for (int i = 0; i <= n; i++) {
        if (!cnt[i]) {
            mex = i;
            break;
        }
    }
    if (n == 1) {
        cout << (a[0] == 1 ? "YES\n" :  "NO\n");
        return;
    }
    if (cnt[mex + 1] == 1) {
        cout << "YES\n";
        return;
    }else if (cnt[mex + 1] == 0) {
        if (mx > mex + 1)
            cout << "YES\n";
        else {
            for (int i = 0; i < mex; i++) {
                if (cnt[i] > 1) {
                    cout << "YES\n";
                    return;
                }
            }
            cout << "NO\n";
        }
        return;
    }
    vector<int> del(n + 7);
    bool pre = false;
    for (int i = 0; i < n; i++) {
        if (a[i] == mex + 1) pre = true;
        if (pre && a[i] <= n + 1) del[a[i]]++;
        if (del[mex + 1] == cnt[mex + 1]) break;
    }
    for (int i = 0; i < mex; i++) {
        if (cnt[i] == del[i]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

欠考虑了欠考虑了