| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 3203 人关注过本帖
标题:这个题自己运行成功,OJ上显示运行错误,为什么?(运行期间执行了什么非法操 ...
只看楼主 加入收藏
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:5 
题目说明是1000000位不是1-1000000
就是最多要处理1000000个数字~

非法操作应该就是说数组越界了

这题可以分3种情况来考虑,如果某数位上的数字是0那么就不用管这个数
如果某数位上的数字是1,那就是sum+=(2^k);--(其中k是表示这个数位所在的位数)
如果某数位上的数字大于1,那后面每个位无论是什么(包括这位)都要归纳为第二种情况处理~

因为数据很大,所以可以每次进行*2或者<<1后和原来的数相加要%1000000007,否则会数据溢出

这题余数很大,对于第三种情况用快速幂对unsigned进行运算很容易溢出(明显题目没有顾及到用快速幂来进行优化这个问题),要另外处理,所以第一种直接算就可以了,对于第二种就是判断处理数位上是否是0就可以了~

好像还是要用到数组来保留信息,因为读取数据的时候是从最低位开始读取的~

但也可以不用数组,但这样就要先知道((2^n)-1)%1000000007的值,然后每遍历一次就进行逆运算,能不能被2整除,如果不能就加1000000007再除以2,如果能就直接除以2就可以了~



另说:
pow到底是个什么函数呢,我竟然不知道那个是怎么用的,这题的pow是用来干嘛的
嗯,看来是我对楼主程序的理解能力有很大问题~

[此贴子已经被作者于2018-5-9 17:29编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-09 16:05
Pine_
Rank: 1
等 级:新手上路
威 望:1
帖 子:4
专家分:6
注 册:2018-5-9
收藏
得分:5 
你for循环中间的那个条件是不是错误的,然后算出来了i-1位的由0,1组成数的个数,但是i位的好像没有计.
2018-05-09 16:07
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 11楼 九转星河
谢谢大佬,pow就是用来求幂的,后面溢出那里我水平不够没看懂,你是说取模那里不能直接用%1000000007来算么?

[此贴子已经被作者于2018-5-9 16:38编辑过]

2018-05-09 16:29
青蝶
Rank: 2
等 级:论坛游民
帖 子:160
专家分:51
注 册:2018-2-4
收藏
得分:0 
回复 12楼 Pine_
我在5楼解释了一下,我觉得方法应该是对的,因为数据输出是对的,只是不知道为什么过不了OJ。
2018-05-09 16:40
nosnoy
Rank: 9Rank: 9Rank: 9
来 自:mcu
等 级:贵宾
威 望:14
帖 子:541
专家分:1178
注 册:2016-9-17
收藏
得分:0 
回复 14楼 青蝶
for(i=i-1;i+1;i--)
尝试改成 for(i=i-1;i>=0;i--)试试?

穷举是最暴力的美学
2018-05-09 17:01
童生
Rank: 6Rank: 6
等 级:侠之大者
威 望:8
帖 子:205
专家分:455
注 册:2018-3-7
收藏
得分:5 
唉,
题目说明是1000000位不是1-1000000
就是最多要处理1000000个数字~
人家都说得这么清楚了
2018-05-09 17:08
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
回复 13楼 青蝶
需要用到pow么,可以看看这操作~
for (i=n-1;i!=-1;--i)
{
    s+=sum;
   
    sum*=2;//sum<<1
    if (sum>=k)
        sum-=k;

    if (s>=k)
        s-=k;
}


PS:

还有另一种写法

for (i=sum=0;i!=n;++i)
{
     sum*=2;//sum<<1
     if (sum>=k)
         sum-=k;
}

for (i=0;i!=n;++i)
{
    s+=sum;
    sum=sum%2?sum/2:(sum+k)/2;

    if (s>=k)
        s-=k;
}


pow其实本质也是一个函数,对于处理一个超过double范围的数还是会产生溢出的,因此要另外处理~

[此贴子已经被作者于2018-5-9 17:41编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-09 17:22
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
这条题目输入和题意似乎有冲突的地方~
输入10
输出2
很明显输入的就是n
但题意说是位数就不知道是怎么回事了~

这里有个关于求位数的代码可以看看,或者还会有bug,但基本没啥问题了~

程序代码:
#include<stdio.h>

unsigned fun( unsigned );

int main( void )
{
    unsigned n;
    
    if (scanf("%u",&n)!=1)
        return 1;
    
    printf("%u\n",fun(n));
    
    return 0;
}

unsigned fun( unsigned n )
{
    const unsigned k=1000000007;
    
    unsigned s=1;
    unsigned sum;
    
    size_t i;
    
    if (n==0)
        return 0;
    
    for (i=1;i!=n;++i)
    {
        s<<=1;
        
        s=(s>=k)?(s-k):(s);
    }
   
    for (i=sum=0;i!=n;++i)
    {
        unsigned t;
        
        if (scanf("%1u",&t)!=1)
            return 0;
            
        if (t)
            sum+=s;
            
        s=(s&1)?((s+k)>>1):(s>>1);
        sum=(sum>=k)?(sum-k):(sum);
         
        if (t>1)
        {
            ++i;
            
            break;
        }
    }
    
    for (;i!=n;++i)
    {
        unsigned t;
        
        if (scanf("%1u",&t)!=1)
            return 0;
            
        sum+=s;
            
        s=(s&1)?((s+k)>>1):(s>>1);
        sum=(sum>=k)?(sum-k):(sum);
    }
    
    return sum;
}

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-09 22:24
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
这题大意应该还是要用到数组(预先不说要输入多少个数),那可以这样~

程序代码:
#include<stdio.h>
#include<string.h>

unsigned fun( const char*,size_t );

char str[1000005];

int main( void )
{   
    fgets(str,sizeof (str),stdin);
    
    str[strcspn(str,"\n")]='\0';
    
    printf("%u\n",fun(str,strlen(str)));
    
    return 0;
}

#include<errno.h>

unsigned fun( const char* str,size_t n )
{
    const unsigned k=1000000007;
    
    unsigned s=1;
    unsigned sum;
    
    size_t i;
    
    if (n==0)
        return 0;
    
    for (i=1;i!=n;++i)
    {
        s<<=1;
        
        s=(s>=k)?(s-k):(s);
    }
   
    for (sum=0;*str!='\0';++str)
    {
        unsigned t;
        if (sscanf(str,"%1u",&t)!=1)
        {
            errno=ERANGE;
            
            return 0;
        }
        
        if (t)
            sum+=s;
            
        s=(s&1)?((s+k)>>1):(s>>1);
        sum=(sum>=k)?(sum-k):(sum);
         
        if (t>1)
        {
            ++str;
            
            break;
        }
    }
    
    for (;*str!='\0';++str)
    {
        unsigned t;
        if (sscanf(str,"%1u",&t)!=1)
        {
            errno=ERANGE;
            
            return 0;
        }
            
        sum+=s;
            
        s=(s&1)?((s+k)>>1):(s>>1);
        sum=(sum>=k)?(sum-k):(sum);
    }
    
    return sum;
}


[此贴子已经被作者于2018-5-9 23:01编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-09 22:59
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:0 
不用数组也预先不知道字符串长度可以这样~

程序代码:
#include<stdio.h>

unsigned fun( void );

int input( unsigned* );

int main( void )
{
    unsigned n;
    
    printf("%u\n",fun());
    
    return 0;
}

int input( unsigned* t )
{
    char s[2]={0,0};
    
    *s=getchar();
    
    return  (*s!='\n')?(sscanf(s,"%1u",t)):(EOF);
}

#include<errno.h>

unsigned fun( void )
{
    const unsigned k=1000000007;
    
    unsigned sum=0;
   
    while (1)
    {
        unsigned t;
        
        const int flag=input(&t);
        
        if (flag==EOF)
            return sum;
        else if (flag!=1)
        {
            errno=ERANGE;
            
            return 0;
        }

        sum=(sum<<1)|(!!t);

        (sum>=k)?(sum-=k):(NULL);
         
        if (t>1)            
            break;
    }
    
    while (1)
    {
        unsigned t;
        
        const int flag=input(&t);
                
        if (flag==EOF)
            break;
        else if (flag!=1)
        {
            errno=ERANGE;
            
            return 0;
        }
            
        sum=(sum<<1)|(1);
        
        (sum>=k)?(sum-=k):(NULL);
    }
    
    return sum;
}


[此贴子已经被作者于2018-5-10 10:38编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2018-05-10 10:25
快速回复:这个题自己运行成功,OJ上显示运行错误,为什么?(运行期间执行了什么 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.040447 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved