当前位置: 代码迷 >> 综合 >> BestCoder Round #82 ztr loves lucky numbers
  详细解决方案

BestCoder Round #82 ztr loves lucky numbers

热度:79   发布时间:2023-12-06 03:33:33.0

题目链接:http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=693&pid=1002

首先,处理4,7感觉上和我们的二进制0,1很像,仔细计算可得在范围内的答案可能有2^18 = 262,144种情况,我们不可能每次都去计算,肯定会爆时间,所以我们可以采取预处理二分的思想去做,但是除了这个之外还有个问题,就是要特判,小编因为没有特判就在比赛的时候没有把这道题A掉,除了发现没有特判也是后悔死了,因为可能会有比我们在10^18次范围内预处理的最大答案还要大,这个时候我们就可以直接输出44444444447777777777即可。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL __int64
using namespace std;
const int maxn = 300000;
LL a[maxn],tot;
void dfs(int n4,int n7,LL sum)
{if(n4 == 0 && n7 == 0)a[++tot] = sum;if(n4) dfs(n4-1,n7,sum*10+4);if(n7) dfs(n4,n7-1,sum*10+7);return ;
}
LL Binary_Search(LL x)
{int l=1,r=tot+1,mid;while(r > l){mid = (l+r)/2;if(x > a[mid]) l = mid+1;else r = mid;}return a[r];
}
int main()
{tot = 0;for(int i=1; i<=9; i++) dfs(i,i,0);int T;scanf("%d",&T);while(T--){LL x;scanf("%I64d",&x);if(x > a[tot]) printf("44444444447777777777\n");else printf("%I64d\n",Binary_Search(x));}
}


  相关解决方案