AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 更多
    • 题解
    • 分享
    • 商店
    • 问答
    • 吐槽
  • App
  • 登录/注册

cf 855 div3 E1

作者: 作者的头像   tamsl3skafut ,  2023-03-19 15:02:34 ,  所有人可见 ,  阅读 28


1


每次只能跳3或者4个位置,所以对于字符串长度大于等于6的string来说就相当于每个字符都可以与其邻位的字符换位置,也就是说可以随意调换位置。这种情况下,只需遍历查找每个字符对应的出现次数是否一样即可;
对于长度小于等于5的string来说:首先是5:只有第三个字符无法变换,因此将其归类于上述判断方法即可,如果满足条件,判断S[2]是否等于T[2];对于小于3的string来说,其无法变换字符,所以直接判断是否为原string即可;对于4来说,只有0位和3位可以互换,必须满足s[1]=t[1],s[2]=t[2](因其无法互换),对于0位和3位,需要判别s0=t3&&s3=t0。
以上,代码如下:(有官方的快捷操作)

#include<iostream>
#include<cstring>
#include<map>
#include<algorithm>

using namespace std;

int t;

bool special(int n, int k, string s, string t)
{
    if(n <= 3)  //  all numbers can not be swapped
    {
        if(s != t)
            return false;
        else return true;
    }
    else if(n == 4)
    {
        if(s == t) return true;
        else
        {
            if(s[1] == t[1] && s[2] == t[2])  //  these number can not be swapped
            {
                if(s[0] == t[3] && s[3] == t[0])  // can be swapped
                    return true;
                else return false;
            }
            else return false;
        }
    }
}

void solve()
{
    int n, k;
    string s, t;
    cin >> n >> k;
    cin >> s >> t;

    if(n < 5)
    {
        if(special(n, k, s, t)) cout << "Yes" << endl;
            else cout << "No" << endl;
    }
    else
    {
        map<char, int> cnt;

        for(auto x : s)
            cnt[x] ++;

        for(auto x : t)
            cnt[x] --;

        bool ok = true;
        for(auto [c, x] : cnt)
            ok &= x == 0;

        if(n == 5 && ok == true) 
        {
            if(s[2] != t[2])
                cout << "No" << endl;
            else cout << "Yes" << endl;
        }
        else cout << (ok ? "Yes" : "No") << endl;
    }
}

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

    return 0;
}

0 评论

你确定删除吗?
1024
x

© 2018-2023 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息