1 条题解

  • 0
    @ 2025-12-14 11:25:48

    一、思路分析(超详细)

    1. 题目核心:操作本质拆解

    要判断字符串S能否通过两种操作变为T,首先需明确两种操作对字符串的影响:

    • 操作1(字符全局交换):选择两个不同字符c1和c2,将S中所有c1替换为c2、所有c2替换为c1。 本质是「字符重命名」——仅改变字符的“名称”(比如把a换成b、b换成a),但不改变每个字符出现次数的集合。例如S中a出现2次、b出现3次,操作1交换a和b后,b出现2次、a出现3次,次数集合仍为{2,3}。
    • 操作2(位置交换):交换S中任意两个位置的字符。 本质是「自由排列」——允许任意调整字符的位置,等价于可以将S重新排列为任意字符顺序的字符串(只要字符种类和次数不变)。例如S=abc,操作2可将其变为acb、bac等任意排列。

    2. 获胜条件推导

    结合两种操作的本质,S能变为T的核心条件是:

    • 操作2让「位置」失去意义,只需关注字符的出现次数;
    • 操作1让「字符种类」失去意义,只需关注“出现次数的多重集合”是否一致。

    “次数多重集合一致”的验证方法: 将S和T的26个小写字母出现次数分别统计为数组,对两个数组排序(消除字符种类的干扰),若排序后完全相同,则说明次数集合一致,可通过操作1+2转换;否则不可转换。

    3. 解题步骤

    1. 输入处理:读取测试用例数t,依次处理每组S和T;
    2. 计数统计:对每组S、T,分别统计26个小写字母的出现次数(存入数组a、b);
    3. 排序消除种类干扰:将计数数组a、b排序(升序);
    4. 一致性校验:逐位比较排序后的a和b,若全部相等则输出Yes,否则输出No。

    二、带详细注释的C++代码

    #include<bits/stdc++.h>  // 包含所有常用标准库(如iostream、algorithm等)
    #define int long long   // 将int类型重定义为long long(本题中无需大整数,仅为习惯)
    const int N =2e5+10;    // 定义常量N(本题未实际使用,预留数组大小)
    using namespace std;    // 使用std命名空间,避免重复写std::
    
    // 全局变量定义
    int a[30], b[30];  // a[]统计S中每个小写字母的出现次数,b[]统计T中每个小写字母的出现次数(开30是为了避免越界)
    int t;             // t表示测试用例的组数
    string s1, s2;     // s1存储输入的字符串S,s2存储字符串T
    
    signed main() {     // main函数用signed(因int被重定义为long long,兼容部分编译器)
        cin >> t;       // 读取测试用例数
        while(t--) {    // 循环处理每组测试用例
            cin >> s1 >> s2;  // 读取当前组的两个字符串S和T
            
            // 初始化计数数组:每次处理新用例前,清空a和b的所有元素(避免上一轮数据残留)
            for(int i=0; i<30; i++) {
                a[i] = 0;
                b[i] = 0;
            }
            
            // 统计字符串s1(S)中每个小写字母的出现次数
            for(int i=0; i<s1.size(); i++) {
                // s1[i]-'a'将字符(如'a')转换为0-25的索引('a'→0,'b'→1,…,'z'→25)
                a[s1[i]-'a']++;
            }
            
            // 统计字符串s2(T)中每个小写字母的出现次数
            for(int i=0; i<s2.size(); i++) {
                b[s2[i]-'a']++;
            }
            
            // 对计数数组排序:消除字符种类的干扰,只保留次数的集合特征
            // 例如a=[1,2,0,...0](a出现1次、z出现2次)排序后为[0,0,...1,1,2]
            sort(a, a+26);  // 仅排序前26位(对应a-z),后4位无意义
            sort(b, b+26);
            
            int flag = 1;   // 标记是否满足条件:1表示满足(Yes),0表示不满足(No)
            // 逐位比较排序后的计数数组,验证次数集合是否一致
            for(int i=0; i<26; i++) {
                if(a[i] != b[i]) {  // 只要有一位次数不同,说明无法转换
                    flag = 0;       // 标记为不满足
                    // 此处可加break优化,但不影响结果,仅减少循环次数
                }
            }
            
            // 根据标记输出结果
            if(flag == 1) cout << "Yes\n";
            else cout << "No\n";
        }
        return 0;  // 程序正常结束
    }
    

    三、代码关键细节补充

    1. 数组大小选择:定义a[30]而非a[26],是为了避免索引越界(如循环时误写i<30),实际仅使用前26位(对应a-z);
    2. 排序的意义:排序后,字符的“种类”被消除(比如S的a出现2次、b出现3次,T的x出现2次、y出现3次,排序后数组均为[0,0,...2,3]),仅保留次数的分布特征;
    3. 初始化的重要性:每次处理新用例前必须清空ab,否则上一轮的计数会残留,导致统计错误;
    4. 数据范围兼容#define int long long是为了兼容可能的大计数(如字符串长度达2e5,单个字符出现次数可达2e5,int已足够,但long long更安全);
    5. 效率分析
      • 统计次数:O(n)(n为字符串长度,2e5级别);
      • 排序:O(26log26)(常数级,可忽略);
      • 比较:O(26)(常数级);
      • 整体时间复杂度:O(t*n),完全满足题目100%数据规模要求(t≤20,n≤2e5)。

    四、样例验证

    以样例1为例:

    • S=azzel → 字符计数:a(1)、z(2)、e(1)、l(1) → a数组为[1,0,0,...,1(e),0,...,1(l),2(z),...];
    • T=apple → 字符计数:a(1)、p(2)、l(1)、e(1) → b数组为[1,0,0,...,1(e),1(l),0,...,2(p),...];
    • 排序后ab均为[0,0,...,1,1,1,2,...] → 比较相等,输出Yes。

    以样例2为例:

    • chokudai和redcoder的计数数组排序后不一致 → 输出No。

    该逻辑完全匹配样例输出,验证了思路的正确性。

    信息

    ID
    5476
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    (无)
    递交数
    60
    已通过
    19
    上传者