Codeforces Round 855 (Div. 3)

A. Is It a Cat?

题意：要求：

字符串必须以只包含字母 "m "或 "M "的非空序列开始
必须紧跟由'e'或'E'字符组成的非空序列
必须紧接着仅由字符'o'或'O'组成的非空序列
必须紧接着是仅由字符'w'或'W'组成的非空序列

思路：一个一个来(WA了三发注意这几个数都要有！！！！！！)

#include <bits/stdc++.h>

using namespace std;
char a[] = {'m', 'e', 'o', 'w'};
char b[] = {'M', 'E', 'O', 'W'};

void solve() {
    int n;
    cin >> n;
    string st;
    cin >> st;
    int num = 0;
    if (st[0] != a[0] && st[0] != b[0]) {
        cout << "NO\n";
        return;
    }
    int res = 1;
    for (int i = 0; i < n; i++) {
        if (st[i] == a[num] || st[i] == b[num]) {
            continue;
        } else if (num != 3 && (st[i] == a[num + 1] || st[i] == b[num + 1])) {
            num++;
            res++;
            continue;
        } else {
            cout << "NO\n";
            return;
        }
    }
    if (num == 3 && res == 4) cout << "YES\n";
    else cout << "NO\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

B. Count the Number of Pairs

题意：a和A可以组成一对

操作：将小写字母转化成大写或者大写转化成小写

思路：分别看看aA有几个，然后看变化次数和对数

#include <bits/stdc++.h>

using namespace std;
int a[26], b[26];

void solve() {
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    int n, k;
    cin >> n >> k;
    string st;
    cin >> st;
    for (int i = 0; i < n; i++) {
        if (st[i] >= 'a' && st[i] <= 'z') {
            a[st[i] - 'a']++;
        } else {
            b[st[i] - 'A']++;
        }
    }
    int ans = 0, res = 0;
    for (int i = 0; i < 26; i++) {
        ans += min(a[i], b[i]);
        res += abs(a[i] - b[i]) / 2;
    }
    cout << ans + min(res, k) << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

C. Powering the Hero

ps：C1,C2就一起了，发现写的都能过

题意：当a[i]=0的时候就可以加前面的数，是的之前加的数最大

思路：很明显加的是之前的最大值(优先队列)(没开龙long longWA了三发)

#include <bits/stdc++.h>

using namespace std;
#define int long long

void solve() {
    int n, res = 0;
    cin >> n;
    priority_queue<int> mp;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (x > 0) {
            mp.push(x);
        } else if (!x && !mp.empty()) {
            res += mp.top();
            mp.pop();
        }
    }
    cout << res << endl;
}

signed main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D. Remove Two Letters

题意：删除两个连续的字符，问可以得到多少不同的字符串

思路：面对样例编程，假设是一样的会发现三个字符只有一个，假设两两相同会发现四个字母只有一个马，再看看发现只要a[i]==a[i+2]那么就会少一个

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int n;
    cin >> n;
    string st;
    cin >> st;
    int ans = 0;
    for (int i = 0; i < n - 2; i++) {
        if (st[i] == st[i + 2]) ans++;
    }
    cout << n - ans - 1 << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E1. Unforgivable Curse (easy version)

本来可以a的结果没考虑清楚零界点5

题意：操作：交换b串中i-j3||i-j4的；目的：b串=a串

思路：可以交换三和四就等于相邻的数可以交换，那么只需要统计数是否相等即可(特判n<=5的时候)

1.n<=3发现没法交换，直接比

2.n==4只能1和4交换23必须相等

3.n==5中间的数是不能交换的所以必须相等

#include <bits/stdc++.h>

using namespace std;
#define int long long
int a[26], b[26];

void solve() {
    int n, k;
    cin >> n >> k;
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    string s, t;
    cin >> s >> t;
    for (int i = 0; i < n; i++) {
        a[s[i] - 'a']++;
    }
    for (int i = 0; i < n; i++) {
        b[t[i] - 'a']++;
    }
    if (n <= 3) {
        if (s != t) {
            cout << "NO\n";
            return;
        }
    }
    if (n == 4) {
        if (s[1] != t[1] || s[2] != t[2]) {
            cout << "NO\n";
            return;
        }
    }
    if (n == 5) {
        if (s[2] != t[2]) {
            cout << "NO\n";
            return;
        }
    }
    for (int i = 0; i < 26; i++) {
        if (a[i] != b[i]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}

signed main() {

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

E2. Unforgivable Curse (hard version)

题意：与简单版相比就是k不一样

思路：不能变换的情况1.i+k>n 2.i-k<0

#include <bits/stdc++.h>

using namespace std;
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    string s, t;
    cin >> s >> t;
    for (int i = 0; i <= n; i++) {
        if (s[i] != t[i] && i - k < 0 && i + k >= n) {
            cout << "NO" << "\n";
            return;
        }
    }
    sort(s.begin(), s.end());
    sort(t.begin(), t.end());
    if (s == t) {
        cout << "YES" << "\n";
        return;
    }
    cout << "NO" << "\n";
}

signed main() {

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}