1 条题解
-
0
一、思路分析(超详细)
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. 解题步骤
- 输入处理:读取测试用例数t,依次处理每组S和T;
- 计数统计:对每组S、T,分别统计26个小写字母的出现次数(存入数组a、b);
- 排序消除种类干扰:将计数数组a、b排序(升序);
- 一致性校验:逐位比较排序后的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; // 程序正常结束 }三、代码关键细节补充
- 数组大小选择:定义
a[30]而非a[26],是为了避免索引越界(如循环时误写i<30),实际仅使用前26位(对应a-z); - 排序的意义:排序后,字符的“种类”被消除(比如S的a出现2次、b出现3次,T的x出现2次、y出现3次,排序后数组均为[0,0,...2,3]),仅保留次数的分布特征;
- 初始化的重要性:每次处理新用例前必须清空
a和b,否则上一轮的计数会残留,导致统计错误; - 数据范围兼容:
#define int long long是为了兼容可能的大计数(如字符串长度达2e5,单个字符出现次数可达2e5,int已足够,但long long更安全); - 效率分析:
- 统计次数: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),...]; - 排序后
a和b均为[0,0,...,1,1,1,2,...] → 比较相等,输出Yes。
以样例2为例:
- chokudai和redcoder的计数数组排序后不一致 → 输出No。
该逻辑完全匹配样例输出,验证了思路的正确性。
- 1
信息
- ID
- 5476
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 60
- 已通过
- 19
- 上传者