hdu 5676 ztr loves lucky numbers 打表+二分

时间：2022-05-25 20:59:26

ztr loves lucky numbers

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1834    Accepted Submission(s): 707

Problem Description
ztr loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not.

Lucky number is super lucky if it's decimal representation contains equal amount of digits 4 and 7. For example, numbers 47, 7744, 474477 are super lucky and 4, 744, 467 are not.

One day ztr came across a positive integer n. Help him to find the least super lucky number which is not less than n.

Input
There are T(1≤n≤105) cases

For each cases:

The only line contains a positive integer n(1≤n≤1018). This number doesn't have leading zeroes.

Output
For each cases
Output the answer
Sample Input
2
4500
47
Sample Output
4747
47
Source

思路：数总共没多少，打表即可，再最大的情况特判一下；

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

#define eps 1e-14

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=1e2+,M=1e6+,inf=1e9+;

const ll INF=5e17+,mod=1e9+;

///数组大小

int check(ll x)

{

    int s=,q=;

    while(x)

    {

        if(x%==)s++;

        else q++;

        x/=;

    }

    if(s==q)return ;

    return ;

}

vector<ll>ans;

vector<ll>::iterator it;

void dfs(ll x)

{

    if(x>INF)return;

    if(check(x))ans.push_back(x);

    dfs(x*+);

    dfs(x*+);

}

int main()

{

    dfs(),dfs();

    sort(ans.begin(),ans.end());

    int T;

    scanf("%d",&T);

    while(T--)

    {

        ll x;

        scanf("%lld",&x);

        it=lower_bound(ans.begin(),ans.end(),x);

        if(it==ans.end())

            printf("44444444447777777777\n");

        else printf("%lld\n",*it);

    }

    return ;

}

相关文章