csp信奥赛C++高频考点专项训练之字符串 --【字符统计】：「MYOI-R3」字符串
csp信奥赛C++高频考点专项训练之字符串 --【字符统计】：「MYOI-R3」字符串
题目描述
给定字符串s , t s,ts,t。
现在你要在s , t s,ts,t中删除一些字符并将它们重新排列使s = t s=ts=t。
问操作后的∣ s ∣ |s|∣s∣（即字符串s ss的长度）最大是多少？
输入格式
第一行一个字符串s ss。
第二行一个字符串t tt。
输出格式
一行一个整数，表示操作后的∣ s ∣ |s|∣s∣的最大值。
输入输出样例 1
输入 1
abc bc输出 1
2输入输出样例 2
输入 2
aaaaa bbbbb输出 2
0说明/提示
在第一个样例中，将a删除，留下bc。
此时∣ s ∣ = 2 |s|=2∣s∣=2，可以证明这是最优解。
在第二个样例中，将aaaaa删除，留下空串。
将bbbbb删除，留下空串。
此时∣ s ∣ = 0 |s|=0∣s∣=0，可以证明这是最优解。
本题采用捆绑测试。
记n = max ( ∣ s ∣ , ∣ t ∣ ) n=\max(|s|,|t|)n=max(∣s∣,∣t∣)。
| Subtask \text{Subtask}Subtask | $n\le $ | 特殊性质 | 总分值 |
|---|---|---|---|
| 1 11 | 10 1010 | 无 | 25 2525 |
| 2 22 | 10 5 10^5105 | A \text{A}A | 25 2525 |
| 3 33 | 10 5 10^5105 | B \text{B}B | 25 2525 |
| 4 44 | 10 5 10^5105 | 无 | 25 2525 |
对于100 % 100\%100%的数据，1 ≤ ∣ s ∣ , ∣ t ∣ ≤ 10 5 1 \le |s|,|t| \le 10^51≤∣s∣,∣t∣≤105，字符串均由小写字母组成。
特殊性质A \text{A}A：s ss是一个a ∼ z \text{a}\sim\text{z}a∼z的排列。
特殊性质B \text{B}B：保证s i , t i ∈ { a , b } s_i,t_i\in\{\text{a},\text{b} \}si,ti∈{a,b}。
思路分析
题目要求：删除两个字符串中的部分字符，并重新排列剩下的字符，使得两个字符串相等。由于可以任意重排，最终字符串的字符组成只取决于两个字符串中字符出现的频数。对于每个字符，能保留的最大数量就是两个字符串中该字符出现次数的最小值。因此，答案等于所有字符的min(cnt_s[ch], cnt_t[ch])之和。
实现步骤：
- 读入字符串
s和t。 - 用两个长度为 26 的数组
a和b分别统计s和t中每个字母出现的次数。 - 遍历 26 个字母，累加
min(a[i], b[i])到答案。 - 输出答案。
时间复杂度 O(|s|+|t|)，空间 O(1)。
代码实现
#include<bits/stdc++.h>usingnamespacestd;string s,t;//两个输入字符串inta[26];//桶a：统计s中每个字母出现次数intb[26];//桶b：统计t中每个字母出现次数intans=0;//最终能得到的字符串长度intmain(){cin>>s>>t;//读入字符串//统计s中每个字母的出现次数for(inti=0;i<s.size();i++){a[s[i]-'a']++;//将字符转换为0~25的下标并累加}//统计t中每个字母的出现次数for(inti=0;i<t.size();i++){b[t[i]-'a']++;}//累加每个字母的最小出现次数for(inti=0;i<26;i++){ans+=min(a[i],b[i]);//取较小值并累加}cout<<ans;//输出结果return0;}功能分析
- 输入处理：从标准输入读取两个字符串
s和t。 - 频数统计：使用两个整型数组
a和b分别记录s和t中每个小写字母（'a'~'z'）出现的次数。通过字符 - 'a'将字符映射到数组下标。 - 答案计算：遍历 26 个字母，将两个数组对应位置的最小值累加到
ans。 - 输出结果：打印
ans，即操作后字符串的最大可能长度。
该算法正确解决了问题，时间复杂度 O(|s|+|t|)，空间复杂度 O(1)，满足题目数据范围（|s|,|t| ≤ 10^5），可通过所有测试点。
【完整系列请查看专栏】：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"########## 一站式掌握信奥赛知识! ##########";cout<<"############# 冲刺信奥赛拿奖! #############";cout<<"###### 课程购买后永久学习，不受限制! ######";return0;}【秘籍汇总】（完整csp信奥赛C++学习资料）：
1、csp/信奥赛C++，完整信奥赛系列课程（永久学习）：
https://edu.csdn.net/lecturer/7901 点击跳转
2、CSP信奥赛C++竞赛拿奖视频课：
https://edu.csdn.net/course/detail/40437 点击跳转
https://edu.csdn.net/course/detail/41081 点击跳转
3、csp信奥赛高频考点知识详解及案例实践：
CSP信奥赛C++动态规划：
https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转
CSP信奥赛C++标准模板库STL：
https://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转
信奥赛C++提高组csp-s知识详解及案例实践：
https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转
4、csp信奥赛冲刺一等奖有效刷题题解：
信奥赛C++普及组CSP-J一等奖通关刷题题单及题解：
https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转
信奥赛C++提高组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转
信奥赛C++提高组csp-s初赛&复赛真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转
5、GESP C++考级真题题解：
GESP(C++ 一级+二级+三级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转
GESP(C++ 四级+五级+六级)真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转
GESP(C++ 七级+八级)真题题解（持续更新）：
https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}