准确说,自己做的时候思维混乱了。一个数进行了两次操作,如果你不知道我当时的想法,你可能不明白我说的什么。
题面:4,7,44,47,74,77,444…… 如上,每个数仅由4、7组成,并从小到大排好序。求第K个数是多少。
思路:
第一步:
4,7 2个,1位数 累计2个,第 1-2个. 对应2进制数为1位数
44,47,74,77 4个,2位数 累计6个, 第3-6个,对应2进制数为2位
444,…… 8个,3位数 累计14个,第7-14个,对应2进制数为3位
观察可知,如题目给第K个时,那么K的二进制表示形式有多少位,那么第K个数就有多少位。如K的二进制有5位,那么第K个数是【44444,77777】中间某数.特别的,当K的二进制数为全1时,如 7:(111)2 为3位。若不为全1,如9:(1011)2则为3位。
第二步:
求出第K个数是从 44……444开始数的第几个数。如74,是从44开始数的第3个数。
第四步:
不妨假设K = 12 ,那么二进制为3位,开始数的数则为:444(对应第(111)2=7个数)。12 - 7 +1 = 6. 那么也就是从444开始数的第6个数字(计444为第1个数字,所以要加一)。如何构造呢?
我也发现个规律:观察:
444
447
474
477
744
747
……
这时我们可以发现第6个数字是 747. 这个数字开头为7,原因是4开头抢去了4个地盘,这4个地盘怎么抢去的呢? 是4、7排列的结果,为2*2,即(1<<(wei-1))=4。
数字第一位确定了,为7。那么现在从744往下数,第6-4=2个数。确定第二位为4,因为4开头确定了44,47.那么2<=2个地盘, 所以第二个位为4. 接着确认第三位,从744往下数第二个,第三位确定为7,方法同上.
构造完成。
代码:
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
int g(LL x)
{
int re = 0;
bool flag = true;
while(x)
{
if(!(x&1)) flag = false;
re++;
x = (x>>1);
}
if(flag == false)
return re-1;
return re;
}
LL f(LL x, int wei)
{
while(wei)
{
x = x - (1LL<<wei); //一I定要记得加LL。wei最大可以为60,1<<wei可能超过int
// cout << (1LL<<wei) << endl;
wei--;
}
return x;
}
int main()
{
int T;
LL a;
scanf("%d", &T);
while(T--)
{
scanf("%lld", &a);
int wei = g(a);
LL Nth = f(a, wei-1);//从44……4开始数,第几个
// cout << Nth << endl;
while(wei)
{
wei--;
LL cmp = (1LL<<wei);
// cout << "Nth: " << Nth << "cmp: " << cmp << endl;
if(Nth <= cmp)
putchar('4');
else
{
putchar('7');
Nth -= cmp;
}
}
putchar('\n');
}
}
/*
3
10000000000
10000000001
10000000002
*/
转载于:https://www.cnblogs.com/Airplus/p/5844282.html