题解 P1549 【棋盘问题(2)】

因为发现题解大多无法真正通过此题,要么是无法过$n = 9$,要么答案根本就是错误的,所以就想写篇题解。

先用线性筛预处理出素数,并直接暴力循环预处理出那些数和哪些数之间能拼成素数,当然可以再疯狂点,直接预处理出每两个数可以和哪些数拼成素数(反正$n$小,随你预处理)。
然后爆搜的时候注意搜索顺序,先搜第一行第一列,以保证第一行第一列之和最小。
然而普通的搜索顺序搜除去第一行第一列剩下的部分会有一个问题,即从小到大搜会导致$n = 9$很慢,若从大到小搜会导致$n = 7$很慢。
我的程序从大到小搜的话,$n = 7$需要$1s$多点,其它秒出,不过经测试开了$O2$在本地或是洛谷$IDE$上都能在$0.9s$内过。
不过我还不够满意,既然不能一直从小到大,也不能一直从大到小,那就折中一下呗,上随机数。
测试了$5$个随机数种子,总算让我找到一个能够使得程序秒出$1\sim 10$所有数据的了(甚至可以出$11,12$)。
这样总算是真正的$A$了此题了。
另外,我发现这个随机数种子仅是使得我本地能过,在洛谷$IDE$上却无法出$9$的数据,可能是因为操作系统不同导致相同随机数种子的结果不同,所以若真要搞过,还是$time(NULL)$看人品吧。。
当然我也难保我的程序是完全正确,欢迎指出错误。

#include<cstdio>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int N = 13;
const int M = N * N;
const int K = M << 1;
int a[N][N], p[M][M], pr[K], L[M], P[M][M][M], PL[M][M], n, l, o;
bool v[K], vis[M], pi[M][M];
inline int re()
{
    int x = 0;
    char c = getchar();
    bool p = 0;
    for (; c < '0' || c > '9'; c = getchar())
        p |= c == '-';
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    return p ? -x : x;
}
inline void ri(int &x, int &y)
{
    y++;
    if (y > n)
    {
        y = 1;
        x++;
    }
}
inline void dw(int &x, int &y)
{
    x++;
    if (x > n)
        x = y = 2;
}
bool dfs(int x, int y)
{
    if (x > n)
        return true;
    int i, le = a[x][y - 1], u = a[x - 1][y], xx = x, yy = y, g;
    if (!(x ^ 1) && y ^ 1)//搜第一行
    {
        ri(xx, yy);
        for (i = 1; i <= L[le]; i++)
            if (!vis[g = p[le][i]])
            {
                a[x][y] = g;
                vis[g] = 1;
                if (dfs(xx, yy))
                    return true;
                vis[g] = 0;
                a[x][y] = 0;
            }
    }
    else
        if (x ^ 1 && !(y ^ 1))//搜第一列
        {
            dw(xx, yy);
            for (i = 1; i <= L[u]; i++)
                if (!vis[g = p[u][i]])
                {
                    a[x][y] = g;
                    vis[g] = 1;
                    if (dfs(xx, yy))
                        return true;
                    vis[g] = 0;
                    a[x][y] = 0;
                }
        }
        else
        {
            ri(xx, yy);
            if (!(yy ^ 1))
                yy++;
            if (rand() & 1)//随机数折中
                for (i = PL[le][u]; i; i--)//从大到小搜
                {
                    g = P[le][u][i];
                    if (!vis[g])
                    {
                        a[x][y] = g;
                        vis[g] = 1;
                        if (dfs(xx, yy))
                            return true;
                        vis[g] = 0;
                        a[x][y] = 0;
                    }
                }
            else
                for (i = 1; i <= PL[le][u]; i++)//从小到大搜
                {
                    g = P[le][u][i];
                    if (!vis[g])
                    {
                        a[x][y] = g;
                        vis[g] = 1;
                        if (dfs(xx, yy))
                            return true;
                        vis[g] = 0;
                        a[x][y] = 0;
                    }
                }
        }
    return false;
}
int main()
{
    srand(9982123);//仅本地能过,洛谷IDE无法过9的数据,不行还是上time(NULL)吧
    int m, i, j, k, x;
    n = re();
    if (!(n ^ 1))//特判掉1
    {
        printf("NO");
        return 0;
    }
    o = n * n;
    m = o << 1;
    v[0] = v[1] = 1;
    for (i = 2; i <= m; i++)//线性筛素数
    {
        if (!v[i])
            pr[++l] = i;
        for (j = 1; j <= l; j++)
        {
            if (i * pr[j] > m)
                break;
            v[i * pr[j]] = 1;
            if (!(i % pr[j]))
                break;
        }
    }
    for (i = 1; i < o; i++)
        for (j = i + 1; j <= o; j++)//预处理每个数能和哪些数的和是素数
            if (!v[i + j])
            {
                p[i][++L[i]] = j;
                p[j][++L[j]] = i;
                pi[i][j] = pi[j][i] = 1;
            }
    for (i = 1; i <= o; i++)
        sort(p[i] + 1, p[i] + L[i] + 1);//排序
    for (i = 1; i < o; i++)//预处理每两个数能和哪些数拼成素数
        for (j = i + 1, m = L[i]; j <= o; j++)
            for (k = 1; k <= m; k++)
                if (pi[x = p[i][k]][j])
                    P[i][j][++PL[i][j]] = P[j][i][++PL[j][i]] = x;
    a[1][1] = 1;
    vis[1] = 1;
    if (dfs(1, 2))
        for (i = 1; i <= n; i++, printf("\n"))
            for (j = 1; j <= n; j++)
                printf("%d ", a[i][j]);
    else
        printf("NO");
    return 0;
}

发表于 2018-10-26 09:28:44 in 题解