首页 > 其他分享 >Codeforces Round 855 (Div

Codeforces Round 855 (Div

时间:2023-03-04 20:36:19浏览次数:56  
标签:std 855 const 字符 int Codeforces cin 字符串 Div

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

相关文章

  • Codeforces Round 855 (Div. 3)
    链接CodeforcesRound855(Div.3)A题这个题先将大写变小写然后将重复元素去除,判断是不是等于meow就可以#include<iostream>#include<algorithm>#include<cstdi......
  • Codeforces Global Round 3
    A   题解:显然就拼一下$a,b$然后再把$c$用完,记得判一下$a=b$的特殊情况。#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;consti......
  • CodeForces 1422F Boring Queries
    洛谷传送门CF传送门套路题。考虑根号分治,\(\le\sqrt{V}=447\)的质因子直接暴力ST表维护。对于\(>\sqrt{V}\)的质因子每个数最多有一个。记\(big_i\)为\(a_......
  • Codeforces Round #855 (Div. 3) E1 E2
    E1.UnforgivableCurse(easyversion)https://codeforces.com/contest/1800/problem/E1题目大意:这是这个问题的一个简单版本。在这个版本中,k始终是3。有两个长度为......
  • Codeforces Round 853 (Div. 2)(C,D)
    CodeforcesRound853(Div.2)(C,D)CC题目大意就是给你\(n\)个数,我们可以按顺序得到接下来的\(m\)个序列,每一个操作是对前面一个序列的第\(p\)个数变成\(v\),保证每次变......
  • Codeforces Round #277 (Div. 2) A B
    http://codeforces.com/contest/486/problem/AA.CalculatingFunctiontimelimitpertest1secondm......
  • Codeforces Round #279 (Div. 2) A B C
    http://codeforces.com/contest/490/problem/AA题贪心水题A.TeamOlympiadtimelimitpertest1secondmemorylimitpertest256......
  • Codeforces Round #277.5 (Div. 2) C
    题目: http://codeforces.com/contest/489/problem/CC.GivenLengthandSumofDigits...timelimitpertest1secondmemorylimitper......
  • Codeforces Round #266 (Div. 2) C
    http://codeforces.com/contest/466/problem/CC.NumberofWaystimelimitpertest2secondsmemorylimitpertest256megabytes......
  • Codeforces Round #271 (Div. 2) A B D
    http://codeforces.com/contest/474A水题枚举每个字符即可A.Keyboardtimelimitpertest2secondsmemorylimitpertest256mega......