HDU 5756 ztr loves lucky numbers （dfs）（搜索）

绝地灬酷狼 2022-08-21 12:39 144阅读 0赞

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5676

题目大意：只有7和4且7和4数量相等的数字为幸运数字，给你数字n，你要找出大于等于n的最小的幸运数字

解题思路：  
计算可得幸运数字最多有C21+C42+C63+…+C189<2^18，所以可以通过dfs打表列出所有的幸运数字，因为n最多有19位，所以要进行特判，如果大于7777777744444444，则必须输出十个四，十个七

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <string>
    #include <vector>
    #include <list>
    #include <map>
    #include <queue>
    #include <stack>
    #include <algorithm>
    #include <numeric>
    #include <functional>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    vector<LL> ans;
    
    void dfs(int four,int seven,LL now)
    {
        if(four&&four==seven) ans.push_back(now);
        if(four<9) dfs(four+1,seven,now*10+4);
        if(seven<9) dfs(four,seven+1,now*10+7);
        return ;
    }
    
    int main()
    {
        dfs(0,0,0);
        sort(ans.begin(),ans.end());
        int t;
        RI(t);
        while(t--)
        {
            bool mark=false;
            char a[30];
            scanf("%s",a);
            int alen=strlen(a);
            if(alen==18)
            {
                for(int i=0;i<9;i++)
                {
                    if(a[i]-'0'>7) mark=true;
                }
                for(int i=9;i<18;i++)
                {
                    if(a[i]-'0'>4) mark=true;
                }
            }
            if(mark||alen==19)
            {
            printf("44444444447777777777\n");
            }
            else
            {
                LL x=0;
                for(int i=0;i<alen;i++)
                {
                    x=x*10+a[i]-'0';
                }
                //cout<<x<<endl;
                cout<<*(lower_bound(ans.begin(),ans.end(),x))<<endl;;
    
            }
        }
        return 0;
    }