首页 > 代码库 > Help him http://acm.hdu.edu.cn/showproblem.php?pid=5059

Help him http://acm.hdu.edu.cn/showproblem.php?pid=5059

  题目是昨天晚上的BC。昨天晚上一直卡在第二题,囧。

  今天看到题解之后,觉得自己想的也是差不多的,该考虑的也考虑到的。究竟是为什么会错。然后我就改了交,改了交。终于让我改对了一次,我找到了自己的代码中哪段有问题。

  接下来上代码:

  wa code:

  

int but=0;if(!sig)    but=1;else    but=0;long long c=0,r=1;for(int i=strlen(str)-1; i>=but; i--){    //not digit    if(str[i]<‘0‘||str[i]>‘9‘)        return 0;    c+=(str[i]-‘0‘)*r;    r*=10;    if(c>1000000000 || r>1000000000)        return 0;}

  

  ac code:

int i=0;if(!sig)    i=1;else    i=0;long long c=0;for(; i<strlen(str); i++){    //not digit    if(str[i]<‘0‘||str[i]>‘9‘)        return 0;    c=c*10+(str[i]-‘0‘);    if(c>1000000000)        return 0;}

  比较两段代码,我认为有可能是这些原因:

  1.第一段代码可能数据的一出,所以我写了组数据:

  

  由数据可以看出在,对于代码中的数据完全可以达到1000000000之后的程度,也就是说完全没有数据问题。那会不会是进制元素r的问题,我在提交的代码将上面的if语句改为:

  

if(c>1000000000 || r>1000000000)    return 0;

  结果仍然是WA

  

  2.有什么特殊的数据使得计算过程中会有变化?会不会是在后面的数据中有什么特殊的数据?然后我把代码修改为:

if(!sig)        but=1;    else        but=0;    int len=strlen(str);    if(!sig)        len--;    if(len>12)        return 0;    __int64 c=0,r=1;    for(int i=strlen(str)-1;i>=but;i--)    {        //not digit        if(str[i]<‘0‘||str[i]>‘9‘)            return 0;        c+=(str[i]-‘0‘)*r;        r*=10;        if(c>1000000000)        {            //cout<<"Now c‘s value is "<<c<<endl;            return 0;        }    }

  我在计算数值前先判定字符串的长度,如果长度大于12,则根本无需计算直接确定数字一定会超过a,b的大小。→_→这段代码变成ac的代码了。

  那么问题更加缩小范围了,既然控制长度能够使得代码通过。不控制长度的时候,也就是说当长度>=13的时候会出现什么状况吗?

  我在做组测试数据来试试:

  

  我的结果显示在 __int64的情况下,即使我的数值取到了14位也没有产生产生错误。但是我发现问题了。

  在if语句中应该数据大于10^9的时候就该输出的,结果输出的结果是10^14,说明当输入的数据是以10^n的数据时,我的程序会有错误,接下来测试10^20:

  

  由此可以得出,当数据为10^n的时候,对于我的wa code来说就是灾难性的。

  灾难性的结果:

    

  这组数据竟然能过...... 这说明数据完全是有问题了。

 

  但是同时,我又提交过另外一份wa code:

  

    __int64 c=0,r=1;    for(int i=strlen(str)-1;i>=but;i--)    {        //not digit        if(str[i]<‘0‘||str[i]>‘9‘)            return 0;        c+=(str[i]-‘0‘)*r;        r*=10;        if(c>1000000000 || r>1000000000)        {            //cout<<"Now c‘s value is "<<c<<endl;            return 0;        }    }

  在这个代码中,我在if语句的判定中加入了关于进制元素r的判定(依旧是wa的代码),继续看刚才的10^20的显示:

  

  由程序的输出可以看出来,现在可以很好的处理关于10^n的数据了。由进制元素来控制数据的大小,间接的其实正好控制了数据的位数,当位数10位时则会将退出,再来测试下前面的错误数据:

  

  测试的结果可以看出来,正常的数据10^9没有问题,而刚才错误也得到了修正。

  现在问题又来了:到底又有什么数据会出现错误呢?

  既然r能够限制进制进而限制字符串的位数,那是不是可以r的条件设置的不够呢?

Help him http://acm.hdu.edu.cn/showproblem.php?pid=5059