csp信奥赛C++高频考点专项训练之字符串 --【字符统计】：「MYOI-R3」字符串

csp信奥赛C高频考点专项训练之字符串 --【字符统计】「MYOI-R3」字符串题目描述给定字符串s , t s,ts,t。现在你要在s , t s,ts,t中删除一些字符并将它们重新排列使s t stst。问操作后的∣ s ∣ |s|∣s∣即字符串s ss的长度最大是多少输入格式第一行一个字符串s ss。第二行一个字符串t tt。输出格式一行一个整数表示操作后的∣ s ∣ |s|∣s∣的最大值。输入输出样例 1输入 1abc bc输出 12输入输出样例 2输入 2aaaaa bbbbb输出 20说明/提示在第一个样例中将a删除留下bc。此时∣ s ∣ 2 |s|2∣s∣2可以证明这是最优解。在第二个样例中将aaaaa删除留下空串。将bbbbb删除留下空串。此时∣ s ∣ 0 |s|0∣s∣0可以证明这是最优解。本题采用捆绑测试。记n max ⁡ ( ∣ s ∣ , ∣ t ∣ ) n\max(|s|,|t|)nmax(∣s∣,∣t∣)。Subtask \text{Subtask}Subtask$n\le $特殊性质总分值1 1110 1010无25 25252 2210 5 10^5105A \text{A}A25 25253 3310 5 10^5105B \text{B}B25 25254 4410 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}As 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)。代码实现#includebits/stdc.husingnamespacestd;string s,t;//两个输入字符串inta[26];//桶a统计s中每个字母出现次数intb[26];//桶b统计t中每个字母出现次数intans0;//最终能得到的字符串长度intmain(){cinst;//读入字符串//统计s中每个字母的出现次数for(inti0;is.size();i){a[s[i]-a];//将字符转换为0~25的下标并累加}//统计t中每个字母的出现次数for(inti0;it.size();i){b[t[i]-a];}//累加每个字母的最小出现次数for(inti0;i26;i){ansmin(a[i],b[i]);//取较小值并累加}coutans;//输出结果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 点击跳转各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;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标准模板库STLhttps://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 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}