Problem Description
假設(shè)：
S1 = 1
S2 = 12
S3 = 123
S4 = 1234
.........
S9 = 123456789
S10 = 1234567891
S11 = 12345678912
............
S18 = 123456789123456789
..................
現(xiàn)在我們把所有的串連接起來
S = 1121231234.......123456789123456789112345678912.........
那么你能告訴我在S串中的第N個(gè)數(shù)字是多少嗎？
?
Input
輸入首先是一個(gè)數(shù)字K，代表有K次詢問。
接下來的K行每行有一個(gè)整數(shù)N(1 <= N < 2^31)。 ?
Output
對于每個(gè)N，輸出S中第N個(gè)對應(yīng)的數(shù)字.
?
Sample Input 6 1 2 3 4 5 10 ?
Sample Output 1 1 2 1 2 4 #include <stdio.h>__int64 n,num[70000]; __int32 w;void Bi_serch(int low, int high){int mid;while(low<= high){//mid=(low+high)/2;mid=low+((high-low)>>1);if(num[mid]<n && num[mid+1]>=n){ w=mid; return ;}else if(num[mid+1]<n)low=mid+1;else if(num[mid]>=n)high=mid-1;} }int main(){int t;for(int i=1;i<=65540;++i)num[i]=num[i-1]+i;//printf("%lld\n",num[65540]);scanf("%d",&t);while(t--){w=-1;scanf("%d",&n);Bi_serch(1,65540);int a=n-num[w];a=a%9;if(a==0) a=9;printf("%d\n",a);} return 0; } 這道題由于數(shù)據(jù)比較大，所以應(yīng)該是先算出二的31次方是在連接后的第幾個(gè)S中出現(xiàn)，然后根據(jù)結(jié)果定義數(shù)組變量大小，由于要查找的數(shù)一定存在而且數(shù)據(jù)有序，可以考慮用二分查找，然后就So easy 了。

總結(jié)

以上是生活随笔為你收集整理的杭电1597_find the nth digit的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。