牛客练习赛13 幸运数系列

119 阅读 0 评论 79 点赞

我是靠谱客的博主专注灰狼，最近开发中收集的这篇文章主要介绍牛客练习赛13 幸运数系列，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

***个人认为这4题出的相当好！

定义: 一个数的数位上数字均是4或7，称为‘幸运数’；

幸运数字I

题意：求出字符串s的出现最多次数的幸运子串，有多个，求字典序最小的。

任何幸运数都由4和7组成，考虑字典序最小，满足题意的幸运子串的长度为1；

例：44由4构成，4出现一定不小于其2倍；77同理；47由4和7组成，4出现的次数不小于47，且4的字典序小于7、47；

所以有答案一定是4或者7；

num_4==0&&num_7==0, 无幸运数，输出“-1”；

num_4>=num_7,输出"4";

num_4 < num_7,输出"7";

#include <iostream>
#include <string.h>
using namespace std;
 
int main()
{
    string s;
    cin>>s;
    int a=0,b=0;
    for(int i=0;i<s.length();++i)
        if(s[i]=='4')++a;
        else if(s[i]=='7')++b;
 
    if(a==0&&b==0)cout<<-1<<endl;
    else if(a>=b){
        cout<<4<<endl;
    }else {
        cout<<7<<endl;
    }
    return 0;
}

幸运数字II

题意：定义next(x)不小于x的第一个幸运数字，求区间[l,r]内所有数的next的和；(r<=1e9)

千万不要走进数位dp的坑！

不大于next(1e9)的幸运数的个数不超过1050个！记ai为所有4位数的幸运数的个数，a1=2；

ai+1 = ai (第i+1位放4） + ai （第i+1位放7），得ai=2^i, Si=2^(i+1)-2;(i<=9）

*按升序顺序求出Si个幸运数

(可以将ai中所有数字的第i+1位上添4，在添7）；

但从Code的角度来说，将ai中每个数字乘10在分别加4、7更加合适！

*遍历ai，调整l，找出区间中next(x)=ai，x的个数，并调整区间左端点l=ai+1；

#include <iostream>
#include <string.h>
#include <vector>
#define llt long long
using namespace std;

int main()
{
    llt l,r;
    cin>>l>>r;
    vector<llt> V;
    V.push_back(4);V.push_back(7);
    for(int i=2;i<=10;++i){
        for(int j=(1<<(i-1))-2;j<(1<<i)-2;++j){
            V.push_back(V[j]*10+4);
            V.push_back(V[j]*10+7);
        }
    }
    llt ans=0;
    for(int i=0;i<V.size();++i){
        //if(l>=r)break;
        if(V[i]<l)continue;

        if(V[i]>=r){ans+=(r-l+1)*V[i];break;}
        ans+=V[i]*(V[i]-l+1);
        l=V[i]+1;
    }

    cout<<ans<<endl;
    return 0;
}

幸运数字III

题意：数字字符串d1d2……dn，对其进行k次操作，每次操作：找出最左侧的dxdx+1="47";

*x为奇数，将dxdx+1变为“44”

*x为偶数，将dxdx+1变为“77”

输出最后的字符串；

遍历字符串，遇到di=‘4’，即测试一下di+1是否为‘7’，如果不为‘7’，即继续遍历；如果di+1==‘7’：

讨论：i为奇数，将di+1变为‘4’，继续向下遍历；

i为偶数，将di变为‘7’，di-1为‘7’，继续向下遍历，如果di-1为‘4’，（i-1奇、i偶、i+1奇）

那么477-->447--->477--->447,操作会在此处以2循环下去，仅需判断此时k的奇偶，k为偶不变，k为奇仅操作1次；

时间复杂度变为O(len)非O(k)!

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
#define llt long long
using namespace std;
 
char  s[100010];
int main()
{
    int n,k;
    cin>>n>>k;
 
    scanf("%s",s);
 
    int l=1;
    while(k){
        if(l>=n){break;}
        if(s[l-1]!='4'||s[l]!='7'){++l;continue;}
 
 
        --k;
        if(l%2==1) {s[l]='4';++l;continue;}
        s[l-1]='7';
         
        if(s[l-2]=='4'){
            if(k%2){s[l-1]='4';}
            break;
        }
    }
    printf("%s",s);
 
}

幸运数字IV

题意：数字1……n的第k小排序中，数字即其位置均为幸运数字的个数；(k<=1e9)

如果n！<k,输出-1！

1e9 对n！来说是个小数字，13！>k; n很大时，前面1……(n-13)的顺序不变，我们考虑的仅仅是13个数字的顺序！

***求出1……13的阶乘a；将需要排序的最后数字放入b数组；

***如果n>13的话，我们需要求出前n-13个数字中幸运数字的个数，将r=n-13的所有数位求出，最高位temp-1为0的

幸运数个数S=2^temp-2；ans+=S;下面的所有幸运数中不能在有数位0！只允许4和7！

从高位i开始，dight[i]<4 ,return; （第i位不能取到4或7，结束！）

dight[i]==4, ans+=(i==0),继续遍历，（i==0，即结束了遍历，前面数位和最后的数位均为4和7，即r为幸运数）

ans+=2^i（即第i位为4，其它数位任取4和7，幸运数的个数）

dight[i]<7（第i位不能取到'7',结束！）

dight[i]==7, ans+=(i==0),继续遍历，（i==0，即结束了遍历，前面数位和最后的数位均为4和7，即r为幸运数）

ans+=2^i（即第i位为7，其它数位任取4和7，幸运数的个数）

return；(已经讨论完全，第i位为8、9绝对不是幸运数）

***对剩下的数进行排序，如果（i-1）*a[len-1]<k<=i*a[len-1],即此时因排bi于此时首位！将bi删去，len减1，

k-=（i-1）*a[len-1]；判断：bi和其位置start是否都是幸运数，是，ans++；直到len为0，就结束！

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <vector>
#define llt long long
#define Size 100010
using namespace std;

int a[15];
int b[15];
int n,k,start,len;
int ans=0;

bool isUNF(int x){
    while(x){
        if(x%10!=4&&x%10!=7)return false;
        x/=10;
    }
    return true;
}

void Havenum(int x){
    int dight[12];
    int temp=0;
    while(x){
        dight[temp++]=x%10;
        x/=10;
    }

    ans=(1<<temp)-2;

    for(int i=temp-1;i>=0;--i){
        //printf("%dn",ans);
        if(dight[i]<4)return;
        if(dight[i]==4){ans+=(i==0);continue;}
        ans+=(1<<i);
        if(dight[i]<7) return;
        if(dight[i]==7){ans+=(i==0);continue;}
        ans+=1<<i;
        return ;
    }
}
void init(){
    a[0]=1;
    for(int i=1;i<=13;++i)
        a[i]=a[i-1]*i;
    //printf("%dn",a[13]);
    start=1;
    if(n>13){
        start=n-12;
        Havenum(n-13);
    }
    len=0;
    for(int i=start;i<=n;++i) b[++len]=i;
}

void Delete(int x){
    for(int i=x;i<len;++i) b[i]=b[i+1];
    --len;
}
int main()
{
    scanf("%d%d",&n,&k);
    init();
    if(n<=13&&k>a[n]) printf("-1n");

    else{
        //printf("%dn",ans);
        while(start<=n){
           int i;
           for(i=1;;++i) if(k<=i*a[len-1])break;
           k-=(i-1)*a[len-1];
           if(isUNF(start)&&isUNF(b[i]))++ans;
           Delete(i);
           ++start;
        }

           printf("%dn",ans);
       }
    return 0;
}