信息学奥赛一本通 1446：素数方阵通过100分_C

我的主页信息学奥赛一本通（C++版）在线评测系统

1446：素数方阵【题目描述】

在下面的方格中，每行，每列，以及两条对角线上的数字可以看作是五位的素数。

方格中的行按照从左到右的顺序组成一个素数，而列按照从上到下的顺序。

两条对角线也是按照从左到右的顺序来组成。

+---+---+---+---+---+
| 1 | 1 | 3 | 5 | 1 |
+---+---+---+---+---+
| 3 | 3 | 2 | 0 | 3 |
+---+---+---+---+---+
| 3 | 0 | 3 | 2 | 3 |
+---+---+---+---+---+
| 1 | 4 | 0 | 3 | 3 |
+---+---+---+---+---+
| 3 | 3 | 3 | 1 | 1 |
+---+---+---+---+---+

这些素数各个数位上的和必须相等。

左上角的数字是预先定好的。

一个素数可能在方阵中重复多次。

如果不只有一个解，将它们全部输出（按照这25个数字组成的25位数的大小排序）。

一个五位的素数开头不能为0（例如：00003 不是五位素数）

【输入】

一行包括两个被空格分开的整数:各个位的数字和和左上角的数字。

【输出】

对于每一个找到的方案输出5行，每行5个字符, 每行可以转化为一个5位的质数.在两组方案中间输出一个空行. 如果没有解就单独输出一行"NONE"。

【输入样例】

11 1

【输出样例】

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair
const int MOD = 1E9+7;
const int N = 1000000+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
 
int n,m;
int bit[6];
bool bprime[100000];
int G[500000][15];
bool vis[500000][10];
int judge[20000][10],tot;
int res[100];
 
int suf[6];
int sumX[6], sumY[6];
int sum[6];
 
void build(){//建图
    int x=0;
    for(int i=1;i<=5;i++){
        if(!vis[x][bit[i]]){
            G[x][0]++;
            G[x][G[x][0]]=bit[i];
            vis[x][bit[i]]=true;
        }
        x=((x<<4)|bit[i]);
    }
 
    x=0;
    for(int i=5;i>=1;i--){
        if(!judge[x][bit[i]])
            judge[x][bit[i]]=++tot;
        x=judge[x][bit[i]];
    }
}
 
void dfs(int x,int y) {
    if(x==6){
        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++){
                int pos=((i-1)<<3)|j;
                printf("%d",res[pos]);
            }
            printf("\n");
        }
        printf("\n");
    }
    else {
        int minn;
        if(G[sumX[x]][0]>G[sumY[y]][0])
            minn=sumY[y];
        else
            minn=sumX[x];
        for(int i=1;i<=G[minn][0];i++){
            int pos=res[((x - 1) << 3) | y] = G[minn][i];
 
            int flag1,flag2;
            if(x+y!=6)
                flag1=true;
            else{
                flag1=judge[suf[x-1]][pos];
                suf[x]=judge[suf[x-1]][pos];
            }
            if(x!=y)
                flag2=true;
            else{
                flag2=vis[sum[x-1]][pos];
                sum[x]=((sum[x-1]<<4)|pos);
            }
 
            if(!flag1||!flag2||!vis[sumY[y]][pos]||!vis[sumX[x]][pos])//存在性剪枝
                continue;
 
            sumX[x]=((sumX[x]<<4)|pos);
            sumY[y]=((sumY[y]<<4)|pos);
 
            if(y<5)
                dfs(x,y+1);
            else
                dfs(x+1,1);
 
            sumX[x]>>=4;
            sumY[y]>>=4;
        }
    }
}
int main() {
    scanf("%d%d",&n,&m);
    for(int i=3;i<=99999;i+=2){//判素数
        if(!bprime[i]){
            if(i>=10000){//分解数位
                bit[1]=i/10000;
                bit[2]=i/1000%10;
                bit[3]=i/100%10;
                bit[4]=i/10%10;
                bit[5]=i%10;
                if(bit[1]+bit[2]+bit[3]+bit[4]+bit[5]==n)//各数位和等于素数
                    build();//建图
            }
            for(int j=i*3;j<=99999;j+=2*i)
                bprime[j]=true;
        }
    }
    sum[1]=m;
    sumX[1]=m;
    sumY[1]=m;
    res[1]=m;
    dfs(1,2);
    return 0;
}

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/577830.html

信息学奥赛一本通 1446：素数方阵通过100分

发表评论

评论列表（0条）

信息学奥赛一本通 1446：素数方阵 通过100分

发表评论

评论列表（0条）

信息学奥赛一本通 1446：素数方阵通过100分