 |
| ||||
Home Page
F.A.Qs
Statistical Charts
Past Contests
Scheduled Contests
Award Contest
| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
分段,再一个一个区间把N对应的数字套住/*Problem: Poj 1019 思路：
归纳分析出m位数所有排出来的长度，有下面的a数组---0索引不用。b数组存储的是该m位数
最后一个（例如9<->9,99<->189,999<->2889)排出来的长度。下面就将序号N对应的数字找出来
*/
#include<iostream>
using namespace std;
int main()
{
int a[5]={0,45,9045,1395495,189414495};
int b[5]={0,9,189,2889,38889};
int c[5]={0,10,100,1000,10000};
int d[5]={1,10,100,1000,10000};
unsigned long i,j,k,n,t;
cin>>t;while(t--)
{
cin>>n;
for(i=1;i<5;i++)
if(n<=a[i])break; //所在的行数为 i位数
n-=a[i-1];
for(k=0,j=1;k<n;j++)
k=b[i-1]*j+i*j*(j+1)/2; //得到该i-1位的数中排列第一个超过序号n的第j个数(例如：2位数，第j个数是11+j
--j; //n号就是落在前面的数10+j
n=n-b[i-1]*(j-1)-i*j*(j-1)/2; //在该数中寻找最终的位置
for(i=1;i<5;i++)
if(n<=b[i])break;
if(i==1)cout<<n<<endl;
else //求得在该数的一排中 最后更新了的序号n对应的数字
{
n-=b[i-1];
k=(n-1)/i+c[i-1];
cout<<k/d[i-(n-1)%i-1]%10<<endl;
}
}
return 0;
}
Followed by:
Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator
