CF95B Lucky Numbers 题解

· · 题解

题目传送门

我们可以把整道题分成两种情况来做。

Part 1 当数字的长度为奇数

假设数字长度为 len 。

因为不存在长度为奇数的超级幸运数字，所以答案就为长度为 len + 1 的最小的超级幸运数字，也就是输出 \frac{( len + 1 )}{2} 个 4 和 \frac{( len + 1 )}{2} 个 7 。

给出代码：

//字符串s在前面已定义过（string s）
cin>>s;
if(s.size()%2==1)//如果长度为奇数
{
    for(int i=0;i<(s.size()+1)/2;i++) cout<<4;
    for(int i=0;i<(s.size()+1)/2;i++) cout<<7;
    return 0;
}

Part 2 当数字的长度为偶数

我们知道，长度为 n 的超级幸运数字的最大值为 \frac{n}{2} 个 7 和 \frac{n}{2} 个 4组合在一起。

所以我们可以判断输入的数字是否大于这个最大值。

如果大于这个最大值，就可以直接输出 ( \frac{n}{2} + 1 ) 个 4 和 ( \frac{n}{2} + 1 ) 个 7 。

给出这一部分的代码：

string maxs;//maxs为长度为s.size()的超级幸运数字的最大值
for(int i=0;i<s.size()/2;i++) maxs+='7';
for(int i=0;i<s.size()/2;i++) maxs+='4';
if(maxs<s)//由于maxs和s为string类型，可以直接用"<"。
{
    for(int i=0;i<s.size()/2+1;i++) cout<<4;
    for(int i=0;i<s.size()/2+1;i++) cout<<7;
    return 0;
}

接下来就是普通情况了。这里我写了一个DFS。

string ans;
void dfs(int p,int cnt_4,int cnt_7)
{
    if(ans<s) return;
    if(p==s.size())
    {
        cout<<ans;
        exit(0);
    }
    if(cnt_4<s.size()/2)
    {
        ans[p]='4';
        dfs(p+1,cnt_4+1,cnt_7);
    }
    if(cnt_7<s.size()/2)
    {
        ans[p]='7';
        dfs(p+1,cnt_4,cnt_7+1);
    }
}

其中， p 表示当前填写数字的位置， cnt\_4 表示当前数字4的数量，cnt\_7 表示当前数字7的数量。

当 ans 比 s 还小，不管接下来怎么填，ans 都比 s 小，所以直接return;。

然后，判断是否已经填完数字。如果填完数字，可以直接输出。因为DFS中我们先的填 4 ,再填的 7 。

最后，如果能填4或7，就填数。

在主函数里这样调用：

for(int i=0;i<s.size();i++) ans+='9';//先把ans设为999999…，避免填过的数与输入数字前半部分一样，却返回了。
dfs(0,0,0);

下面给出完整代码：

#include<bits/stdc++.h>
using namespace std;
string s,ans;
void dfs(int p,int cnt_4,int cnt_7)
{
    if(ans<s) return;
    if(p==s.size())
    {
        cout<<ans;
        exit(0);
    }
    if(cnt_4<s.size()/2)
    {
        ans[p]='4';
        dfs(p+1,cnt_4+1,cnt_7);
    }
    if(cnt_7<s.size()/2)
    {
        ans[p]='7';
        dfs(p+1,cnt_4,cnt_7+1);
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>s;
    if(s.size()%2==1)
    {
        for(int i=0;i<(s.size()+1)/2;i++) cout<<4;
        for(int i=0;i<(s.size()+1)/2;i++) cout<<7;
        return 0;
    }
    string maxs;
    for(int i=0;i<s.size()/2;i++) maxs+='7';
    for(int i=0;i<s.size()/2;i++) maxs+='4';
    if(maxs<s)
    {
        for(int i=0;i<s.size()/2+1;i++) cout<<4;
        for(int i=0;i<s.size()/2+1;i++) cout<<7;
        return 0;
    }
    for(int i=0;i<s.size();i++) ans+='9';
    dfs(0,0,0);
    return 0;
}