QuXiao

每天进步一点点!

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  50 随笔 :: 0 文章 :: 27 评论 :: 0 Trackbacks
题意:
    就是有这样一个序列: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;
posted on 2008-01-19 16:46 quxiao 阅读(1690) 评论(0)  编辑 收藏 引用 所属分类: ACM

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理