P7200求助大佬
查看原帖
P7200求助大佬
321687
bowlder_lover楼主2021/2/1 00:19

这道题COCI的竞赛题。我的代码在本地运行时,可通过官网提供的全部31组数据,但是我在洛谷提交时却老是不通过 求大佬帮我看一下是哪出了问题

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long i;
long long left_border,right_border;//left和right分别表示序列的左右边界(即刚开始输入的两数)
int sign;//sign用于标记是否找到解
long long sequence[50];//数组sequence用于记录可能要输出的序列

int if_prime_number(long long x)//判定x是否为质数
{
    long long i;
    if(x<=1)//0和1都不是质数
    {
        return 0;//返回假值
    }
    if(x==2)
    {
        return 1;
    }
    if(x%2==0)
    {
        return 0;
    }
    for(i=3;i*i<=x;i+=2)
    {
        if(x%i==0)
        {
            return 0;
        }
    }
    return 1;//返回真值
}

int DFS(long long insert_num,long long right_num,long long t)//insert_num表示当前要插入序列的数,right_num就是right_border
{//t表示当前要插入第几个数
    int a,b;
    if(sign)//sign=1表示已经找到可行解,此时不需继续搜索,直接返回
    {
        return 1;
    }
    sequence[t]=insert_num;//printf("sequence[%I64d]=%I64d\n",t,sequence[t]);
    if(if_prime_number(abs(insert_num-right_num)))//要插入的质数与左边数的差已经是质数,若其与右界的差也是质数,则说明已找到可行序列
    {
        sign=1;//将标记赋为真值
        printf("%I64d\n",t+1);//输出序列元素数目
        for(i=1;i<=t;i++)
        {
            printf("%I64d ",sequence[i]);
        }
        printf("%I64d",right_num);
        return 1;
    }
    if(insert_num!=2)//若本次要插入的数不是2,则inser_num是奇质数.
    {
        a=if_prime_number((insert_num+2));
        if(a)//当这两个奇质数之间的差值要为质数时,这个差值只能为2
        {
            DFS(insert_num+2,right_border,t+1);
        }
        a=if_prime_number((insert_num-2));
        if(a)//当这两个奇质数之间的差值要为质数时,这个差值只能为2
        {//若inser_num与2的差值为质数
            DFS(2,right_border,t+1);//则尝试下一次插入2
            DFS(insert_num-2,right_border,t+1);//则尝试下一次插入insert_num-2
        }
    }
    else//若本次要插入的数是2
    {
        a=if_prime_number((right_num+2));
        if(a)
        {
            DFS(right_num+2,right_border,t+1);
        }
        a=if_prime_number((right_num-2));
        b=if_prime_number((right_num-4));
        if(a&&b)
        {
            DFS(right_num-2,right_border,t+1);
        }
    }
    return 0;
}

int main()
{
    //输入数据
    scanf("%I64d%I64d",&left_border,&right_border);
    //搜索
    DFS(left_border,right_border,1);
    //输出结果
    if(!sign)//
    {
        printf("-1");
        return 0;
    }
    return 0;
}

2021/2/1 00:19
加载中...