HDU 5676：ztr loves lucky numbers——暴力打表+二分查找求最小超級幸運數

題目大意

「幸運數」定義為十進制僅包含數字4和7的正整數。「超級幸運數」進一步要求4和7的個數相等。給定n（1≤n≤10^18），求不小於n的最小超級幸運數。測試用例T≤10^5。

解題思路

1. 暴力生成所有超級幸運數：超級幸運數位數必為偶數（2,4,...,18位）。對每個長度2k，生成所有含k個4和k個7的排列。總數量極小（C(18,9)=48620），可預處理存入陣列並排序。
2. 二分查找答案：對每個查詢n，在有序陣列中用lower_bound找到首個≥n的數。特殊情況：若n大於最大18位超級幸運數（777...444...），答案為最小20位超級幸運數（10個4後跟10個7）。

關鍵實現細節

• DFS生成：參數(当前数值, 剩余4的个数, 剩余7的个数)，優先嘗試添加4再添加7，自然生成遞增序列（無需額外排序）。
• 邊界處理：unsigned long long（或__int128）存儲18位數；20位數超出64位範圍，直接輸出字符串"44444444447777777777"。
• 查詢優化：預處理一次，每查詢O(log M)，M≈5萬，總複雜度O(T log M)極快。

參考代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
using u64 = unsigned long long;

vector<u64> lucky;

void dfs(u64 cur, int cnt4, int cnt7) {
    if (cnt4 == 0 && cnt7 == 0) {
        lucky.push_back(cur);
        return;
    }
    if (cnt4) dfs(cur * 10 + 4, cnt4 - 1, cnt7);
    if (cnt7) dfs(cur * 10 + 7, cnt4, cnt7 - 1);
}

int main() {
    // 預生成所有 2~18 位超級幸運數
    for (int len = 2; len <= 18; len += 2)
        dfs(0, len/2, len/2);
    sort(lucky.begin(), lucky.end()); // 實際上DFS已有序，保險起見排序

    int T; scanf("%d", &T);
    while (T--) {
        u64 n; scanf("%llu", &n);
        if (n > 777777777444444444ULL) { // 最大18位超級幸運數
            puts("44444444447777777777");
            continue;
        }
        auto it = lower_bound(lucky.begin(), lucky.end(), n);
        printf("%llu\n", *it);
    }
    return 0;
}

總結

本題利用數據範圍小（超級幸運數總量少）的特點，採用「預處理+二分」經典模式，避免了複雜的數位DP，代碼簡短高效。