首页 > 代码库 > PKU 1019 Number Sequence(模拟，思维)

PKU 1019 Number Sequence(模拟，思维)

2024-07-22 17:17:11   219人阅读

题目

 

以下思路参考自discuss：http://poj.org/showmessage?message_id=176353

 

/*我的思路：1.将长串数分成一个个部分，每个部分是从1到x的无重复的数字序列2.每个序列比前一个序列多的位数是他的最后一个数的位数，如12345678910比123456789多最后一个10，  即多占了两位，由此可推算出任何一个序列的长度3.输入位置n，则从1到n查找，每次位置移动一个序列的长度，如果第j个加上序列长度超过n，则输出j这个整数的从个位数第j-n+1位上的数字*/

 

#include<iostream>#include<string>#include<stdio.h>#include<string.h>#include<math.h>#include<algorithm>using namespace std;int len[40000];//len[i] 最后为i的数列的长度void init(){    len[1]=1;    for(int i=2;i<40000;i++)    {        int num=0,ii=i;        while(ii){            num++;            ii=ii/10;        }        len[i]=len[i-1]+num;    }}int main() {    init();    int t,n;    scanf("%d",&t);    while(t--)    {        scanf("%d",&n);        int i=1;        while(n>len[i]){            n=n-len[i];            i++;        }        int j=1;        for(;j<=i;j++)        {            int num=0,ii=j;            while(ii){                num++;                ii=ii/10;            }            if(n-num>0)                n=n-num;            else            {                int ni=0;                while(j)                {                    ni=ni*10+(j%10);                    j=j/10;                }                while(--n)                {                    ni=ni/10;                }                printf("%d\n",ni%10);                break;            }        }    }    return 0;}
View Code

 

PKU 1019 Number Sequence(模拟，思维)


联系
我们