首页 > 代码库 > [思路题] spoj 11354 Amusing numbers
[思路题] spoj 11354 Amusing numbers
题意:
给k(1<=k<=10^15),问第k 大的只含有数字5和6的数是多少
比如 1就是5 ,3就是55 ,4就是56
思路:
首先我们可以发现,一位数有2个这的数,两位数有4个,三位数有8个。。
那么我们可以通过统计确定出第k大的数是几位的。
通过累和,一位数以下0个,两位数以下2,三位数以下6
n位数以下就是2^n-2
然后给k,从大到下搜索第一个小于k的bit[i],那么就有i位数。
然后就是对于i位数,它是第几个数。
比如说k=70,它就是6位数。
然后 70-bit[6]-1=7 它是6位数的第7个数。
然后思考一下,只有5和6,其实就可以当做是二进制,
0就是5,1就是6.
对于7(10)=111(2)
然后补齐6位 其实就是 000111(2),也就是555666。
代码:
#include"cstdlib" #include"cstdio" #include"cstring" #include"cmath" #include"queue" #include"algorithm" #include"iostream" using namespace std; #define ll long long ll bit[66]; int main() { bit[1]=0; for(int i=2;i<=51;i++) bit[i]=(1LL<<i)-2; //注意加LL int t; cin>>t; while(t--) { ll k; int i; scanf("%lld",&k); for(i=51;i>=1;i--) if(bit[i]<k) break; //确认几位数 ll tep=k-bit[i]-1; //几位数的第几个 int num[66],cnt=0; while(tep) { num[++cnt]=tep%2; tep/=2; } for(int j=0;j<i-cnt;j++) printf("5"); //补上前面的0 for(int j=cnt;j>=1;j--) { if(num[j]) printf("6"); else printf("5"); } puts(""); } return 0; }
[思路题] spoj 11354 Amusing numbers
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。