2022年CSP-X复赛真题及题解（T3：口袋）
题目描述
克拉拉同学平时就喜欢一些奇奇怪怪的东西，她有一个神奇的口袋，她能从口袋里拿出各种神奇的东西。
某一天她发现口袋里出现了一些像数字形状的物品，我们用
0
\\tt{0}
0 到
9
\\tt{9}
9 这十种数字来表示不同的物品。
克拉拉有一个非常喜欢的数字
x
x
x, 现在她想用口袋里的给出的这些数字形状的物品来组成尽可能多的
x
x
x，每个物品只能用一次。组装过程中克拉拉发现这些像数字形状的物品中，
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
x
x 的最多的个数。
输入格式
第一行为一个正整数
x
x
x，表示克拉拉最喜欢的数字。
第二行为一个字符串，字符串每一位为
0
\\tt{0}
0 到
9
\\tt{9}
9 的某个字符，字符串长度为物品的个数（数字之间没有其他符号）。
输出格式
一行，一个整数，表示能用物品拼成最多的
x
x
x 的个数(拼成
x
x
x 的次数)。
输入输出样例 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 100
1≤x≤100，字符串长度不超过
20
20
20。
其中
10
%
10\\%
10% 的数据保证
x
<
10
x < 10
x<10，另外
10
%
10\\%
10% 的数据保证
x
x
x 中不出现
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 1000
1≤x≤1000, 字符串长度不超过
100
100
100；
对于
100
%
100\\%
100% 的数据，
1
≤
x
≤
10
5
1 \\leq x \\leq 10^5
1≤x≤105，字符串长度不超过
2
×
10
5
2\\times 10^5
2×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>
using namespace std;
string sx, s; // sx:喜欢的数字, s:物品串
int cnt[10] , need[10] ;
int main() {
cin >> sx >> s;
for(char c : sx) need[c–'0']++; // 统计需求
for(char c : s) cnt[c–'0']++; // 统计物品
int g1_need = need[2] + need[5]; // 2&5组需求
int g2_need = need[6] + need[9]; // 6&9组需求
int g1_avail = cnt[2] + cnt[5]; // 2&5组可用
int g2_avail = cnt[6] + cnt[9]; // 6&9组可用
int ans = 1e9; // 初始大值
// 处理独立数字
for(int d=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;
return 0;
}
功能分析
- 统计物品和需求的频次：遍历字符串，将每个字符转为数字并累加计数。
- 合并可互换的数字：将 2 和 5 视为同一资源组，6 和 9 视为另一资源组，分别计算总需求和总可用数量。
- 计算最大可拼个数：对于每一组（独立数字或合并组），计算可用数量除以需求数量的整数商，取所有组的最小值作为答案。
- 边界处理：若某个需求为 0，则不对该组做限制；若可用数量小于需求，除法结果为 0，最终答案也会为 0。
- 时间复杂度：O(len(s) + len(sx))，可处理长度
2
×
10
5
2×10^5
2×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>
using namespace std;
int main(){
cout<<"跟着王老师一起学习信奥赛C++";
cout<<" 成就更好的自己！ ";
cout<<" csp信奥赛一等奖属于你! ";
return 0;
}
