POJ-1019 Number Sequence(思维题)
题意：
有一个序列：11212312341234512345612345671234567812345678912345678910...
给定一个数n，求序列的第n个数的值。
思路：
以每一个递增序列为一段进行预处理，num[i]存储该段内数字的个数，然后求一个前缀和，输入n后找到第一个>=n的前缀和位置k，然后暴力从1搜到k寻找答案。
代码：
#include <algorithm>
#include <cstdio>
#define LL long long
using namespace std;
const int maxn = 50005;
const LL UP = 2.2e9;
LL num[maxn], sum[maxn];
int cnt, wei[15];
inline void init()
{
LL up = 0, pre = 0, x = 0, cut = 0; cnt = 0;
int flag = 0;
for(int k = 1; k <= 9; ++k)
{
cut = x;
x = x*10+9;
LL xx = x-cut;
for(int i = 1; i <= xx; ++i)
{
up += pre+i*k;
num[++cnt] = pre+i*k;
if(up >= UP){flag = 1; break;}
}
if(flag) break;
pre += (x-x/10)*k;
}
sum[0] = 0; sum[1] = num[1];
for(int i = 1; i <= cnt; ++i) sum[i] = sum[i-1]+num[i];
}
int main()
{
init();
int t, n, k, flag;
scanf("%d", &t);
while(t--)
{
scanf("%d", &n);
for(k = 1; k <= cnt; ++k)
if(n <= sum[k]) break;
n -= sum[k-1]; flag = 0;
for(int i = 1; i <= k; ++i)
{
int t = i, j = 0;
while(t)
{
wei[++j] = t%10;
t /= 10;
}
for(int l = j; l >= 1; --l)
{
--n;
if(n == 0)
{
flag = 1;
printf("%d\n", wei[l]);
break;
}
}
if(flag) break;
}
}
return 0;
}继续加油~