题解 P6445 【[COCI2010-2011#1] SRETAN】

wuyonghuming · 2020-04-21 15:56:57 · 题解

思路：

这道题目就像二进制一样，只有两个数，可以按二进制的做法试试（十进制转二进制）。

我们不妨先弄张表，从里面找找规律，用s表示答案。

表格：

发现：

上一行和这一行中，前面总会有重叠的一部分。

假设这个数的位置是i。

现在发现，位置(i-1)/2的数，总会是位置i的那个数的前面那一部分。

接着，我们又发现：位置是偶数的最后一位一定是7，位置是奇数的最后一位一定是4。

公式：

当i是奇数时：s_i=s_{(i-1)/2}*10+4

当i是偶数时：s_i=s_{(i-1)/2}*10+7

方法：

可以从后往前算，每次算出最后一位，到最后，答案就算出来了。但是要倒叙输出。

注意事项：

答案可能非常大，long long也存不下，最好用字符串来记录答案！！！

代码：

#include <bits/stdc++.h>//头文件
using namespace std;
int main()
{
    long long k;//第k个幸运数
    string ans="";//这个记录答案
    cin>>k;//输入k
    while(k>0)//当它大于零
    {
        if(k%2==0)//如果除以2余数是0
            ans+='7';//加上7
        else//否则
            ans+='4';//加上4
        k=(k-1)/2;//现在到了它的上一行
    }
    for(int i=ans.size()-1;i>=0;i--)//size是长度
        cout<<ans[i];//输出答案
    return 0;//别忘了
}

总结：

遇到这种类似的题目，做了很久做不出来时，可以打表看看答案，最后再来写代码。

感谢：

谢谢大家的观赏，谢谢管理抽出时间审核！！！