首页 > 代码库 > hdu5676 ztr loves lucky numbers(dfs)

hdu5676 ztr loves lucky numbers(dfs)

链接

ztrloveslucky numbers

题意

定义幸运数为:只存在4和7且4和7数量相等的数,给出n,求比>=n的最小幸运数

做法

暴力搜出所有长度从2-18的幸运数,因为最多9个4,9个7,再大的话好像数组存不下只能特判了,然后二分找出比这个数大的那个数就行了

代码

 #include<bits/stdc++.h>using namespace std;#define LL long longLL n[1100000];int s4, s7, len, t;void dfs(int s4, int s7, int len, LL num) {    if(s4 == len && len == s7) {        n[t++] = num;        return ;    }    if(s4 < len)        dfs(s4 + 1, s7, len, num * 10 + 4);    if(s7 < len)        dfs(s4, s7 + 1, len, num * 10 + 7);}int main() {    int T;    cin >> T;    t = 0;    for(int i = 1; i <= 9; i++)        dfs(0, 0, i, 0);    while(T--) {        LL num;        cin >> num;        int k = lower_bound(n, n + t, num) - n;        if(n[k])cout << n[k] << endl;        else {            for(int i = 0; i < 10; i++)cout << "4";            for(int i = 0; i < 10; i++)cout << "7";            cout << endl;        }    }}
?

hdu5676 ztr loves lucky numbers(dfs)