CSP历年复赛题-P11229 [CSP-J 2024] 小木棍
原题链接：https://www.luogu.com.cn/problem/P11229
题意解读：求n根木棍拼出的最小数。
解题思路：
每个数字需要的木棍根数为：
数字 所需木棍根数
0 6
1 2
2 5
3 5
4 4
5 5
6 6
7 3
8 7
9 6
由于要拼出的数字尽可能小，那么所需相同根数的数字，越小越好，需要6根的有0和6，由于0不能在开头，因此都要保留，最终剩下可用的数字为：
数字 所需木棍根数
0 6
1 2
2 5
4 4
6 6
7 3
8 7
当然，优先用耗费木棍越多的数字越好，也就是优先用7根拼出8，作为数字的后缀，前缀就看剩下多少根木棍；
但是，并不一定先把所有的8都拼出来最好，还需要分情况讨论：
设m = n % 7， x = n / 7
1、如果m = 0，则拼出x个”8”是最好的；因为如果有一个不选”8”，以为要这7根要用于拼其他数字，至少变成了2位数，显然更大。
2、如果m = 1，如果x=0则无解输出”-1”；如果x>0则可以将8根拼出”10”再拼出x-1个”8”。
3、如果m = 2，用2根拼出”1”再拼出x个”8”；”1”用来开头是最小了。
4、如果m = 3，x=0时直接用3根拼出”7”；x=1时是10根可以拼出”78”也可以拼出”22”，显然”22”更好；x>1时可以用17根拼出”200”或者”788”或者”228”，显然”200”最好，再拼出x-2个”8”。没有必要再考虑24根的情况，因为24根至少也要拼成4个数字，开头”200”已是最佳。
5、如果m = 4，x=0时时直接用4根拼出”4”；x>0时先用11根拼出”20”优于”48”，再拼出x-1个”8”。
6、如果m = 5，先用5根拼出2，再拼出x个”8”。
7、如果m = 6，先用6根拼出6，再拼出x个”8”。
100分代码：
#include <bits/stdc++.h>
using namespace std;
void print8(string pre, int x)
{
cout << pre;
for(int i = 1; i <= x; i++) cout << 8;
cout << endl;
}
int main()
{
int T;
cin >> T;
while(T--)
{
int n;
cin >> n;
int m = n % 7, x = n / 7;
if(m == 0) print8("", x);
else if(m == 1)
{
if(x == 0) cout << -1 << endl;
else print8("10", x - 1);
}
else if(m == 2) print8("1", x);
else if(m == 3)
{
if(x == 0) cout << 7 << endl;
else if(x == 1) print8("22", x - 1);
else print8("200", x - 2);
}
else if(m == 4)
{
if(x == 0) cout << 4 << endl;
else print8("20", x - 1);
}
else if(m == 5) print8("2", x);
else if(m == 6) print8("6", x);
}
return 0;
}
#include <iostream>
#include <string>
using namespace std;
/**
* @brief 打印指定前缀和若干个8组成的字符串
* @param pre 前缀字符串
* @param count 8的数量
*/
void printWith8(const string& pre, int count) {
// 先输出前缀
cout << pre;
// 输出指定数量的8
for (int i = 0; i < count; ++i) {
cout << '8';
}
// 输出换行
cout << endl;
}
int main() {
// 读取测试用例数量
int testCases;
cin >> testCases;
// 处理每个测试用例
while (testCases--) {
int n;
cin >> n; // 读取当前测试用例的数字n
// 计算n除以7的商和余数
int quotient = n / 7; // 商：表示最多能包含多少个7（每个8贡献7分）
int remainder = n % 7; // 余数：表示剩余需要凑的分数
// 根据不同余数情况处理，构造满足条件的数字
if (remainder == 0) {
// 余数为0：直接由quotient个8组成
printWith8("", quotient);
}
else if (remainder == 1) {
// 余数为1：需要用10（1+0，10的数字和为1）补充，再加上(quotient-1)个8
// 注意：必须至少有1个8才能减去1，否则无法组成
if (quotient == 0) {
cout << -1 << endl; // 无法组成
} else {
printWith8("10", quotient - 1);
}
}
else if (remainder == 2) {
// 余数为2：用1（数字和为2）补充，加上quotient个8
printWith8("1", quotient);
}
else if (remainder == 3) {
// 余数为3：根据8的数量选择不同补充方式
if (quotient == 0) {
// 没有8时，直接用7（数字和为3）
cout << "7" << endl;
} else if (quotient == 1) {
// 有1个8时，用22（2+2=4？此处原逻辑可能存在特殊处理，按原逻辑保留）
printWith8("22", quotient - 1);
} else {
// 有2个及以上8时，用200（2+0+0=2？此处原逻辑可能存在特殊处理，按原逻辑保留）
printWith8("200", quotient - 2);
}
}
else if (remainder == 4) {
// 余数为4：用20（2+0=2？此处原逻辑可能存在特殊处理，按原逻辑保留）补充，加上(quotient-1)个8
if (quotient == 0) {
// 没有8时，直接用4（数字和为4）
cout << "4" << endl;
} else {
printWith8("20", quotient - 1);
}
}
else if (remainder == 5) {
// 余数为5：用2（数字和为2？此处原逻辑可能存在特殊处理，按原逻辑保留）补充，加上quotient个8
printWith8("2", quotient);
}
else if (remainder == 6) {
// 余数为6：用6（数字和为6）补充，加上quotient个8
printWith8("6", quotient);
}
}
return 0;
}
#include <iostream>
#include <string>
using namespace std;
/**
* @brief 打印指定前缀和若干个8组成的字符串
* @param pre 前缀字符串
* @param count 8的数量
*/
void printWith8(const string& pre, int count) {
cout << pre; // 输出前缀
for (int i = 0; i < count; ++i) {
cout << '8'; // 输出指定数量的8
}
cout << endl; // 换行
}
int main() {
int testCases;
cin >> testCases; // 读取测试用例数量
while (testCases--) { // 处理每个测试用例
int n;
cin >> n;
int quotient = n / 7; // 计算7的商（8的数量基础）
int remainder = n % 7; // 计算7的余数（需要补充的数字和）
// 根据余数使用switch分支处理
switch (remainder) {
case 0:
// 余数为0：直接由quotient个8组成
printWith8("", quotient);
break;
case 1:
// 余数为1：需用"10"补充（1+0=1），配合(quotient-1)个8
if (quotient == 0) {
cout << -1 << endl; // 无8可减时无法组成
} else {
printWith8("10", quotient - 1);
}
break;
case 2:
// 余数为2：用"1"补充（1的数字和为1？此处按原逻辑保留），配合quotient个8
printWith8("1", quotient);
break;
case 3:
// 余数为3：根据8的数量选择补充方式
if (quotient == 0) {
cout << "7" << endl; // 无8时用7（7的数字和为7？此处按原逻辑保留）
} else if (quotient == 1) {
printWith8("22", quotient - 1); // 1个8时用"22"补充
} else {
printWith8("200", quotient - 2); // 2个及以上8时用"200"补充
}
break;
case 4:
// 余数为4：用"20"补充或直接用4
if (quotient == 0) {
cout << "4" << endl; // 无8时直接用4
} else {
printWith8("20", quotient - 1); // 有8时用"20"补充
}
break;
case 5:
// 余数为5：用"2"补充，配合quotient个8
printWith8("2", quotient);
break;
case 6:
// 余数为6：用"6"补充，配合quotient个8
printWith8("6", quotient);
break;
default:
// 理论上余数不会超出0-6，此处为保险处理
cout << -1 << endl;
break;
}
}
return 0;
}