2022年CSP-X复赛真题及题解（T3：口袋）

2022年CSP-X复赛真题及题解（T3：口袋）

题目描述

克拉拉同学平时就喜欢一些奇奇怪怪的东西，她有一个神奇的口袋，她能从口袋里拿出各种神奇的东西。

某一天她发现口袋里出现了一些像数字形状的物品，我们用0 \tt{0}0到9 \tt{9}9这十种数字来表示不同的物品。

克拉拉有一个非常喜欢的数字x xx, 现在她想用口袋里的给出的这些数字形状的物品来组成尽可能多的x xx，每个物品只能用一次。组装过程中克拉拉发现这些像数字形状的物品中，2 \tt{2}2和5 \tt{5}5倒过来特别像，6 \tt{6}6和9 \tt{9}9倒过来也特别像，所以她可以用2 \tt{2}2和5 \tt{5}5互相代替，也能用6 \tt{6}6和9 \tt{9}9互相代替（其他的不能代替）。

举个例子，克拉拉喜欢数42 \tt{42}42，现在口袋里能拿出来顺序为23454 \tt{23454}23454这五种物品，因此她可以用第一个物品2 \tt{2}2和第三个物品4 \tt{4}4组成42 \tt{42}42（可以组成24 \tt{24}24，但不是需要的），还能用第四个物品5 \tt{5}5和第五个物品4 \tt{4}4组成42 \tt{42}42（其中5 \tt{5}5倒过来可以当作2 \tt{2}2）。

现在想要知道这些物品最多能组成几个克拉拉最喜欢的数字。请你编程帮克拉拉解决这个问题，并输出能用物品组成x xx的最多的个数。

输入格式

第一行为一个正整数x xx，表示克拉拉最喜欢的数字。

第二行为一个字符串，字符串每一位为0 \tt{0}0到9 \tt{9}9的某个字符，字符串长度为物品的个数（数字之间没有其他符号）。

输出格式

一行，一个整数，表示能用物品拼成最多的x xx的个数(拼成x xx的次数)。

输入输出样例 1

输入 1

42 23454

输出 1

2

输入输出样例 2

输入 2

169 21891919

输出 2

1

输入输出样例 3

输入 3

801 12345678111

输出 3

0

说明/提示

样例 1 说明

( 2 , 4 ) (\tt{2},\tt{4})(2,4)和( 5 , 4 ) (\tt{5},\tt{4})(5,4)拼成42 \tt{42}42，其中5 \tt{5}5可以倒过来当作2 \tt{2}2。可以证明不能再多拼成一个42 \tt{42}42了。

样例 2 说明

2 − 1 − 8 − 9 − 1 − 9 − 1 − 9 \tt{2}-{\color{red}{\tt{1}}}-\tt{8}-{\color{red}{\tt{9}}}-\tt{1}-{\color{red}{\tt{9}}}-\tt{1}-\tt{9}2−1−8−9−1−9−1−9，可以用( 1 , 9 , 9 ) (\tt{1},\tt{9},\tt{9})(1,9,9)拼成169 \tt{169}169，第一个9 \tt{9}9可以倒过来当6 \tt{6}6使用。因为每个数字只能用一次，因此最多只能拼成一个169 \tt{169}169。

【数据范围和限制】

对于30 % 30\%30%的数据，1 ≤ x ≤ 100 1 \leq x \leq 1001≤x≤100，字符串长度不超过20 2020。

其中10 % 10\%10%的数据保证x < 10 x < 10x<10，另外10 % 10\%10%的数据保证x xx中不出现2 , 5 , 6 , 9 \tt{2},\tt{5},\tt{6},\tt{9}2,5,6,9。

对于60 % 60\%60%的数据，1 ≤ x ≤ 1000 1 \leq x \leq 10001≤x≤1000, 字符串长度不超过100 100100；

对于100 % 100\%100%的数据，1 ≤ x ≤ 10 5 1 \leq x \leq 10^51≤x≤105，字符串长度不超过2 × 10 5 2\times 10^52×105。

思路分析

题目要求用给定的数字物品（字符串s）拼出尽可能多的数字x，每个物品只能用一次，且2与5可以互相代替，6与9可以互相代替。由于只关心每个数字的个数，不关心顺序，这是一个典型的“资源分配”问题。

• 将x的各位数字统计到need[0..9]，将物品字符串的各位数字统计到cnt[0..9]。
• 对于不能替换的数字（0,1,3,4,7,8），它们各自独立，最多能拼出的个数为cnt[d] / need[d]（若need[d]=0则无限制）。
• 对于可替换的数字：2和5看作一组，总需求 =need[2] + need[5]，总可用 =cnt[2] + cnt[5]，个数 =总可用 / 总需求。同理处理6和9。
• 最终答案为所有组（包括独立数字）中的最小值，即为最多能拼出的完整x的个数。

代码实现

#include<bits/stdc++.h>usingnamespacestd;string sx,s;// sx:喜欢的数字, s:物品串intcnt[10],need[10];intmain(){cin>>sx>>s;for(charc:sx)need[c-'0']++;// 统计需求for(charc:s)cnt[c-'0']++;// 统计物品intg1_need=need[2]+need[5];// 2&5组需求intg2_need=need[6]+need[9];// 6&9组需求intg1_avail=cnt[2]+cnt[5];// 2&5组可用intg2_avail=cnt[6]+cnt[9];// 6&9组可用intans=1e9;// 初始大值// 处理独立数字for(intd=0;d<10;d++){if(d==2||d==5||d==6||d==9)continue;// 跳过已合并的组if(need[d]>0)ans=min(ans,cnt[d]/need[d]);}if(g1_need>0)ans=min(ans,g1_avail/g1_need);if(g2_need>0)ans=min(ans,g2_avail/g2_need);cout<<ans<<endl;return0;}

功能分析

• 统计物品和需求的频次：遍历字符串，将每个字符转为数字并累加计数。
• 合并可互换的数字：将2和5视为同一资源组，6和9视为另一资源组，分别计算总需求和总可用数量。
• 计算最大可拼个数：对于每一组（独立数字或合并组），计算可用数量除以需求数量的整数商，取所有组的最小值作为答案。
• 边界处理：若某个需求为 0，则不对该组做限制；若可用数量小于需求，除法结果为 0，最终答案也会为 0。
• 时间复杂度：O(len(s) + len(sx))，可处理长度2 × 10 5 2×10^52×105的字符串。
• 空间复杂度：O(1)，仅使用常数大小的数组。

更多内容请关注专栏：信奥赛C++普及组csp-j初赛&复赛真题题解（持续更新）：https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转

【秘籍汇总】（完整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;}