华师一附中OI组

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 2549|回复: 8
打印 上一主题 下一主题

1-m之间的自然数排成一排其中8出现了多少次

[复制链接]

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
跳转到指定楼层
楼主
发表于 2018-5-1 14:31:38 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式
1、最直接的方法是模拟,碰到一个数字,就分解它,统计8的个数,这样很直观,但是这显然不是最好的方法,时间复杂度太高。
2、另外一种分析就是统计法,0-9 之间有1个8,0-99之间有20个,0-999之间有300个*** 。0-m之间的数字化成很多区间去统计,这样逻辑比较复杂,但是程序运行会很快。
回复

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
推荐
 楼主| 发表于 2018-5-1 14:32:23 | 只看该作者
第二种方法
回复 支持 2 反对 0

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
推荐
 楼主| 发表于 2018-5-9 20:11:03 | 只看该作者
wzd同学的这个做法是我比较认同的一种做法,非常好,但是就是程序写得不漂亮,我来给他改一改
回复 支持 1 反对 0

使用道具 举报

61

主题

147

帖子

563

积分

超级版主

Rank: 8Rank: 8

积分
563
推荐
发表于 2018-5-2 16:36:39 来自手机 | 只看该作者
wyl同学的这个方法很新颖,请他讲讲自己的思路。
回复 支持 1 反对 0

使用道具 举报

738

主题

1485

帖子

5422

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
5422
推荐
 楼主| 发表于 2018-5-1 14:32:05 | 只看该作者
  1. #include<iostream>
  2. using namespace std;
  3. int s,i,x,n,t;
  4. int main()
  5. {
  6.     cin>>n;
  7.     for (i=1;i<=n;i++)
  8.     {
  9.         x=i;  ///保存现场
  10.         while (x!=0)
  11.         {
  12.             t=x%10;x=x/10;  
  13.             if (t==8) s++; ///  s+=(t==8)
  14.         }
  15.     }
  16.     cout<<s;
  17.     return 0;
  18. }
复制代码
回复 支持 1 反对 0

使用道具 举报

2

主题

105

帖子

306

积分

中级会员

Rank: 3Rank: 3

积分
306
地板
发表于 2018-5-1 20:32:31 | 只看该作者
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <cstdlib>
  6. using namespace std;
  7. long long to=1,all=0;
  8. char a[10000];
  9. int main()
  10. {
  11.     scanf("%s",a);
  12.     int l=strlen(a);
  13.     for(int i=l-1,j=0;i>=0;i--,j++)
  14.     {
  15.         if(a[i]>='8')
  16.             all+=to;
  17.         all+=((j*to/10)*(a[i]-'0'));
  18.         to*=10;
  19.     }
  20.     printf("%lld",all);
  21.     return 0;
  22. }
复制代码
回复 支持 反对

使用道具 举报

0

主题

8

帖子

56

积分

注册会员

Rank: 2

积分
56
6#
发表于 2018-5-4 23:01:27 | 只看该作者
#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;
}
回复 支持 反对

使用道具 举报

0

主题

8

帖子

56

积分

注册会员

Rank: 2

积分
56
7#
发表于 2018-5-4 23:54:21 | 只看该作者
  1. #include <cstdio>
  2. #include <cstdlib>
  3. using namespace std;
  4. int m;
  5. int dfs_(int k)
  6. {
  7.     if(k<10 && k>=8)
  8.         return 1;
  9.     if(k<8)
  10.         return 0;

  11.     int temp=k;
  12.     int MOD=1;
  13.     while(temp>0)
  14.     {
  15.         temp=temp/10;
  16.         MOD*=10;
  17.     }
  18.     MOD/=10;
  19.     int first=k/MOD;
  20.     if(first>=8)
  21.     {
  22.         if(first==8)
  23.             return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+(k-MOD*first+1));
  24.         else
  25.             return (first*dfs_(MOD-1)+dfs_(k-MOD*first)+MOD);
  26.     }
  27.     else
  28.         return (first*dfs_(MOD-1)+dfs_(k-MOD*first));
  29. }
  30. int main()
  31. {
  32.     scanf("%d",&m);

  33.     printf("%lld\n",dfs_(m));

  34.     return 0;
  35. }
复制代码
回复 支持 反对

使用道具 举报

2

主题

105

帖子

306

积分

中级会员

Rank: 3Rank: 3

积分
306
9#
发表于 2018-5-10 15:09:28 | 只看该作者
本帖最后由 吴语林 于 2018-5-10 15:14 编辑

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

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

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|Archiver|手机版|小黑屋|服务支持:DZ动力|华师一附中OI组  

GMT+8, 2024-12-25 15:05 , Processed in 0.107122 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表