题目链接
题目大意
给你长度为n的两个字符串,你有两种操作,第一个操作你可以交换a[i], a[i + 1]
,操作二,你可以将连续的k
个相同的字符自增1,例如a->b, b->c
,最大到z
题解
错误示范:
刚开始想的是排序一下,然后用双指针扫描,如果a提供的字符串不够就不行,然后这个错误点在于,如果b字符串的最后一个字符,它可以由a的任何字符补过来,但是我的写法会只管最后的情况。
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,那么他就不合法。 然后就是模拟
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整除,那就没办法提供给下一个字符用,也是非法情况。如果合法就给下一个字符串加上这次没用完的字符数目。
#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;
}