?

題意：給出一串那樣的數字，很有規律的，總共有2147483647位，然后問你第 n 位上的數字是多少。

?

思路：具體做法是用兩個數組保存上面的數據。

1、[] 數組表示前面所有段的位數，a[i]表示前i段一共有多少位。

?

2、保存那一段具體的位數，b[]數組存儲的是序列12345678910111213…各位位數對應數組的值，即b[1]=1, b[2]=2, b[3]=3, b[4]=4, b[5]=5, b[6]=6, b[7]=7, b[8]=8, b[9]=9, b[10]=1,b[11]=0, b[12]=1,b[13]=1, b[14]=1,b[15]=1, b[16]=1,b[17]=2, b[18]=1,b[19]=3

?

3、利用a數組計算出某段的第幾位時，直接對應輸出就可以b[i];

?

4、關鍵是求出是某一段多少位就可以啦。

?

CODE：

?

#include?<iostream>
#include?<cstdlib>
#include?<cstring>
#include?<cstdio>
#include?<cmath>
#include?<algorithm>
using?namespace?std;


long?long?a[32768],?b[200010];
char?str[10];

void?init()
{
????long?long??s?=?0,?k?=?1;
????for(int?i?=?1;?i?<?32768;?i++)
????{
????????s?=?s?+?(int)(log10(double(i)))+1;???????//求數字的位數?
????????a[i]?=?a[i-1]?+?s;
????}
????for(int?i?=?1;?i?<?32768;?i++)
????{
????????memset(str,?0,?sizeof(str));
????????sprintf(str,?"%d",?i);
????????for(int?j?=?0;?j?<?strlen(str);?j++)
????????{
????????????b[k++]?=?str[j]-'0';
????????}
????}
}

int?main()
{
????int?T;
????scanf("%d",?&T);
????init();
????while(T--)
????{
????????long?long?q;
????????scanf("%lld",?&q);
????????long?long?*p?=?lower_bound(a,?a+32768,?q);??????//二分求下界，返回的是指針。?
????????int?ans?=?q-a[p-a-1];???????????//計算是某一子串的多少位
????????printf("%lld\n",?b[ans]);
????}
????return?0;
}

?

轉載于:https://www.cnblogs.com/g0feng/archive/2012/10/15/2724605.html

總結

以上是生活随笔為你收集整理的UVA 10706 Number Sequence的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。