模拟+二分 poj-1019-Number Sequence-白红宇

模拟+二分 poj-1019-Number Sequence

阅读量：5106 次

发布时间：2019-06-13

本文共 1192 字，大约阅读时间需要 3 分钟。

题目链接：

题目大意：

Sk表示123...k

把S1S2S3...Sk排成一行比如：112123123412345123456....

求第i个数字是多少。

解题思路：

如果Sk表示123...k所占的位数，显然Sk=Sk-1+Cal(k)。Cal(k)表示k的位数。

先打表预处理sum[i]=S1+S2+..+Si;

然后在sum[i]中查找第n个属于哪一个Sk.

在同一个Sk中，一位有1~9 9个，2位有10~99 90个 3位有100~999 900个。。。所以可以先找到属于该Sk中的第几位的数。

找到位数后，就可以算出属于该位的第几个数了比如四位的第一个数1000，第二个数为1001，，，

找到该位数的第几个后，再找属于该数的第几位，比如1234的第二位是2.

代码：

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #define eps 1e-6#define INF 0x1f1f1f1f#define PI acos(-1.0)#define ll __int64#define lson l,m,(rt<<1)#define rson m+1,r,(rt<<1)|1//#pragma comment(linker, "/STACK:1024000000,1024000000")using namespace std;/*freopen("data.in","r",stdin);freopen("data.out","w",stdout);*/ll Cal(ll k) //计算k的位数{ ll res=0; while(k) { res++; k/=10; } return res;}ll cnt[33000]; //cnt[i]表示S1S2...Si的总位数ll bitcnt[20]; //在一个Si中，bitcnt[i]表示1~i位总共的个数ll shi[12]; //shi[i]表示10^(i-1);int fun(int x,int num) //计算x的第num位数字{ int res=0,temp=x; while(temp) { res++; temp/=10; } res=res-num+1; for(int i=1;i