前言
我们班很多人这道题都爆了，原因是写分讨写挂了。不像睿智的我，直接暴力加上一点点思维。
方法一
解题思路
step 1
首先我们把每个数的贡献都列出来。
设 为拼成 需要的木棍数量。
第一行表示数 ，第二行表示 。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|
| 6 | 2 | 5 | 4 | 5 | 6 | 3 | 7 | 6 | |
然后按照贡献分类。
由于表格不好列，就不列表格了。
每一行开头的数字代表 ，后面的是满足 的所有 。
。
。
。
。
。
。
我们可以观察到一些数字是没有用的，比如数字 永远不是最优的，因为 ，且 ，那么 肯定是这三个数中最优的。
于是我们就可以精简成：
。
。
。
。
。
。
需要注意的是 并不能直接删去，因为题目要求没有前导 。比如 ，答案应为是 而不是 或 。
step 2
这时，我们再来考虑如何使答案尽可能小。
首先我们要满足答案尽可能小，这意味着答案的位数要尽可能小。比如 。所以然后我们发现 是最大的，所以大多数情况下，答案肯定包含一堆 。
为什么说是大多数情况下呢，比如 时，只有当 或 或 的时候答案才包含 。
step 3
然后我们继续考虑如何使答案尽可能小。
这次我们考虑的是如何使答案在位数一样的情况下选出最小值。
很明显 一定只能跟在答案的最后面。
显然，会出现一些特殊情况导致 个较小的数比 个较小的数再加上 个 更优。于是我们只需要写一个暴力程序找找关系，发现对于任意答案只有至多前 位不为 ，所以我们可以暴力枚举前 位怎么组合最优。
需要注意的是由于不能有前导零，所以我们需要特殊处理，具体实现请看代码。
注意
题目要求拼出一个正整数，所以答案不能为 。
谔谔，由于是考场上写的，为了保险，我枚举的是前 位。而且建议不要使用 to_string()，因为本人亲测会超时。
CODE：
#include <bits/stdc++.h>
using namespace std;
int k[100], b[100010];
int main() {
ios::sync_with_stdio(false);
ios_base::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int t;
cin >> t;
k[0] = k[6] = k[9] = 6, k[1] = 2, k[2] = k[3] = k[5] = 5, k[4] = 4, k[8] = 7;
while (t--) {
int id2 = 0;
int n;
cin >> n;
if (n == 1) {
cout << "-1" << endl;
} else if (n == 2) {
cout << "1" << endl;
} else if (n == 3) {
cout << "7" << endl;
} else if (n == 4) {
cout << "4" << endl;
} else if (n == 5) {
cout << "2" << endl;
} else if (n == 6) {
cout << "6" << endl;
} else if (n == 7) {
cout << "8" << endl;
} else if (n % 7 == 0) {
for (int i = 1; i <= n / 7; i++) {
cout << 8;
}
cout << endl;
} else {
while (n - 7 > 28) {
b[++id2] = 8;
n -= 7;
}
string a = "9999999999999999999";
for (int i = -1; i <= 9; i++) {
for (int j = -1; j <= 9; j++) {
for (int o = -1; o <= 9; o++) {
for (int l = -1; l <= 9; l++) {
for (int m = -1; m <= 9; m++) { //从 -1 开始是因为位数前面位数不一定为 5，也就是说其实是至多 5 位。
string b = "";
int sum = 0;
if (i != -1) {
b += i + '0';
sum += k[i];
}
if (j != -1) {
b += j + '0';
sum += k[j];
}
if (o != -1) {
b += o + '0';
sum += k[o];
}
if (l != -1) {
b += l + '0';
sum += k[l];
}
if (m != -1) {
b += m + '0';
sum += k[m];
}
if (sum == n && b.size() > 0 && b[0] != '0') {
if (a.size() > b.size())
a = b;
else if (a.size() == b.size()) {
a = min(a, b);
}
}
}
}
}
}
}
for (int i = 0; i < a.size(); i++) {
b[++id2] = a[i] - '0';
}
sort(b + 1, b + 1 + id2);
int kk = 0;
for (int i = 1; i <= id2; i++) { //找到第一个不为 0 的数，然后将其放到第一个位置输出。
if (b[i] != 0) {
kk = i;
cout << b[i];
break;
}
}
for (int i = 1; i <= id2; i++) {
if (i != kk) {
cout << b[i];
}
}
cout << endl;
}
}
return 0;
}
方法二
找关于 的规律，由于作者考试时没用这个方法所以懒得写。
方法三
dp，由于作者不会 dp。
方法四
图论建模。
总结
方法二、三、四值得读者去探索。（别喷我不会） 为了让读者受益匪浅，所以方法二、三、四就不讲了。但是方法一是可以过滤大多数题目的特判的，除了像 这种的特判。