首页 > 代码库 > hdu5676 ztr loves lucky numbers DFS
hdu5676 ztr loves lucky numbers DFS
题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=5676
题意:
定义幸运数为:只存在4和7且4和7数量相等的数,给出n,求比>=n的最小幸运数
思路:
因为n最多18位,幸运数最大是10个4,10个7,这种情况特判掉,爆longlong,其他的暴力搜出所有长度从2-18的幸运数,因为最多9个4,9个7,然后二分找出比这个数大的那个数
代码:
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 #define MS(a) memset(a,0,sizeof(a)) 5 #define MP make_pair 6 #define PB push_back 7 const int INF = 0x3f3f3f3f; 8 const ll INFLL = 0x3f3f3f3f3f3f3f3fLL; 9 inline ll read(){ 10 ll x=0,f=1;char ch=getchar(); 11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 12 while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 13 return x*f; 14 } 15 ////////////////////////////////////////////////////////////////////////// 16 const int maxn = 11000000; 17 18 ll n,x[maxn],cnt; 19 20 void dfs(int s4,int s7,int len,ll num){ 21 if(s4==s7 && s4==len){ 22 x[cnt++] = num; 23 return ; 24 } 25 26 if(s4<len) 27 dfs(s4+1,s7,len,num*10+4); 28 if(s7<len) 29 dfs(s4,s7+1,len,num*10+7); 30 } 31 32 int main(){ 33 for(int i=1; i<=9; i++) 34 dfs(0,0,i,0); 35 int T = read(); 36 while(T--){ 37 cin >> n; 38 int pos = lower_bound(x,x+cnt,n)-x; 39 if(x[pos]) cout << x[pos] << endl; 40 else{ 41 for(int i=0; i<10; i++) cout<<"4"; 42 for(int i=0; i<10; i++) cout<<"7"; 43 cout << endl; 44 } 45 } 46 47 return 0; 48 }
hdu5676 ztr loves lucky numbers DFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。