华师一附中OI组

标题: 1-m之间的自然数排成一排其中8出现了多少次 [打印本页]

作者: admin 时间: 2018-5-1 14:31
标题: 1-m之间的自然数排成一排其中8出现了多少次
1、最直接的方法是模拟，碰到一个数字，就分解它，统计8的个数，这样很直观，但是这显然不是最好的方法，时间复杂度太高。
2、另外一种分析就是统计法，0-9 之间有1个8，0-99之间有20个，0-999之间有300个*** 。0-m之间的数字化成很多区间去统计，这样逻辑比较复杂，但是程序运行会很快。

作者: admin 时间: 2018-5-1 14:32

#include<iostream>
using namespace std;
int s,i,x,n,t;
int main()
{
cin>>n;
for (i=1;i<=n;i++)
{
x=i; ///保存现场
while (x!=0)
{
t=x%10;x=x/10;
if (t==8) s++; /// s+=(t==8)
}
}
cout<<s;
return 0;
}

复制代码

作者: admin 时间: 2018-5-1 14:32
第二种方法

作者: 吴语林 时间: 2018-5-1 20:32

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
using namespace std;
long long to=1,all=0;
char a[10000];
int main()
{
scanf("%s",a);
int l=strlen(a);
for(int i=l-1,j=0;i>=0;i--,j++)
{
if(a[i]>='8')
all+=to;
all+=((j*to/10)*(a[i]-'0'));
to*=10;
}
printf("%lld",all);
return 0;
}

复制代码

作者: diggersun 时间: 2018-5-2 16:36
wyl同学的这个方法很新颖，请他讲讲自己的思路。

作者: wzd(temp) 时间: 2018-5-4 23:01
#include <cstdio>
#include <cstdlib>
using namespace std;
int m;
int dfs_(int k)
{
if(k<10 && k>=8)
      return 1;
if(k<8)
      return 0;

int i=0;
int temp=k;
int MOD=1;
while(temp>0)
{
      temp=temp/10;
      i++;
      MOD*=10;
}
MOD/=10;
int first=k/MOD;
if(first>=8)
{
      if(first==8)
         return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+(k-MOD*first+1));
      else
         return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+MOD);
}
else
      return (first*dfs_(MOD-1)+dfs_(k-MOD*first));
}
int main()
{
scanf("%d",&m);

printf("%d\n",dfs_(m));

return 0;
}

作者: wzd(temp) 时间: 2018-5-4 23:54

#include <cstdio>
#include <cstdlib>
using namespace std;
int m;
int dfs_(int k)
{
if(k<10 && k>=8)
return 1;
if(k<8)
return 0;
int temp=k;
int MOD=1;
while(temp>0)
{
temp=temp/10;
MOD*=10;
}
MOD/=10;
int first=k/MOD;
if(first>=8)
{
if(first==8)
return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+(k-MOD*first+1));
else
return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+MOD);
}
else
return (first*dfs_(MOD-1)+dfs_(k-MOD*first));
}
int main()
{
scanf("%d",&m);
printf("%lld\n",dfs_(m));
return 0;
}

复制代码

作者: admin 时间: 2018-5-9 20:11
wzd同学的这个做法是我比较认同的一种做法，非常好，但是就是程序写得不漂亮，我来给他改一改

作者: 吴语林 时间: 2018-5-10 15:09
本帖最后由吴语林于 2018-5-10 15:14 编辑

吴语林发表于 2018-5-1 20:32

a>='8' 额外加一个 10^位数

其他以正常方式累加 ps：加10^(位数-1)*位数