XTU 1227 Digit

最新推荐文章于 2021-12-10 13:52:49 发布

ACM__dongsheng

最新推荐文章于 2021-12-10 13:52:49 发布

阅读量701

点赞数

分类专栏：规律

本文链接：https://blog.csdn.net/ACM__dongsheng/article/details/51549863

版权

规律专栏收录该内容

13 篇文章

订阅专栏

题目描述

我们把十进制整数依次写成一个字符串，123456789101112…请问第n位数码是多少？
输入

第一行是一个整数T(T≤10000)，表示样例的个数。每行输入一个整数n(1≤n≤788888899)。
输出

每行输出一个样例的结果。
样例输入

2
1
788888899

样例输出

1
1
最近在湘大oj上刷题，为湘大比赛做准备。感觉有点坑，题目不同的提交方式，竟然结果不同，无语了，然后花大量的时间找BUG,无语了！
分析：这一题直接做的暴力，估计会GG,数据有点大。所以我先对1,到9位的数所占的位数都算出来了，比如一位数有 1,2，3,4，5,6,7,8,9 : 2位数有 10 到99 :3位数有100到999。然后具体求输入n所对应的数，并求它的位。.

#include<iostream>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#include<cstdio>
using namespace std;
__int64  s[10000];
char st[2000];
int main()
{
    s[0]=0,s[1]=9 ;
    __int64 x=9 , y=1;
     for(int i=2; i<=9 ;i++)
     {
        x=x*10+9 ,y*=10;
        s[i]=(x-y+1)*i;
     }

     for(int i=2; i<=9 ;i++)//前n位数之和
     {
        s[i]+=s[i-1];
     }
     int t;
     scanf("%d",&t);
     while(t--)
     {
        __int64  b;
        scanf("%I64d",&b);
        int k,flag=0;
        for(int i=1;i<=9;i++)
        {
            if(s[i]>b) //找到在几位数之间 
            {
                k=i;//k代表 n是几位数
                break;
            }
             if(s[i]==b)//位全是9的情况
            {
                flag=1;
                printf("9\n");
                break;
            }
        }
        if(flag)
        continue;
         __int64 sum;
        sum=b-s[k-1];
        __int64   sum1=sum/k,sum2=sum%k;//sum1 cong 9999…………(k-1个9)扩展sum个位，也就是+sum1,sum2用来处理扩展为不是K整数情况。
        if(sum2!=0)
        {
                k--;
              __int64  n=pow(10,k*1.0);
            n+=sum1;
            sprintf(st,"%I64d",n);
            printf("%c\n",st[sum2-1]);
        }
        else
        {
            k--;
            __int64  n=pow(10,k*1.0);
            n+=(sum1-1);
            sprintf(st,"%I64d",n);
            printf("%c\n",st[k]);
        }
     }
    return 0;
}