P7200 [COCI2019-2020#1] Lutrija题解

· · 题解

我们可以先分类讨论一下。

两个素数x和y，其必有两种情况——两个奇数和一奇一偶。

首先来说两个奇数的情况，题目让我们找一些素数使相邻两数之差为素数，而两个奇数之差只能为偶数，即两数之差为2时，x与y可通。

再说一奇一偶的情况，因为2是唯一的偶素数，所以x与y中一定有一个为2，假定x为2，那么y与2的差为素数时，x与y可通。

我们可以用深搜来枚举以上的所有情况，但既然是要判断素数，自然少不了素数筛子，注意数据范围已经超过了int的最大范围，因此要开long long。

素数筛子：

bool is_prime(long long x){
    if(x==1) return false; //1既不是素数，也不是合数 
    if(x==2) return true; //2是素数 
    if(x%2==0) return false; //但2的倍数不是素数 
    for(long long i=3;i*i<=x;i+=2) //标准素数筛子，但注意数据范围 
        if(x%i==0)
            return false;
    return true; //剩下的必为素数 
}

接下来是最核心的DFS代码，若前面的分析没看懂的可看此处：

void dfs(long long x,long long y,int t){
    if(flag) return; //搜到可行方案就直接返回 
    if(is_prime(abs(x-y))){ //搜到了可行方案 
        cout<<t+1<<endl; 
        //因为在上一层递归中总方案数为t+2，所以在本层中为t+1 
        cout<<a<<" ";
        for(int i=1;i<t;i++) cout<<ans[i]<<" ";
        cout<<b<<endl;
        flag=true; //标志已搜到可行方案 
        return;
    }
    if(x!=2) //两个奇数的情况 
        for(int i=1;i<=3;i++){
            if(i==1&&is_prime(x-2)){ 
                ans[t]=2; //记录方案 
                dfs(2,y,t+1);
            } 
            //将其中一个奇数变为偶数，即变为2 
            if(i==2&&is_prime(x-2)){ 
                ans[t]=x-2;
                dfs(x-2,y,t+1);
            }
            //将其中一个奇数减2，使两个奇数差为2 
            if(i==3&&is_prime(x+2)){
                ans[t]=x+2;
                dfs(x+2,y,t+1);
            }
            //将其中一个奇数加2，使两个奇数差为2
        }
    else{ //一奇一偶的情况 
        if(is_prime(y+2)){
            ans[t]=y+2;
            dfs(y+2,y,t+1);
        }
        //将2变为与另一个奇数相差2的奇数 
    }
    return; //搜索结束 
}

最后再上一遍完整的AC代码：

#include<bits/stdc++.h> //万能头文件 
using namespace std;
long long ans[50]; //记录方案的数组 
long long a,b,n=2;
bool flag;
bool is_prime(long long x){ //素数筛子 
    if(x==1) return false;
    if(x==2) return true;
    if(x%2==0) return false;
    for(long long i=3;i*i<=x;i+=2)
        if(x%i==0)
            return false;
    return true;
}
void dfs(long long x,long long y,int t){ //深搜
    if(flag) return; 
    if(is_prime(abs(x-y))){
        cout<<t+1<<endl; 
        cout<<a<<" ";
        for(int i=1;i<t;i++) cout<<ans[i]<<" ";
        cout<<b<<endl;
        flag=true;
        return;
    }
    if(x!=2)
        for(int i=1;i<=3;i++){
            if(i==1&&is_prime(x-2)){ 
                ans[t]=2;
                dfs(2,y,t+1);
            } 
            if(i==2&&is_prime(x-2)){ 
                ans[t]=x-2;
                dfs(x-2,y,t+1);
            }
            if(i==3&&is_prime(x+2)){
                ans[t]=x+2;
                dfs(x+2,y,t+1);
            }
        }
    else{
        if(is_prime(y+2)){
            ans[t]=y+2;
            dfs(y+2,y,t+1);
        }
    }
    return;
}
void inp(){
    cin>>a>>b; //输入
    return;
}
void work(){
    if(is_prime(abs(a-b))){ //特判，若a和b可达，直接输出 
        cout<<n<<endl<<a<<" "<<b;
        return;
    }
    dfs(a,b,1); //因为输出方案时i从1开始，所以t从1开始 
    if(!flag) cout<<"-1"; //若没搜到，输出-1 
    return;
}
int main(){
    ios::sync_with_stdio(false); //输入输出流加速代码 
    inp();
    work(); 
    return 0; //代码结束 
}

以上是本蒟蒻的第一份题解，若有错误，请大佬指正，谢谢。

感谢bowlder_lover的提醒，有一段代码是多余的，现已修正。