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输入 142 23454输出 12输入输出样例 2输入 2169 21891919输出 21输入输出样例 3输入 3801 12345678111输出 30说明/提示样例 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 10x10另外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的个数。代码实现#includebits/stdc.husingnamespacestd;string sx,s;// sx:喜欢的数字, s:物品串intcnt[10],need[10];intmain(){cinsxs;for(charc:sx)need[c-0];// 统计需求for(charc:s)cnt[c-0];// 统计物品intg1_needneed[2]need[5];// 25组需求intg2_needneed[6]need[9];// 69组需求intg1_availcnt[2]cnt[5];// 25组可用intg2_availcnt[6]cnt[9];// 69组可用intans1e9;// 初始大值// 处理独立数字for(intd0;d10;d){if(d2||d5||d6||d9)continue;// 跳过已合并的组if(need[d]0)ansmin(ans,cnt[d]/need[d]);}if(g1_need0)ansmin(ans,g1_avail/g1_need);if(g2_need0)ansmin(ans,g2_avail/g2_need);coutansendl;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标准模板库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;}