题解 SP395 【APRIME - Anti-prime Sequences】

· · 题解

筛素数+dfs深搜

先把所有素数筛出来标记后再直接暴力dfs搜索序列的排序顺序。

#include <bitset>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define rr register int
#define ll long long
using namespace std;
inline int read()//读优不解释
{
    char ch=getchar();
    int f=1,x=0;
    while(ch>'9'||ch<'0')
    {
        if(ch=='-')f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
int n,m,d,a[1001],pri[10001];//a数组记录当前放的数
bool flag,v[1001];
bitset<10001> vis;//bitset压空间
inline bool is_prime(int dep,int pos)//判断长度小于等于d的一段序列的和是否是合数
{
    int sum=pos;
    for(rr i=1;i<d&&dep-i>0;++i)
    {
        sum+=a[dep-i];
        if(vis[sum])return 0;//由题得,可以任意取长度小于等于d的一段序列求和,其和都要是合数,所以一旦有一个和不是合数就返回0
    }
    return 1;//所有都是合数就返回1
}
inline void dfs(int dep)//dfs搜索
{
    if(dep==m-n+2)//整个序列放满了证明找到一种
    {
        flag=0;//标记找到了
        printf("%d",a[1]);//注意输出有格式要求
        for(rr i=2;i<m-n+2;++i)
            printf(",%d",a[i]);
        putchar('\n');
        return;
    }
    for(rr i=n;i<=m&&flag;++i)//因为是字典序最小,所以贪心,每次都尽量从最小的放起
        if(!v[i]&&is_prime(dep,i))//判断当前正在放的数被放入后序列是否还合法
        {
            v[i]=1;//合法就放入再找下一个
            a[dep]=i;//放入
            dfs(dep+1);
            v[i]=0;
        }
}
int main()
{
    vis.set();
    int tot=0;
    for(rr i=2;i<10001;++i)//欧式筛筛素数
    {
        if(vis[i])pri[++tot]=i;
        for(rr j=1;j<=tot&&i*pri[j]<10001;++j)
        {
            vis[i*pri[j]]=0;//标记合数
            if(!(i%pri[j]))break;
        }
    }
    while(1)//多组数据
    {
        n=read();
        m=read();
        d=read();
        if(!(n+m+d))break;
        flag=1;//标记清零
        for(rr i=n;i<=m&&flag;++i)//暴力dfs搜索
        {
            v[i]=1;
            a[1]=i;//枚举每一个数作为开头时的情况去dfs
            dfs(2);
            v[i]=0;
        }
        if(flag)puts("No anti-prime sequence exists.");//如果找不到合法序列,就如题输出
    }
    return 0;
}

我是蒟蒻