TIMU:
题目描述
抽奖环节让所有的同学都很兴奋，有的同学兴奋是因为抽到了想要的东西，但有的同学抽到的却是不想要的，比如寒假活动大礼包。还有的人则抽到了好几个奖，羡慕死其他同学了。
在联欢会临近结束的时候， 抽奖的最后一个环节是同学们可以把自己的奖品让给其他同学，但是让的话也是有规则的。这个规则就是幸运数指定。一位获奖的同学，他要根据自己的抽奖号码 n，然后想一个数 m，计算符合要求的幸运数有多少个。
所谓幸运数字，是指一个数字，如果它的数位的平均数不超过m，那么这个数字称为幸运数。
例 如 当 m=5 时 ， 1234567890 和 123456789 是 幸 运 数 ， 因 为(1+2+3+4+5+6+7+8+9+0)/10=4.5 < 5，(1+2+3+4+5+6+7+8+9)/9 = 5；
而99 则不是幸运数，因为(9+9)/2=9 > 5。
给定一位同学的抽奖码n和他想的数 m，统计 1~n 之间有多少个幸运数。
输入
一行，两个整数 n 和 m
输出
一个整数，1~n 之间幸运数的个数。
样例输入 Copy
19 3
样例输出 Copy
9
提示
【样例 2 输入】
2022 5
【样例 2 输出】
1516
【样例 3 输入】
123512353 8
【样例 3 输出】
123503565
【样例 1 说明】
第一个样例 1,2,3,10,11,12,13,14,15 是幸运数
【数据范围】
对于 30%数据：1<=n<=10^5, 1<=m<=9
对于 70%数据：1<=n<=10^9, 1<=m<=9
对于 100%数据：1<=n<=10^18, 1<=m<=9
还没看数据大小就直接写暴力：
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int ans=0;
for(int i=1;i<=n;i++)
{
double sum=0,cnt=0;
int x=i;
while(x)
{
sum+=x%10;
x/=10;
cnt++;
}
if(sum/cnt<=m)ans++;
}
cout<<ans;
return 0;
}
俗话说暴力出奇迹，可是为什么（凉凉code~）
时间超限tttttttt!
🔑后来发现可以用搜索🔍写🎇🎇，定义一个flag表示当前一位能否随便填
其实我的这个代码是错的
int ans=0;
int n[20],m,N; //n为了好用所以用数组存储
long long x;
void dfs(int i,int sum,int cnt,bool flag){
if(i==N){ //当时在这里犹豫不定
// printf("%d %d %d %d\n",i,sum,cnt,flag);
if(cnt)ans+=sum<=m*cnt;
return;
}
for(int a=0;a<=(flag?9:n[i]);a++)
dfs(i+1,sum+a,cnt+(cnt||a),flag||a<n[i]);
}
可是又凉凉code~
时间超限！！！！！！（吼出来的）
于是又加了个记忆化：
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>
using namespace std;
int ans=0;
int n[20],m,N;
long long x;
long long dp[20][200][20][2];
long long dfs(int i,int sum,int cnt,bool flag){
if(i==N){
return cnt&&sum<=m*cnt;
}long long& d=dp[i][sum][cnt][flag];
if(~d)return d;
d=0;
for(int a=0;a<=(flag?9:n[i]);a++) d+=dfs(i+1,sum+a,cnt+(cnt||a),flag||a<n[i]);
return d;
}
int main()
{memset(dp,-1,sizeof(dp));
cin>>x>>m;
long long n2=0;
while(x){
n2=n2*10+x%10;
x/=10;
}
while(n2){
n[N++]=n2%10;
n2/=10;
}
cout<<dfs(0,0,0,0);
return 0;
}
这次，我自信满满的交了，等待着好消息，结果…
[答案错误91]？？？？？？！！！！
为什么呢？
我不停的测其他的样例，我决定侧式一下极端情况：
1000000000000000000 9
本来的ans应该是1000000000000000000可是输出的竟然是1？
这时候我才恍然大悟，原来我的n2没有判断后导0，把后导0删掉了n[i]=0就是会被判定成没有。
所以我直接用字符串：
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>
using namespace std;
long long n[30],m,N;
long long dp[30][200][30][5];
long long dfs(int i,int sum,int cnt,bool flag){
if(i==N)return cnt&&sum<=m*cnt;
long long& d=dp[i][sum][cnt][flag];
if(~d)return d;
d=0;
for(int a=0;a<=(flag?9:n[i]);a++) d+=dfs(i+1,sum+a,cnt+(cnt||a),flag||a<n[i]);
return d;
}
int main()
{
memset(dp,-1,sizeof(dp));
string x;
cin>>x>>m;
for(int i=0;i<x.size();i++){
n[i]=x[i]-'0';
}N=x.size();
cout<<dfs(0,0,0,0);
return 0;
} //AC!!!
🎆🎆🎆🎆🎆终于AC啦！！！！！！🧨🧨🧨🧨🧨🧨🧨
