} } }

    POJ 1019 解题呈报

    添加时间:2013-7-17 点击量:

    题目地址:http://poj.org/problem?id=1019



    一道通俗的ACM题,然则从中可以看出一些题目。题很简单,就是给你一串数字串,其规律为:


    1 12 123 1234 12345 123456 1234567 12345678 123456789 12345678910 1234567891011 123456789101112······


    输入地位i,策画这一串数字第i位是什么数字,重视是数字,不是数。例如12345678910的第10位是1,而不是10,第11位是0,也不是10。



    然后就很好说了,策画一个数字k的长度用:int(log10(double(num))) + 1,然后变量sk每次加上k的长度,再定一个和变量sum,它每次加上sk的值,直到sum比index大。然后再按照残剩的长度在sk内部找那个数字,很简单。



    这里有个题目就是,题中说“The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647)”,遵守OJ的常规,测试用例必然会有极端景象,极大的或极小的,所以i = 2147483647是必然要推敲的。这里若是处理惩罚不好或许会呈现超时的景象。很不幸我就超时了。



    有一点很是诡异,在代码第48行,注释说:若是sum < index 则超时。因为我开端时while里用的就是sum < index,每次剖断当前数到的长度是否比题中给的长度index小。然则很遗憾如许对于极大的景象:i = 2147483647会很慢,插装了策画时候的代码后发明这一步须要策画60秒阁下。



    而后我在网上搜刮到了别人的代码,根蒂根基都是应用累加的办法,比如:http://blog.csdn.net/lyy289065406/article/details/6648504中是如许累加的:


    const int size=31269;


    void play_table(void) 


        a[1]=s[1]=1; 

        for(int i=2;i<size;i++) 

        { 

            a[i]=a[i-1]+(int)log10((double)i)+1;  //log10(i)+1 默示第i组数字列的长度 比 第i-1组 长的位数 

            s[i]=s[i-1]+a[i];      //前i组的长度s[i] 便是 前i-1组的长度s[i-1] + 第i组的长度a[i] 

        }                          //log()是重载函数,必须对int的i强迫类型转换,以断定参数类型 

        return; 

    }

    固然采取的是数组打表的办法在多量测试用例的景象下会快很多,然则累加过程是一样的,耗时差别如此之大,我想,可能就是出在断定语句上了。


    他的断定语句是“i<31269”,而我的是“sum < 2147483647”,题目或许就出在这里,我的小于号两端用来斗劲的数字都太大。事实证实是如许的,我采取了与他类似的断定前提来累加后,耗时变成了0s,然后我将while的剖断前提从sum < index改为了index - sum > 0,耗时也是0s。



    为什么只是一个小小的批改,耗时却变更这么大呢?或许我们要到底层去推敲,int型的变量占4个字节,也就是32bit,两个斗劲大32bit的数字彼此斗劲天然比两个斗劲小的彼此斗劲要耗时很多。或许再连络汇编里的常识会懂得地更透辟一些,然则很遗憾我已经忘了。。。


    下面是完全的代码,在POJ上经由过程,268K    16MS。(若是打表的话,占用内存会增长,然则时候会削减,以空间换时候罢了,既然如许能过就不打表了)



     1 #include <iostream>
    
    2 #include <cmath>
    3 #include <fstream>
    4 #include <time.h>
    5 using namespace std;
    6
    7 int size(int num)
    8 {
    9 return int(log10(double(num))) + 1;//数字num的长度
    10 }
    11
    12 int digit(int num, int length)
    13 {
    14 length = size(num) - length;
    15 while(length--
    16 {
    17 num /= 10;
    18 }
    19 num %= 10;
    20 return num; //返回数字num的第length个数字
    21 }
    22
    23 int main()
    24 {
    25 //ifstream in(in.txt);//重定向cin和cout,使法度从文本读入数据,避免一遍遍输入
    26 //cin.rdbuf(in.rdbuf());
    27
    28 //ofstream out(out.txt);
    29 //cout.rdbuf(out.rdbuf());
    30
    31 //time_t start,stop; //用于查看耗时
    32
    33 int t,k;
    34 long index, sk, sum;
    35 cin >>t;
    36 while(t--
    37 {
    38 cin >>index;
    39
    40 //cout <<endl <<endl <<index = <<index <<endl;
    41
    42 sum = 1;
    43 k = 1;
    44 sk = 1;
    45
    46 //time(&start); //返回当前时候到start
    47
    48 while(index - sum > 0//若是sum < index 则超时
    49 {
    50 k++;
    51 sk += size(k);
    52 sum += sk;
    53 }
    54
    55 //time(&stop); //返回当前时候到stop
    56 //cout <<time_cost= <<stop - start <<endl;
    57
    58 sum = index - sum + sk;
    59
    60 //cout << sk残剩长度 << sum <<endl;
    61
    62 int num = 1;
    63 int length = 1;
    64 while(length < sum)
    65 {
    66 num++;
    67 length += size(num);
    68 }
    69
    70 length = sum - length + size(num);
    71
    72 //cout << num残剩长度 <<length <<endl;
    73 //cout << 数字num是 <<num <<endl;
    74
    75 cout <<digit(num, length) <<endl;
    76 }
    77 return 0;
    78 }



     
    分享到: