牛客练习赛13

链接:牛客练习赛13

A幸运数字1

  • 幸运数字是只含4,7的数字,给一个字符串,求出现次数最多的且是幸运数字的子串

    题解

  • 没啥说的,答案只有4,7,-1三种可能

    B幸运数字2

  • next(x)表示比x大的第一个幸运数字,给定l,r,求出next(l)+…+next(r)

    题解

  • 我的做法是跑出所有幸运数字,1-1e10中最多2^9个,然后二分l和r在数组中的位置,累加答案
  • 实际上不需要二分,对于幸运数字i来说,满足next(x)==i的只有上一个幸运数字y的后一个数y+1到i的那些
  • 不多说,上代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,x,y) for(register int i=x;i<=y;++i)
#define repd(i,x,y) for(register int i=x;i>=y;--i)
#define ll long long
using namespace std;
const int N=1e6;
ll c[N],len,ans,l,r;
int main(){
rep(i,1,10)rep(j,0,(1<<i)-1){
ll num=0;
rep(k,0,i-1)if(j>>k&1)num=num*10+4;else num=num*10+7;
c[++len]=num;
}
sort(c+1,c+len+1);
scanf("%d%d",&l,&r);
for(int i=1;l<=r;++i)if(c[i]>=l)ans+=(ll)(min(r,c[i])-l+1)*c[i],l=c[i]+1;
printf("%lld",ans);
return 0;
}

C幸运数字3