• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            QuXiao

            每天進(jìn)步一點(diǎn)點(diǎn)!

              C++博客 :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理 ::
              50 隨筆 :: 0 文章 :: 27 評論 :: 0 Trackbacks
            題意:
                就是有這樣一個序列: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;
            posted on 2008-01-19 16:46 quxiao 閱讀(1706) 評論(0)  編輯 收藏 引用 所屬分類: ACM
            一本大道久久a久久精品综合| 国产精品国色综合久久| 久久天堂电影网| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 国产成人综合久久久久久| 国产午夜精品理论片久久| 亚洲色大成网站www久久九| 婷婷久久综合九色综合98| 天堂无码久久综合东京热| 99久久99这里只有免费的精品| 久久国产视频网| 国产精品一区二区久久国产| 色综合久久天天综线观看| 国内精品久久久久久99| 一级做a爰片久久毛片看看 | 精品国产91久久久久久久| 久久精品视频一| 国产精久久一区二区三区| 久久精品国产亚洲av高清漫画| 99久久亚洲综合精品成人| 久久99精品久久只有精品 | 狠狠色丁香婷婷综合久久来| 久久青青草视频| 久久午夜福利电影| 久久精品二区| 久久国产精品免费一区二区三区| 精品久久久久久久无码| 色婷婷综合久久久久中文| 久久伊人五月丁香狠狠色| 欧美精品丝袜久久久中文字幕| 亚洲午夜精品久久久久久人妖| 奇米影视7777久久精品| 无码伊人66久久大杳蕉网站谷歌| 狠狠色丁香久久婷婷综合_中| 久久综合五月丁香久久激情| 国产三级精品久久| 久久夜色撩人精品国产| 久久一区二区三区99| 久久只有这里有精品4| 久久人人爽人人爽人人爽| 伊人色综合久久天天网|