[CSP-J 2024-T3] 小木棍摘要本题是 CSP-J 2024 第三题要求用恰好n nn根长度相等的小木棍拼出一个无前导零的正整数并使该数尽可能小。题解采用贪心 模 7 分类讨论优先用木棍数最多的数字87 根以减少位数再根据n m o d 7 n \bmod 7nmod7的余数调整最高位数字最终在位数最少的前提下使高位最小。需注意n 6 n6n6时不能输出0、n ≥ 17 n \geq 17n≥17且余数为 3 时应输出200...等易错细节。题目描述小 S 喜欢收集小木棍。在收集了n nn根长度相等的小木棍之后他闲来无事便用它们拼起了数字。用小木棍拼每种数字的方法如下图所示。现在小 S 希望拼出一个正整数满足如下条件拼出这个数恰好使用n nn根小木棍拼出的数没有前导0 00在满足以上两个条件的前提下这个数尽可能小。小 S 想知道这个数是多少可n nn很大把木棍整理清楚就把小 S 折腾坏了所以你需要帮他解决这个问题。如果不存在正整数满足以上条件你需要输出− 1 -1−1进行报告。输入格式本题有多组测试数据。输入的第一行包含一个正整数T TT表示数据组数。接下来包含T TT组数据每组数据的格式如下一行包含一个整数n nn表示木棍数。输出格式对于每组数据输出一行如果存在满足题意的正整数输出这个数否则输出− 1 -1−1。输入输出样例 #1输入 #15 1 2 3 6 18输出 #1-1 1 7 6 208说明/提示【样例 1 解释】对于第一组测试数据不存在任何一个正整数可以使用恰好一根小木棍摆出故输出− 1 -1−1。对于第四组测试数据注意0 00并不是一个满足要求的方案。摆出9 99、41 4141以及111 111111都恰好需要6 66根小木棍但它们不是摆出的数最小的方案。对于第五组测试数据摆出208 208208需要5 6 7 18 5 6 7 1856718根小木棍。可以证明摆出任何一个小于208 208208的正整数需要的小木棍数都不是18 1818。注意尽管拼出006 006006也需要18 1818根小木棍但因为这个数有前导零因此并不是一个满足要求的方案。【数据范围】对于所有测试数据保证1 ≤ T ≤ 50 1 \leq T \leq 501≤T≤501 ≤ n ≤ 10 5 1 \leq n \leq 10^51≤n≤105。测试点编号n ≤ n\leqn≤特殊性质1 1120 2020无2 2250 5050^3 3310 3 10^3103A4 , 5 4,54,510 5 10^5105^6 6610 3 10^3103B7 , 8 7,87,810 5 10^5105^9 9910 3 10^3103无10 101010 5 10^5105^特殊性质 A保证n nn是7 77的倍数且n ≥ 100 n \geq 100n≥100。特殊性质 B保证存在整数k kk使得n 7 k 1 n 7k 1n7k1且n ≥ 100 n \geq 100n≥100。思路要点我们手里有n nn根木棍要拼出一个正整数不能有前导0 00要求恰好用完n nn根木棍并且让这个正整数尽可能小。首先我们要明确每个数字需要消耗的木棍数量数字1需要 2 根数字7需要 3 根数字4需要 4 根数字2,3,5需要 5 根数字0,6,9需要 6 根数字8需要 7 根撇开题目中“小木棍拼数字”的背景外壳这道题的本质是贪心算法Greedy 整数模运算与分类讨论。在给定的数字总和木棍数限制下组合出位数最少、且高位数字最小的数。关键思路如何让拼出来的数字“尽可能小”这里有两个核心的贪心策略位数越少数值越小比如任意一个 2 位数都一定小于 3 位数。因此我们要让每个数字消耗尽量多的木棍。观察发现数字8消耗的木棍最多7根。所以我们应该尽可能多地使用数字8。高位的数字越小数值越小如果位数相同决定大小的关键在最高位。例如18小于81。因此我们要把消耗木棍少、数值小的数字尽量往前排。基于以上两点我们可以用n nn除以 7商k n / 7 k n / 7kn/7表示我们最多能拼出多少个数字8。余数r n ( m o d 7 ) r n \pmod 7rn(mod7)则是剩下的木棍我们需要用这些余数和前面的8进行微调凑出最小的开头数字。解题步骤我们以样例输入中的n 18 n 18n18为例模拟代码的执行过程变量定义与初始化定义全局变量int T, n;用于存储测试组数和当前木棍数。定义辅助函数void prt(int k)用于连续输出k kk个数字8。读入数据系统读入T 5 T 5T5表示有 5 组数据。进入while(T--)循环读入当前组的木棍数n 18 n 18n18。条件分支判断首先判断n 2不成立最少摆出数字 1 需要 2 根木棍。再判断n 8不成立18 ≥ 8 18 \ge 818≥8。程序进入else分支开始核心的模 7 分类讨论。公式计算与输出k 18 / 7 2 k 18 / 7 2k18/72r 18 ( m o d 7 ) 4 r 18 \pmod 7 4r18(mod7)4程序进入switch(r)匹配到case 4据贪心原则余下 4 根木棍加上一个87 根共 11 根木棍。能拼出的最小两位数是202用 5 根0用 6 根5 6 11 5 6 115611。执行printf(20);。执行prt(--k);此时k自减 1 变成 1调用函数打印 1 个8。最终输出结果208。本题易错点坑一前导零与数字0的限制要点提醒当n 6 n 6n6时虽然数字0只需要 6 根木棍且比6小但题目要求拼出正整数因此单个0是非法的必须输出6。但在大数字中间如n 18 n 18n18输出2080可以作为中间位或低位存在。坑二r 3 r 3r3时的隐藏陷阱要点提醒当n 10 n 10n10时k 1 , r 3 k 1, r 3k1,r3答案是22 2222但是当n 17 n 17n17时k 2 , r 3 k 2, r 3k2,r3如果按之前思路尽可能末尾都是8 88把17 1717看成10 7 10 7107那剩下10 1010根木棍拼出的前缀最小的数是22 2222答案是228 228228。但如果末尾不是8 88把17 1717看成11 6 11 6116可以得到更小的200 200200也就是 $n 17 $且r 3 r 3r3的情况都应前缀数字200 200200才是最小。坑三纯暴力搜索DFS要点提醒试图从 1 开始枚举所有正整数去校验木棍数。当n 10 5 n 10^5n105时答案是一个长达一万多位的数字暴力搜索连第一组数据都跑不完。参考代码#includebits/stdc.husingnamespacestd;intT,n;// T: 测试数据组数, n: 每组的木棍数量// 工具函数连续打印 k 个数字 8voidprt(intk){for(inti1;ik;i){printf(8);}}intmain(){scanf(%d,T);while(T--){scanf(%d,n);// 特殊情况 1少于 2 根木棍无法拼出任何正整数if(n2){printf(-1);}// 特殊情况 2个位数木棍直接特判输出最优解elseif(n8){switch(n){case2:printf(1);break;case3:printf(7);break;case4:printf(4);break;case5:printf(2);break;case6:printf(6);break;// 注意不能是 0因为要求正整数case7:printf(8);break;}}// 通用情况n 8采用模 7 贪心策略else{intkn/7;// 最多可以拼出的 8 的个数intrn%7;// 模 7 的余数switch(r){case0:// 恰好整除全部填 8prt(k);break;case1:// 余 1 根向 8 借 1 根凑成 8 根拼出 10printf(10);prt(--k);break;case2:// 余 2 根直接在最前面放 1 (2根)剩下填 8printf(18);prt(--k);break;case3:// 余 3 根分情况讨论if(n17){// 也就是 n 10 的特殊情况printf(22);}else{// n 17 时借两个 8 凑成 17 根拼出 200printf(200);prt(k-2);}break;case4:// 余 4 根借一个 8 凑成 11 根拼出 20printf(20);prt(--k);break;case5:// 余 5 根借一个 8 凑成 12 根拼出 28printf(28);prt(--k);break;case6:// 余 6 根借一个 8 凑成 13 根拼出 68printf(68);prt(--k);break;}}printf(\n);// 每组数据输出完毕后换行}return0;}