poj 1019 Number Sequence

http://poj.org/problem?id=1019

题意:1 12 123 1234 12345 一窜数字 求第n位的数字是什么

分析:拿到题就是不会。。。

         看了题解

         a[i]计算i数字的位数,s[i]计算到达i数字的总位数

         i数字的位数log10(i)+1  

#include<stdio.h>
#include<math.h>
const int MAXN=40000;
long long  a[MAXN];
long long  s[MAXN];
void init()
{
    s[1]=a[1]=1;
    for(int i=2;i<MAXN;i++)
    {
        a[i]=a[i-1]+(int)log10((double)i)+1;
        s[i]=s[i-1]+a[i];
    }
}

int compute(int n)
{
    int pos,i=1;
    while(s[i]<n) i++;//找出第i个数字的位数和是大于n的

    pos=n-s[i-1];//计算出n位是第i个数字的第几位
    int len=0;
    for(i=1;len<pos;i++)//找出那个数字i
        len+=(int)log10((double)i)+1;

    return (i-1)/(int)pow(10.0,len-pos)%10;//i-1是上一个循环i多加了一次,len-pos是‘
      //所求位数字的后面那几位要除掉,在%10就是所求位的数字了
}

//例如5 s[3]=112123,pos=5-s[2]=2;循环中所能找到的len=3,i=3; 2/1%10=2;

int main()
{
    int T,n;
    init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%d\n",compute(n));
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每天一算:Reverse String

我们会在每天早上8点30分准时推送一条LeetCode上的算法题目,并给出改题目的动画解析以及参考答案,每篇文章阅读时长为五分钟左右。

892
来自专栏IT可乐

深入理解计算机系统(2.3)------布尔代数以及C语言运算符

  本篇博客我们主要讲解计算机中的布尔代数以及C语言的几个运算符。 1、布尔代数   我们知道二进制值是计算机编码、存储和操作信息的核心,随着计算机的发展,围绕...

2335
来自专栏Golang语言社区

Golang 中"泛型"的支持

Golang不支持一般的类似java中的标记式泛型。很多人因此而十分不满,认为没有泛型增加了很多工作量。而目前由于泛型支持的复杂性,Golang的设计和实现者并...

37413
来自专栏尾尾部落

[剑指offer] 不用加减乘除做加法

872
来自专栏数据结构与算法

洛谷P3804 【模板】后缀自动机

1303
来自专栏程序生活

Leetcode-Easy 796. Rotate String

796. Rotate String 描述: 有两个字符串A和B,将A的第一个字符左移到最后位置,判断此时A是否等于B,如果等于返回true。不等于则继续左...

2865
来自专栏chenjx85的技术专栏

leetcode-204-Count Primes

2558
来自专栏swag code

swap()交换两个变量的方法汇总

984
来自专栏数据结构与算法

1462 素数和

1462 素数和 时间限制: 1 s 空间限制: 64000 KB 题目等级 : 青铜 Bronze 题目描述 Description 给定2个整...

2797
来自专栏木子昭的博客

寻找"单身数"

一个有N个数的数组里, 每个数字都出现两次, 现在取出一个数, 根据剩下的数字, 猜测取出的数的值(要求时间复杂度为N, 空间复杂度为1) 异或运算 两个相同...

2635

扫码关注云+社区

领取腾讯云代金券