本文主要是介绍POJ 1019 许久之前，觉得这真是一道神题呢。。 递推+二分，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
11212312341234512345612345671234567812345678912345678910123456789101112345678910
给出一串有以上规律的数字，找出第 n 个位置上的数字是几。
我们把这串字符串分一下
dp[i] 代表从 1 开始 结尾为 i 的子串的长度
sum[i] 代表从 1 开始到 i 子串长度的总和。
这样，我们首先确定这是到哪一个子串的，lower_bound 一下 sum,
然后我们就知道了 他在子串中的哪一个位置。
dp中保留了这个信息，在 lower bound 一下 dp.
我们就得到了一个数字，以及在这个数字中的位置。。
由于实在懒，怕错（%要从后往前，我们数位置从前往后（理论上 从前往后的第 i 个 = 从后往前的 length -i+1 个）），直接写了个函数来判断是不是到了这个位置。。
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>using namespace std;
#define MAX 31952
#define INF 0x3f3f3f3f
#define MS(x) memset(x,0,sizeof(x))
#define ll long longll dp[50000];
ll sum[50000];
ll len(ll n)
{ll ans=0;while(n)ans++,n/=10;return ans;
}
int main()
{dp[1]=1;sum[1]=1;int i;for(i=2;i<MAX;i++){dp[i]=dp[i-1]+len(i);sum[i]+=sum[i-1]+dp[i];}ll num;int T;cin>>T;while(T--){cin>>num;ll index1=(lower_bound(sum,sum+MAX,num)-sum)-1;num-=sum[index1];ll index2=(lower_bound(dp,dp+MAX,num)-dp)-1;num-=dp[index2];ll tn=index2+1;while(len(tn)>num)tn/=10;cout<<tn%10<<endl;}return 0;
}
这篇关于POJ 1019 许久之前，觉得这真是一道神题呢。。 递推+二分的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
