1019numbersequence.cpp

算法编程题,北京大学OnlineJudge 1019NumberSequence

//别的解法
//题意：
//就是有这样一个序列：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;

//112123...9, 11231234...99, ... 的位数
const long long a[] = {0, 45, 9045, 1395495, 189414495, 2147483648};            

//1, 1234...10, 1234...100, ...的位数
const long long b[] = {1, 11, 192, 2893, 38894, 488895, 5888896};               


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; 
}