题意:
就是有这样一个序列:1 12 123 1234 12345 .....,输入序列的下标,让你算出该序列所在下标的字符
思路:
一开始想用字符串模拟来做,结果TLE。后来看了discuss,又想了一下,发现可以按规律将序列分成几段,然后再在每段中查找。具体做法是:先按序列
中数字的位数来分,112123...123456789是一段,1..10 1..11 1..12 ... 1..99是一段,1..100
...
1..999是一段,以此类推。确定了是在上面的哪一段以后,再按类似的思想确定这个下标是在哪个12345...n的序列,最后判断是在其中哪个数字的
哪一位。
代码:
#include <iostream>
#include <cmath>
using namespace std;
const long long a[] = {0, 45, 9045, 1395495, 189414495, 2147483648}; //112123...9, 11231234...99, ... 的位数
const long long b[] = {1, 11, 192, 2893, 38894, 488895, 5888896}; //1, 1234...10, 1234...100, ...的位数
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中找到下标为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;