題意：
就是有這樣一個序列：1 12 123 1234 12345 .....，輸入序列的下標(biāo)，讓你算出該序列所在下標(biāo)的字符
思路：
一開始想用字符串模擬來做，結(jié)果TLE。后來看了discuss，又想了一下，發(fā)現(xiàn)可以按規(guī)律將序列分成幾段，然后再在每段中查找。具體做法是：先按序列
中數(shù)字的位數(shù)來分，112123...123456789是一段，1..10 1..11 1..12 ... 1..99是一段，1..100
...
1..999是一段，以此類推。確定了是在上面的哪一段以后，再按類似的思想確定這個下標(biāo)是在哪個12345...n的序列，最后判斷是在其中哪個數(shù)字的
哪一位。
代碼：
#include <iostream>
#include <cmath>
using namespace std;
const long long a[] = {0, 45, 9045, 1395495, 189414495, 2147483648}; //112123...9, 11231234...99, ... 的位數(shù)
const long long b[] = {1, 11, 192, 2893, 38894, 488895, 5888896}; //1, 1234...10, 1234...100, ...的位數(shù)
int digit (int n)
{
int ans = 1;
while ( n / 10 != 0 )
{
n /= 10;
ans ++;
}
return ans;
}
char Pos (int n, long long index) //在1234...n中找到下標(biāo)為index的字符
{
long long i, j;
long long pos = 0;
for (i=1; i<=n; i++)
{
pos += digit(i);
if ( pos >= index )
break;
}
pos -= digit(i); //定位在i上
j = digit(i) - (index - pos);
//if ( j == digit(i) - 1 )
// cout<<endl;
while ( j > 0 )
{
i /= 10;
j --;
}
return (i % 10) + '0';
}
char Find (long long pos)
{
long long p, t;
int index = 0;
int temp;
while ( a[index] < pos )
{
index ++;
}
p = a[index - 1];
p += b[index - 1];
temp = int(pow(10.0, index-1));
t = b[index - 1] + index;
while ( p < pos )
{
p += t;
t += index;
temp ++;
}
p -= t - index;
return Pos(temp, pos-p);
}
int main ()
{
int test;
long long i;
cin>>test
while ( test-- )
{
cin>>i;
cout<<Find(i)<<endl;
}
return 0;