Problem - E2 - Unforgivable Curse (hard version)
给定一个初始字符串s和目标字符串t,我们可以对字符串s进行以下任意次操作:
对于位置\(i\),如果\(i+k+1<=s.length()\) ,那么就可以交换\(i和k或k+1\)的位置上的字符,即\(swap(s[i],s[k])\ \ or \ \ swap(s[i],s[i+k+1])\)
询问能否通过操作使得字符串s变成字符串t
题解:思维
我们经过模拟后发现,除了不能交换位置的字符之外,其他字符之间可以任意交换,我们只要检查一下在不能交换的位置上s和t字符是否相等,然后对在可以交换的位置上的字符计数即可,因为可能会有不是s原本的字符出现在t中
#include <bits/stdc++.h>
#define Zeoy std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
#define debug(x) cerr << #x << '=' << x << endl
#define all(x) (x).begin(), (x).end()
#define rson id << 1 | 1
#define lson id << 1
#define int long long
#define mpk make_pair
#define endl '\n'
using namespace std;
typedef unsigned long long ULL;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-9;
const int N = 2e5 + 10, M = 4e5 + 10;
int n, k;
void solve()
{
cin >> n >> k;
string s, t;
cin >> s >> t;
vector<int> cnt(26, 0);
for (int i = 0; i < n; ++i)
{
if (i - k < 0 && i + k >= n)
{
if (s[i] != t[i])
{
cout << "NO" << endl;
return;
}
}
else
{
cnt[s[i] - 'a']++;
cnt[t[i] - 'a']--;
}
}
for (int i = 0; i < 26; ++i)
{
if (cnt[i] != 0)
{
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
signed main(void)
{
Zeoy;
int T = 1;
cin >> T;
while (T--)
{
solve();
}
return 0;
}
标签:std,855,const,字符,int,Codeforces,cin,字符串,Div
From: https://www.cnblogs.com/Zeoy-kkk/p/17179011.html