【20 分】超时的 dfs

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1'000'000'000'000'000'000;
int T, n;
int ans;
int num[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};
// 当前考虑第 now 位，之前用了 cnt 个火柴棒
// 之前凑出来了 x
void dfs(int now, int cnt, int x)
{
    if (x > ans)
        return;
    if (now == 20)
        return;
    if (cnt > n)
        return;
    if (cnt == n)
    {
        ans = min(ans, x);
        return;
    }
    for (int i = 0; i <= 9; i++)
    {
        if (now == 1 && i == 0)
            continue;
        dfs(now + 1, cnt + num[i], x * 10 + i);
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n;
        ans = INF;
        dfs(1, 0, 0);
        if (ans == INF)
            cout << "-1\n";
        else
            cout << ans << "\n";
    }
    return 0;
}

【100 分】根据 dfs 规律的做法

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1'000'000'000'000'000'000;
int T, n;
int a[21] = {0,
             -1, 1, 7, 4, 2,
             6, 8, 10, 18, 22,
             20, 28, 68, 88, 108,
             188, 200, 208, 288, 688};
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while (T--)
    {
        cin >> n;
        if (n <= 20)
            cout << a[n] << "\n";
        else
        {
            if (n % 7 == 1)
            {
                cout << "10";
                n -= 8;
            }
            else if (n % 7 == 2)
            {
                cout << "1";
                n -= 2;
            }
            else if (n % 7 == 3)
            {
                cout << "200";
                n -= 17;
            }
            else if (n % 7 == 4)
            {
                cout << "20";
                n -= 11;
            }
            else if (n % 7 == 5)
            {
                cout << "2";
                n -= 5;
            }
            else if (n % 7 == 6)
            {
                cout << "6";
                n -= 6;
            }
            for (int i = 1; i <= n / 7; i++)
                cout << "8";
            cout << "\n";
        }
    }
    return 0;
}