题解：P13958 [ICPC 2023 Nanjing R] 谜题：问号

Wei_Han · 2026-11-08 19:44:53 · 题解

你只是想玩 mc 了。

考虑这个问号形的不是很好看，我们先组合出几种基础图形，后面就可能直接拿这个用了：

从左到右分别编号为 1,2,3，他们显然也可以任意旋转。

发现 3 可以密铺，那么 n \equiv 0 \pmod 4 就简单了：

然后因为 3 还可以转过来，所以 n \equiv 2 \pmod 4 可以这样做，写个暴力拍一拍什么的也可以发现这样肯定会有 4 个空位：

然后考虑奇数的情况，我们依然考虑 n \equiv 2 \pmod 4 这种添加一个边框的办法能不能扩展，发现如果再多一列我们就恰好可以把剩的位置换成一个 1，所以有：

所以我们现在可以让 n \equiv 3 \pmod 4 \to n \equiv 1 \pmod 4。

然后是 n \equiv 1 的情况，我们仍然考虑加边框，继续扩展刚才的做法，发现少两列问题很大。

这就意味着我们必须把一个 3 换成 2，手玩一下。大概的手玩过程是，发现这个时候上下不能对称放置了，所以把对称的 2 的方向变一下放到另一边，刚好占用了原来最右四列两个 3 的位置，就可以得到这样的图形：

所以我们就可以让 n \equiv 5 \pmod 4 \to n \equiv 1 \pmod 4。

但是发现这对于 n 小的时候不成立，我们还得手玩一下 n=3,5,7,9 的情况：

然后就讨论完了吧，一直这样做即可。代码写起来还挺麻烦的，但是这种题调起来比较简单。

:::info[代码]

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f3f3f3f3f
#define inf 0x3f3f3f3f
#define pr putchar(10)
#define fi first
#define se second
#define pp putchar(' ')
#define pii pair<ll,ll>
#define tri tuple<ll,ll,ll>
#define gt(k,x) (get<k>(x))
#define pdi pair<double,ll>
#define mem(aa,bb) memset(aa,bb,sizeof(aa))
#define fo(a,i,b) for(ll i = (a) ; i <= (b) ; ++ i )
#define Fo(a,i,b) for(ll i = (a) ; i >= (b) ; -- i )
#define pb push_back
#define eb emplace_back
#define bct __builtin_popcount
#define mk make_pair
#define IT iterator
#define all(x) x.begin(),x.end()
#define lbd lower_bound
#define ubd upper_bound
#define lowbit(x) ((x)&(-(x)))
#define gb(x,i) (((x)>>i)&1)
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define deb(a...) [&](auto...b){char s[]=" , ,"#a;strtok(s,",");((cerr<<strtok(0,",")<<"="<<b<<"; "),...)<<endl;}(__LINE__,a)
//#pragma GCC optimize(2)
using namespace std;
bool ST;

typedef long long i64;
typedef unsigned int u32;
typedef unsigned long long u64;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;

// typedef int ll;
typedef long long ll;
// typedef __int128 ll;

// #define getchar getchar_unlocked
// #define putchar putchar_unlocked

const ll mod=1e9+7;
template <class T> inline bool ckmn(T &a,T b){return a>b?a=b,1:0;}
template <class T> inline bool ckmx(T &a,T b){return a<b?a=b,1:0;}
template <class T> inline void _A(T &x,T y){x=(x+y>=mod?x+y-mod:x+y);}
template <class T> inline void _M(T &x,T y){x=1ll*x*y%mod;}
template <class T> inline T A_(T x,T y){return (x+y>=mod?x+y-mod:x+y);}
template <class T> inline T M_(T x,T y){return 1ll*x*y%mod;}
template <class T> inline void read(T &s)
{
   s=0;int f=1;char c=getchar();while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
   while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();s*=f;return;
}
template <class T> inline void wr(T x)
{
   if(x<0)putchar('-'),x=-x;int buf[21],top=0;while(x)buf[++top]=x%10,x/=10;
   if(!top)buf[++top]=0;while(top)putchar(buf[top--]^'0');return;
}
template <class T, class ...A> inline void read(T &x,A &...a){read(x);read(a...);}
template <class T, class ...A> inline bool ckmn(T &x,T y,A ...a){return ckmn(x,y)|ckmn(x,a...);}
template <class T, class ...A> inline bool ckmx(T &x,T y,A ...a){return ckmx(x,y)|ckmx(x,a...);}
template <class T, class ...A> inline void _A(T &x,T y,A ...a){_A(x,y),_A(x,a...);}
template <class T, class ...A> inline void _M(T &x,T y,A ...a){_M(x,y),_M(x,a...);}
template <class T, class ...A> inline T A_(T x,T y,A ...a){return A_(A_(x,y),a...);}
template <class T, class ...A> inline T M_(T x,T y,A ...a){return M_(M_(x,y),a...);}

// template<class... T> void deb_(int line, const T&... v){cerr<<"LINE "<<line<<" =";int _[]={0,(cerr<<' '<<v,0)...};(void)_;cerr<<'\n';}
// #define deb(...) deb_(__LINE__, __VA_ARGS__)

const ll N=2e3+5,M=1e5+5;
inline void solve()
{
    ll n,_n;read(n),_n=n;vector<vector<ll>> a(n+2,vector<ll>(n+2,0));ll cnt=0;
    auto A = [&](ll i,ll j){a[i][j]=a[i][j+1]=a[i+1][j+1]=a[i+2][j]=++cnt;};
    auto B = [&](ll i,ll j){a[i][j]=a[i][j+2]=a[i+1][j+1]=a[i+1][j+2]=++cnt;};
    auto C = [&](ll i,ll j){a[i][j+1]=a[i+1][j]=a[i+2][j]=a[i+2][j+1]=++cnt;};
    auto D = [&](ll i,ll j){a[i][j]=a[i][j+1]=a[i+1][j]=a[i+1][j+2]=++cnt;};
    auto E = [&](ll i,ll j){a[i][j]=a[i][j+1]=a[i+1][j]=a[i+2][j+1]=++cnt;};
    auto F = [&](ll i,ll j){a[i][j+1]=a[i][j+2]=a[i+1][j]=a[i+1][j+2]=++cnt;};
    auto G = [&](ll i,ll j){a[i][j]=a[i+1][j+1]=a[i+2][j]=a[i+2][j+1]=++cnt;};
    auto H = [&](ll i,ll j){a[i][j]=a[i][j+2]=a[i+1][j]=a[i+1][j+1]=++cnt;};
    if(n==1) return cout << "0\n0\n",void();
    if(n==2) return cout << "0\n0 0\n0 0\n",void();
    if(n%4==0) for(ll i=1;i<=n;i+=2) for(ll j=1;j+3<=n;j+=4) D(i,j),F(i,j+1);
    else if(n%4==2)
    {
        for(ll i=1;i<=n;i+=2) for(ll j=1;j+3<=n;j+=4) D(i,j),F(i,j+1);
        for(ll i=1;i+3<=n;i+=4) A(i,n-1),G(i+1,n-1);
    }
    else if(n%4==3)
    {
        for(ll j=1;j+3<=n;j+=4) D(n-1,j),F(n-1,j+1);
        for(ll i=1;i+3<=n;i+=4) A(i,n-1),G(i+1,n-1);
        A(n-2,n-1),D(n-1,n-2),n-=2;
    }
    if(n==5) E(1,1),G(2,2),D(1,3),C(1,4),F(4,3),n=1;
    if(n%4==1&&n>1)
    {
        ll x=1,y=1,nx=x+n-1,ny=y+n-1;
        while(n>9)
        {
            nx=x+n-1,ny=y+n-1;
            for(ll j=1;j+5<=n;j+=4)
                D(x,y+j-1),F(x,y+j);
            for(ll j=1;j+5<=n;j+=4)
                D(nx-1,y+j-1),F(nx-1,y+j);
            E(x,ny-4),G(x+1,ny-3),D(x,ny-2),C(x,ny-1);
            for(ll i=4;i+6<=n;i+=4)
                A(x+i-1,ny-1),G(x+i,ny-1);
            for(ll i=5;i+5<=n;i+=4)
                A(x+i-1,ny-3),G(x+i,ny-3);
            H(nx-4,ny-3),F(nx-5,ny-2),
            A(nx-3,ny-1),G(nx-2,ny-1),
            A(nx-2,ny-3),D(nx-1,ny-4),n-=4,x+=2;
        }
        D(x,y),F(x,y+1),D(x,y+4),C(x,y+5),
        A(x,y+7),G(x+1,y+7),A(x+4,y+7),D(x+5,y+6),
        D(x+7,y+5),F(x+7,y+6),F(x+7,y+2),E(x+6,y+2),
        A(x+5,y),G(x+6,y),G(x+2,y),F(x+2,y),
        D(x+2,y+3),B(x+3,y+4),D(x+4,y+2),B(x+5,y+3);
/*
 A   B   C   D   E   F   G   H 
@@* @*@ *@* @@* @@* *@@ @** @*@ 
*@* *@@ @** @*@ @** @*@ *@* @@* 
@** *** @@* *** *@* *** @@* *** 
*/
    }
    cout << cnt << '\n',n=_n;
    fo(1,i,n) fo(1,j,n) cout << a[i][j] << ' ',j==n&&pr;
}
bool ED;
signed main(){
    ll T;read(T);while(T--) solve();

    cerr << "Time: " << (double)clock()/CLOCKS_PER_SEC << "s\n";
    cerr << "Memory: " << abs(&ST - &ED) / 1024.0 / 1024.0 << " MB\n";
    return 0;
}

:::