Codeforces Round 685 (Div. 2) - C. String Equality

Solost

2023 年 05 月 18 日

195 次浏览

暂无评论

1455字数

题目题解

## 题目链接

[链接](https://codeforces.com/problemset/problem/1451/C)

## 题目大意

给你长度为n的两个字符串，你有两种操作，第一个操作你可以交换`a[i], a[i + 1]`，操作二，你可以将连续的`k`个相同的字符自增1，例如`a->b, b->c`,最大到z

## 题解

### 错误示范：

刚开始想的是排序一下，然后用双指针扫描，如果a提供的字符串不够就不行，然后这个错误点在于，如果b字符串的最后一个字符，它可以由a的任何字符补过来，但是我的写法会只管最后的情况。

```cpp
void solve()
{
    cin >> n >> k;
    cin >> a >> b;
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i = 0; i < n; i++) {
        if (a[i] == b[i])
            continue;
        if (a[i] > b[i]) {
            cout << "No\n";
            return;
        }
        int j = i, l = i;
        while (j < n && j - i + 1 <= k && a[j] == a[i]) j++;
        while (l < n && l - i + 1 <= k && b[l] == b[i]) l++;
        if (j != l || l - i != k) {
            cout << "No\n";
            return;
        }
        i = l - 1;
    }
    cout << "Yes\n";
}
```

### 自己写的正解

看了下题解，题解说要单个字母统计，遍历字母就行。那么我们统计好两个字符串里面字符的个数，b串从后往前找，如果b串的某个字母不能被消成0，那么他就不合法。	然后就是模拟

```cpp
int n, k;
string a, b;

void solve()
{
    cin >> n >> k;
    cin >> a >> b;
    map<int, int> v1, v2;
    for (auto x : a) {
        v1[x - 'a']++;
    }
    for (auto x : b) {
        v2[x - 'a']++;
    }
    for (int i = 25; i >= 0; i--) {
        if (!v2[i]) continue;
        for (int j = i; j >= 0; j--) {
            if(!v1[j]) continue;
            if (i == j) {
                int t = min(v1[i], v2[i]);
                v1[i] -= t;
                v2[i] -= t;
                continue;
            }
            if (v2[i] < k && v2[i]) {//注意v2[i] == 0时候不能算不合法情况
                cout << "NO\n";
                return;
            }
            int t = min((v2[i] / k), (v1[j] / k)) * k;
            v2[i] -= t;
            v1[j] -= t;
            if(!v2[i]) break;
        }
        if (v2[i]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
}
```

### 官方题解

官方题解就简单多了，统计每个字符出现的次数，如果当前a能提供的字符不够b的那就直接输出不合法，或者是当前的a字符串的字符匹配完b以后，剩下的字符不能被k整除，那就没办法提供给下一个字符用，也是非法情况。如果合法就给下一个字符串加上这次没用完的字符数目。

```cpp
#include <bits/stdc++.h>
using namespace std;

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int t;
    cin >> t;
    while(t--) {
        int i, n, k; string a, b;
        cin >> n >> k >> a >> b;
        array<int, 27> have{}, need{};
        for(auto& c: a)
            have[c-'a']++;
        for(auto& c: b)
            need[c-'a']++;
   
        bool bad = false;
        for(i = 0; i < 26; i++) {
            if(have[i] < need[i] || (have[i] -= need[i]) % k)
                bad = true;
            have[i+1] += have[i];
        }
        cout << (bad? "No" : "Yes") << '\n';
    }
    return 0;
}
```

最后修改：2023 年 05 月 18 日