POJ 1019 Number Sequence (数学+预处理 循环递增序列第k位数字)

题目链接

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

题目大意

有一串数字串，其规律为 1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011 123456789101112······k 输入位置n，计算这一串数字第n位是什么数字。

分析

大致思路就是将这一串数按循环节分组，确定第n位数组出现在第几组，在那一组中有处在第几个位置，然后确定那位数是多少。 要确定这些东西，就需要预处理，用a[i]记录第i组序列的总位数，用s[i]记录前i组序列的总位数。这里记录一个重要的数学技巧，求一个数的位数可以用公式(int)log10((double)i)+1。 当确定第n位数在第x组序列时，我们需去除其后面多余的数，再取出该位数，这部分详见代码。

代码

#include <iostream> #include <cmath> #define LL long long int #define MAXN 40000 using namespace std; LL a[MAXN],s[MAXN]; void Init()//预处理打表 { a[1]=s[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 Count(int n) { int i=1,pos,len; while (s[i]<n) //确定第n位在哪一组 i++; pos=n-s[i-1]; //确定第n位在自己组里面的位置 len=0; for (i=1;len<pos;i++) len+=(int)log10((double)i)+1; return (i-1)/(int)pow((double)10,len-pos)%10; //之所以i-1，是因为前面寻找第i组长度时，i++多执行了一次 //i=i-1 此时i刚好等于第n位个置上的数 （数是整体，例如123一百二十三，i刚好等于123，但n指向的可能是1，2或3） //pos为n指向的数字在第i组中的下标值 //len为第i组的长度 //那么len-pos就是第i组中pos位置后多余的数字位数 //则若要取出pos位上的数字，就要利用(i-1)/pow(10,len-pos)先删除pos后多余的数字 //再对剩下的数字取模，就可以得到pos //例如要取出1234的2，那么多余的位数有2位：34。那么用1234 / 10^2，得到12，再对12取模10，就得到2 } int main() { int t,n; Init(); cin>>t; while (t--) { cin>>n; cout<<Count(n)<<endl; } return 0; }

在这道题的DISCUSS中，看见一份用二分low_bound函数实现的代码，觉得也写得十分巧妙，因此也记录一下这种解法。

#include<cstdio> #include<algorithm> using namespace std; unsigned group[40000], sum[40000];//题目中给的最大数据一定不会超过40000组（粗略） int main() { int t, i, j, k, n, ans; char s[10]; scanf("%d", &t); group[0] = 0, sum[0] = 0; for( j=1; j<40000; j++) { group[j] += group[j-1] + 1 + (j/10 > 0) + (j/100 > 0) + (j/1000 > 0) + (j/10000 > 0);//递推计算第j组里有几个数字 sum[j] = sum[j-1] + group[j];//计算前j组数字个数之和 } while( t-- ) { scanf("%d", &i); k = lower_bound(sum, sum+40000, i) - sum;//计算第i个数位于哪个组 n = i - sum[k-1];//计算该数位于该组中的第几个位置 k = lower_bound(group, group+40000, n) - group;//找到位于哪个数中 n -= group[k-1];//该数的第几个位置 sprintf(s, "%d", k);//转化为字符形式，方便查找 ans = s[n-1] - '0'; printf("%d\n", ans); } return 0; }