#10024. 「一本通 1.3 练习 3」质数方阵

loj题目传送门
一本通题目传送门
洛谷传送门
原题是UVA835，是多测

思路

肯定是要剪枝的呀
众所周知，dfs的路径像树一样
显而易见，树的某一层的节点越少，他的下面的分支就越少
于是我们考虑改变搜索顺序来剪掉更多的分支
一个数的末位要是 \(0\)，那他肯定不是质数。于是我们先从所有数的末位开填
对角线由于斜着，所以可以影响到更多行和列。于是我们在填对角线
注意：对角线是从左上到右下和左下到右上的
最后我们要尽可能让某行某列满，再剪掉更多分支（这个可以随便选某行某列，就是选剩空少的就行）
填表顺序如下：

我们不能等他填完一行/一列/对角线才去检查他是否是质数，这样会很浪费时间
于是剪枝
先枚举出所有的五位质数，用一个五维数组pri[][][][][]来存放
然后我们把质数的某几位用 \(10\) 替换，代表这几位还没填
把替换完的数也标成质数，表示要是当前填成这样有可能是质数
由于我们不是按顺序搜索的，所以最后还需要排个序

代码

#include<bits/stdc++.h>
#define ll long long
#define pc putchar
using namespace std;
template<typename T>
inline void read(T &x)
{
    x=0;
    T f=1;
    char c=getchar();
    while(!isdigit(c)){if(!isspace(c))f=-1; c=getchar();}
    while(isdigit(c)){x=x*10+(c^48); c=getchar();}
    x*=f;
    return;
}
template<typename T,typename... Args> inline void read(T &x, Args&... args){read(x); read(args...);}
template<typename Z>
inline void write(Z x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar((x%10)^48);
}
template<typename Z,typename... Args> inline void write(Z x, Args... args){write(x); putchar(' '); write(args...);}
const int order[27][3] = {//搜索顺序
    {0, 0, 0},
    {0, 1, 1},
    {0, 1, 5},
    {0, 2, 5},
    {0, 3, 5},
    {0, 4, 5},
    {0, 5, 5},
    {0, 5, 1},
    {0, 5, 2},
    {0, 5, 3},
    {0, 5, 4},
    {0, 2, 2},
    {0, 3, 3},
    {0, 4, 4},
    {0, 4, 2},
    {0, 2, 4},
    {0, 1, 2},
    {0, 3, 2},
    {0, 1, 4},
    {0, 3, 4},
    {0, 3, 1},
    {0, 2, 1},
    {0, 4, 1},
    {0, 1, 3},
    {0, 2, 3},
    {0, 4, 3},
};
struct sol{
    int a[6][6];
    void copy(int b[6][6])
    {
        for(int i=1;i<=5;i++)
            for(int j=1;j<=5;j++)
                a[i][j] = b[i][j];
    }
    void out()//输出
    {
        for(int i=1;i<=5;i++)
        {
            for(int j=1;j<=5;j++)
                write(a[i][j]);
            pc('\n');
        }
        pc('\n');
    }
    friend bool operator<(const sol& x, const sol& y){//排序函数
        for(int i=1;i<=5;i++)
            for(int j=1;j<=5;j++)
            	if(x.a[i][j] != y.a[i][j])//相等的话暂时不能返回
					return (x.a[i][j] < y.a[i][j]);//从小到大
    }
};
int sum, k, a[6][6];
bool pri[11][11][11][11][11];
bool is_p(int x)//检验是否是质数
{
    for(int i=2;i*i<=x;i++)
        if(x%i == 0)
            return 0;
    return 1;
}
void cope_prime()
{
    for(int x=10000;x<=99999;x++)//枚举五位质数
        if(is_p(x))
        {
            int p[6], s=x;
            p[5] = s%10; s /= 10;//每位分解出来
            p[4] = s%10; s /= 10;
            p[3] = s%10; s /= 10;
            p[2] = s%10; s /= 10;
            p[1] = s%10;
            for(int i1=0;i1<=1;i1++)
                for(int i2=0;i2<=1;i2++)
                    for(int i3=0;i3<=1;i3++)
                        for(int i4=0;i4<=1;i4++)
                            for(int i5=0;i5<=1;i5++)
                            {
                                int a,b,c,d,e;
                                i1 ? a=p[1] : a=10;//进行替换
                                i2 ? b=p[2] : b=10;
                                i3 ? c=p[3] : c=10;
                                i4 ? d=p[4] : d=10;
                                i5 ? e=p[5] : e=10;
                                pri[a][b][c][d][e] = 1;//标记
                            }
        }
}
bool check(int x,int y)
{
    bool ful = 1;//满没满, 0为有空, 1为满了
    int cnt=0, p[10];//cnt记录和; p[]记录每一位数字, 判断是否是质数
    for(int i=1;i<=5;i++)//列
    {
        if(a[i][y] == -1) ful = 0, p[i] = 10;//有空缺
        else p[i] = a[i][y];//这位有数，记录
        if(ful) cnt += a[i][y];//没有空缺, 累加进和
    }
    if(pri[p[1]][p[2]][p[3]][p[4]][p[5]] == 0) return 0;//不是质数
    if(ful && cnt != sum) return 0;//全填了, 但是和不对

    ful = 1; cnt = 0;
    for(int i=1;i<=5;i++)//行
    {
        if(a[x][i] == -1) ful = 0, p[i] = 10;
        else p[i] = a[x][i];
        if(ful) cnt += a[x][i];
    }
    if(pri[p[1]][p[2]][p[3]][p[4]][p[5]] == 0) return 0;
    if(ful && cnt != sum) return 0;

    if(x == y)//从左上到右下的对角线
    {
        ful = 1; cnt = 0;
        for(int i=1;i<=5;i++)
        {
            if(a[i][i] == -1) ful = 0, p[i] = 10;
            else p[i] = a[i][i];
            if(ful) cnt += a[i][i];
        }
        if(pri[p[1]][p[2]][p[3]][p[4]][p[5]] == 0) return 0;
        if(ful && cnt != sum) return 0;
    }

    if(x+y == 6)//从左下到右上的对角线
    {
        ful = 1; cnt = 0;
        for(int i=5;i>=1;i--)
        {
            int j = 6-i;
            if(a[i][j] == -1) ful = 0, p[j] = 10;
            else p[j] = a[i][j];
            if(ful) cnt += a[i][j];
        }
        if(pri[p[1]][p[2]][p[3]][p[4]][p[5]] == 0) return 0;
        if(ful && cnt != sum) return 0;
    }
	return 1;//检查全都合格啦
}
vector<sol> ans;
void dfs(int pos)
{
    if(pos == 26)//都填完了
    {
        sol tmp;
        tmp.copy(a);
        ans.push_back(tmp);//记录答案
        return;
    }
    int x = order[pos][1], y = order[pos][2];
    if(pos == 1)//第一个数，得用他给的数
    {
        a[1][1] = k;
        dfs(2);
        a[1][1] = -1;//回溯
        return;
    }
    for(int i=0;i<=9;i++)//枚举搜索
    {
        a[x][y] = i;
        if(check(x, y))//填这个数可行
            dfs(pos + 1);//接着填
    }
    a[x][y] = -1;//回溯
    return;
}
int main()
{
    cope_prime();
    read(sum, k);
    for(int i=1;i<=5;i++)
        for(int j=1;j<=5;j++)
            a[i][j] = -1;
    dfs(1);
    if(ans.empty()) puts("NONE");
    else
    {
        sort(ans.begin(), ans.end());
        for(auto i:ans)
            i.out();
    }
    return 0;
}