順時針打印數組，poj1019（打表預處理+數學）

2023-10-25 阅读 32 评论 0

摘要：題目鏈接：http://poj.org/problem?id=1019 題意：對于序列1121231234...，求第i個數字（i<=2147483647)。思路：記第一組為1，第二組為12，第三組為123，打表預處理計算除第2147482647位在第31268組，然后

題目鏈接：http://poj.org/problem?id=1019

題意：對于序列1121231234...，求第i個數字（i<=2147483647)。

思路：記第一組為1，第二組為12，第三組為123，打表預處理計算除第2147482647位在第31268組，然后預處理計算前31268組的位數，存儲在sum數組中，其中(int)log10((double)i)+1表示數據 i 的位數。然后模擬就行了，計算出當前要計算的第x位處在第k1組中，然后找到所求位數位于整數 i 中，把 i 后面的數字除掉，取模之后即所求結果，看著很繞，自己模擬一遍就明白了。

AC代碼：

 1 #include<cstdio>
 2 #include<cmath>
 3 using namespace std;
 4 
 5 unsigned int sum[31270];
 6 int T,n;
 7 
 8 void play_table(){
 9     unsigned int pre=1,nw;
10     sum[1]=1;
11     for(int i=2;i<=31268;++i){
12         nw=pre+(int)log10((double)i)+1;
13         sum[i]=sum[i-1]+nw;
14         pre=nw;
15     }
16 }
17 
18 int getd(int x){
19     int k1;
20     for(int i=1;i<=31268;++i)
21         if(x<=sum[i]){
22             k1=i;
23             break;
24         }
25     int p=x-sum[k1-1],len=0,i;
26     for(i=1;i<=k1;++i){
27         len+=(int)log10((double)i)+1;
28         if(p<=len)
29             break;
30     }
31     int ilen=(int)log10((double)i)+1;
32     len-=ilen;
33     int k2=p-len;
34     for(int j=k2+1;j<=ilen;++j)
35         i/=10;
36     return i%10;
37 }
38 
39 int main(){
40     play_table();
41     scanf("%d",&T);
42     while(T--){
43         scanf("%d",&n);
44         printf("%d\n",getd(n));
45     }
46     return 0;
47 }