题解：P10871 [COTS/CETS 2022] 皇后 Kraljice

· · 题解

更好的阅读体验：我的博客！

这题我想到了一个绝妙的构造方法，空间足够，我写下了。

首先，当 n\le 2 时答案均为 1。下面 n\ge 3。

此时若 n 为奇数，则答案为 n^2。否则答案为 n^2-2。

接下来构造。请注意观察 n=3 的情况，尤其是倒二步剩下的那个缺口，在后面十分关键。

首先考虑偶数，先是 n=4 的情况。

我们先构造一个缺口：

0111
0x11
0111
x000

而后再依次填上位置 (1,1),(4,2),(4,4),(3,1),(2,1),(4,3) 即可，其中两个 x 是最后空的格子。

然后考虑构造一个如下的外壳递归到 n-2 的情况：

111111
100001
100001
100001
100001
111111

首先这样：

1357...00
0000...00
0000...00
0000...00
0000...00
4286...00

继续下去构造成这样 (*)：

1111...1100
0000...0000
0000...0000
0000...0000
0000...0000
1111...1100

但此时最后四个不能类似构造（对角线有影响），稍微动点脑子：

1111...11AB
0000...0000
0000...0000
0000...0000
0000...0000
1111...11DC

然后是左右两侧：

1111...1111
A000...000D
1000...0004
.  .      .
.    .    .
.      .  .
3000...0002
C000...000B
1111...1111

此时没有对角线的影响能直接构造完整个边框。

然后递归：n\to n-2\to n-4\to \cdots \to 4，最后上 n=4 的构造即可。

偶数：

inline void out(int x,int y){cout<<x<<" "<<y<<"\n";}//输出
inline void ex3(int m,int M)
{
    out(m,M+1);out(m+1,M-1);out(m,M);out(m-1,M-1);
    out(m+1,M+1);out(m+1,M);out(m-1,M);out(m-1,M+1);
}//3 的带有缺口的构造
namespace even
{
    inline void sol(int l,int r)
    {
        if(l+3==r) return;
        for(int i=l;i<r-2;i+=2)
        {
            out(l,i);out(r,i+1);
            out(l,i+1);out(r,i);
        }
        out(l,r-1);out(l,r);
        out(r,r);out(r,r-1);

        for(int i=l+1;i<=(l+r-1)/2;i++)
        {
            out(i,l);out(l+r-i,r);
            out(l+r-i,l);out(i,r);
        }
        sol(l+1,r-1);
    }//构造边框，递归到 n-2
    inline void get()
    {
        cout<<n*n-2<<"\n";
        sol(1,n);
        int l=(n/2)-2;ex3(l+2,l+3);

        out(l+1,l+1);
        out(l+4,l+2);
        out(l+4,l+4);
        out(l+3,l+1);
        out(l+2,l+1);
        out(l+4,l+3);//n=4 的构造
    }
}

然后考虑奇数，此时构造边框就比较难了（反正我不会）。

此时考虑一点其他的优美构型，参考 n 为偶数时左右边框的方法：

先这样：

0000000
1000001
1000001
0000000
1000001
1000001
0000000

再这样：

0110110
1000001
1000001
0000000
1000001
1000001
0110110

递归下去，构造成只剩余中间米字型：

0110110
1010101
1100011
0000000
1100011
1010101
0110110

此时如果直接填满中间 3\times 3，则剩下就没有位置可以给我们填了。

还是考虑 3\times 3 构造中的缺口！

我们先这样构造，其中 x 位置是缺口：

0110110
1010101
1111111
00x1100
1111111
1010101
0110110

然后继续剥外壳（按字母顺序）：

E11B11G
1010101
1111111
A0x110C
1111111
1010101
D11H11F

然后把剥外壳的过程递归下去构造，最后填上位置 x 即可！

奇数：

inline void out(int x,int y){cout<<x<<" "<<y<<"\n";}//输出
inline void ex3(int m,int M)
{
    out(m,M+1);out(m+1,M-1);out(m,M);out(m-1,M-1);
    out(m+1,M+1);out(m+1,M);out(m-1,M);out(m-1,M+1);
}//3 的带有缺口的构造
namespace odd
{
    inline void sol(int l,int r)
    {
        if(l==r) return;int m=(l+r)/2;
        for(int i=l+1;i<m;i++)
        {
            out(i,l);out(l+r-i,r);
            out(n+1-i,l);out(i,r);
        }
        for(int i=l+1;i<m;i++)
        {
            out(l,i);out(r,l+r-i);
            out(l,l+r-i);out(r,i);
        }
        sol(l+1,r-1);
    }//递归构造到只剩米字型
    inline void sol1(int l,int r)
    {
        if(l+2==r) return;int m=(l+r)>>1;
        out(m,l);out(l,m);out(m,r);
        out(r,l);out(l,l);out(r,r);out(l,r);
        out(r,m);
        sol1(l+1,r-1);
    }//继续剥米字型的外壳
    inline void get()
    {
        cout<<n*n<<"\n";
        sol(1,n);
        int m=(n+1)/2;ex3(m,m);
        sol1(1,n);
        out(m,m-1);
    }
}

于是本题就做完啦！这篇题解给出了一种极其精妙且极富有对称性的构造方法。欢迎大家学习借鉴。

完整代码：

#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1<<10|5;
int n;
inline void out(int x,int y){cout<<x<<" "<<y<<"\n";}
inline void ex3(int m,int M)
{
    out(m,M+1);out(m+1,M-1);out(m,M);out(m-1,M-1);
    out(m+1,M+1);out(m+1,M);out(m-1,M);out(m-1,M+1);
}
namespace odd
{
    inline void sol(int l,int r)
    {
        if(l==r) return;int m=(l+r)/2;
        for(int i=l+1;i<m;i++)
        {
            out(i,l);out(l+r-i,r);
            out(n+1-i,l);out(i,r);
        }
        for(int i=l+1;i<m;i++)
        {
            out(l,i);out(r,l+r-i);
            out(l,l+r-i);out(r,i);
        }
        sol(l+1,r-1);
    }
    inline void sol1(int l,int r)
    {
        if(l+2==r) return;int m=(l+r)>>1;
        out(m,l);out(l,m);out(m,r);
        out(r,l);out(l,l);out(r,r);out(l,r);
        out(r,m);
        sol1(l+1,r-1);
    }
    inline void get()
    {
        cout<<n*n<<"\n";
        sol(1,n);
        int m=(n+1)/2;ex3(m,m);
        sol1(1,n);
        out(m,m-1);
    }
}
namespace even
{
    inline void sol(int l,int r)
    {
        if(l+3==r) return;
        for(int i=l;i<r-2;i+=2)
        {
            out(l,i);out(r,i+1);
            out(l,i+1);out(r,i);
        }
        out(l,r-1);out(l,r);
        out(r,r);out(r,r-1);

        for(int i=l+1;i<=(l+r-1)/2;i++)
        {
            out(i,l);out(l+r-i,r);
            out(l+r-i,l);out(i,r);
        }
        sol(l+1,r-1);
    }
    inline void get()
    {
        cout<<n*n-2<<"\n";
        sol(1,n);
        int l=(n/2)-2;ex3(l+2,l+3);

        out(l+1,l+1);
        out(l+4,l+2);
        out(l+4,l+4);
        out(l+3,l+1);
        out(l+2,l+1);
        out(l+4,l+3);
    }
}
int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
    if(n<=2) return cout<<"1\n1 1\n",0;
    return (n&1)?odd::get():even::get(),0;
}

</details>