首页 > 代码库 > 【poj1019】 Number Sequence
【poj1019】 Number Sequence
http://poj.org/problem?id=1019 (题目链接)
题意：给出一个数：1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910（当然中间是没有空格的）求它从左往右第n位上是多少。
solution
水题一道。我们可以发现，这个数可以分成若干串数，记为i，那么每串数i就是从1~i。我们可以用数组x[i]来记录串i所占的空间也就是位数，数组sum[i]来记录串i的末尾位于整个串中的哪个位置。
对于每次输入的数n，我们先二分找到它位于哪个串中，之后再递归到当前串中处理。在这里我们发现x[i]=x[i-1]+log10(i)+1，所以就很好做了。
代码：
// poj1019#include<algorithm>#include<iostream>#include<cstring>#include<cstdlib>#include<cstdio>#include<cmath>#include<vector>#define MOD 1000000007#define inf 2147483640#define LL long long#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);using namespace std;inline LL getint() { LL x=0,f=1;char ch=getchar(); while (ch>‘9‘ || ch<‘0‘) {if (ch==‘-‘) f=-1;ch=getchar();} while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘;ch=getchar();} return x*f;}LL x[1000000],sum[1000000];vector<int> v;int main() { int T;scanf("%d",&T); sum[0]=x[0]=0; for (int i=1;i<=9;i++) x[i]=x[i-1]+1; for (int i=10;i<=99;i++) x[i]=x[i-1]+2; for (int i=100;i<=999;i++) x[i]=x[i-1]+3; for (int i=1000;i<=9999;i++) x[i]=x[i-1]+4; for (int i=10000;i<=99999;i++) x[i]=x[i-1]+5; for (int i=1;i<=99999;i++) sum[i]=sum[i-1]+x[i]; while (T--) { LL n;scanf("%lld",&n); int i=lower_bound(sum,sum+100000,n)-sum; n-=sum[i-1]; i=lower_bound(x,x+i+1,n)-x; n-=x[i-1]; v.clear(); while (i) { v.push_back(i%10); i/=10; } reverse(v.begin(),v.end()); printf("%d\n",v[n-1]); } return 0;}
【poj1019】 Number Sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。