专栏文章

P13052 [GCJ 2020 Qualification] Indicium 题解

JJorisyKuno Kako
P13052题解参与者 3已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@miooe5pw
此快照首次捕获于
2025/12/02 22:30
3 个月前
此快照最后确认于
2025/12/02 22:30
3 个月前
查看原文
考虑一个矩阵主对角线会是什么样的排布。
首先，一个显然的事情是，不存在合法的方案，使得其主对角线是 x,x,⋯ ,x,x,yx,x,\cdots,x,x,y，不然最后一行一列的 xx 就没地方放了。
那考虑 x,x,⋯ ,x,y,zx,x,\cdots,x,y,z 的情况。
一个比较简单的结论是：
对于任意正整数 k∈[n,n2]k\in[n,n^2]，都存在 x,y,z∈[1,n]x,y,z\in[1,n]，满足 (n−2)x+y+z=k(n-2)x+y+z=k。
证明考虑归纳。k=nk=n 显然成立。对于 k>nk>n，假设之前有一组 x,y,zx,y,z，那么如果 y+z<2ny+z<2n，那么就可以对 y,zy,z 中较小的那个 +1+1。若 y+z=2ny+z=2n，那么就可以让 x←x+1x\gets x+1，这样 y,zy,z 总体就要去掉 n−2n-2，又回到上一种情况，再对较小的 +1+1 即可。
按照以上方式，再进行一些微调，我们可以得到一组 x,y,zx,y,z。
然后我们考虑如何在这个主对角线的基础上构造。
首先被 y,zy,z 占用的行列，剩余的两个 xx 是可以确定的。
[xx⋱xyxxz]\begin{bmatrix} x&&&\\ &x&&\\ &&\ddots&&\\ &&&x&&\\ &&&&y&x\\ &&&&x&z \end{bmatrix}
由于 x,y,zx,y,z 是较为特殊的，所以我们钦定第一行为 x,y,z,1,2,⋯ ,nx,y,z,1,2,\cdots,n（即在 1,2,⋯n1,2,\cdots n 的基础上，将 x,y,zx,y,z 提到前面来）。
假如没有最后两行列，我们可以直接每行在上一行的基础上循环移位填入。
那现在这两行列较为特殊，我们其实也可以类似地填入。
下面以 n=7,x=1,y=2,z=3n=7,x=1,y=2,z=3 为例。
初始是这样：
[111112113]\begin{bmatrix} 1&&&&&&\\ &1&&&&&\\ &&1&&&&\\ &&&1&&&\\ &&&&1&&\\ &&&&&2&1\\ &&&&&1&3 \end{bmatrix}
接下来我们填入 22。按照原本的循环移位的思路，我们试着填在 11 的后面一个。
[12121212122113]\begin{bmatrix} 1&2&&&&\\ &1&2&&&\\ &&1&2&&\\ &&&1&2&\\ &&&&1&\red2&\\ &&&&&\red2&1\\ &&&&&1&3 \end{bmatrix}
发现填到这里的时候爆了，我们跳过这一位。
[121212121221213]\begin{bmatrix} 1&2&&&&\\ &1&2&&&&\\ &&1&2&&&\\ &&&1&2&&\\ &&&&1&&2\\ &&&&&2&1\\ 2&&&&&1&3 \end{bmatrix}
接下来填 33。
[1231231231231221213]\begin{bmatrix} 1&2&3&&&\\ &1&2&3&&\\ &&1&2&3&\\ &&&1&2&3\\ &&&&1&&\red2\\ &&&&&2&1\\ 2&&&&&1&\red3 \end{bmatrix}
发现位置冲突了，并且 33 已经出现过，那么 33 自动向后一个填入。
[123123123123312321213]\begin{bmatrix} 1&2&3&&&\\ &1&2&3&&\\ &&1&2&3&\\ &&&1&2&3\\ 3&&&&1&&2\\ &3&&&&2&1\\ 2&&&&&1&3 \end{bmatrix}
接下来填 44。
[1234123412341234312321213]\begin{bmatrix} 1&2&3&4&&\\ &1&2&3&4&\\ &&1&2&3&4\\ &&&1&2&3&4\\ \red3&&&&1&&2\\ &3&&&&2&1\\ 2&&&&&1&3 \end{bmatrix}
发现只是单纯的冲突了，我们这次跳过，但下面需要找机会补回来。
[12341234123412343412321213]\begin{bmatrix} 1&2&3&4&&\\ &1&2&3&4&\\ &&1&2&3&4\\ &&&1&2&3&4\\ 3&4&&&1&&2\\ &3&&&&2&1\\ 2&&&&&1&3 \end{bmatrix}
发现这一行对应我们没有填的列是可以填的，立刻补回来。后面正常填。
[1234123412341234341243212413]\begin{bmatrix} 1&2&3&4&&\\ &1&2&3&4&\\ &&1&2&3&4\\ &&&1&2&3&4\\ 3&4&&&1&&2\\ 4&3&&&&2&1\\ 2&&4&&&1&3 \end{bmatrix}
填 55 的时候，遇到冲突和解决冲突的过程是一样的。
若有之前冲突的没填的列，在这一行可以填，那就填；若当前列冲突，则向后一列再填，并压入一个栈，栈内都是跳过未填的列。
[12345123451234551234345124352125413]\begin{bmatrix} 1&2&3&4&5&\\ &1&2&3&4&5\\ &&1&2&3&4&5\\ 5&&&1&2&3&4\\ 3&4&5&&1&&2\\ 4&3&&5&&2&1\\ 2&5&4&&&1&3 \end{bmatrix}
66 和 77 用相同的方式可以填完。
[1234567712345667123455671234345617243657212547613]\begin{bmatrix} 1&2&3&4&5&6&7\\ 7&1&2&3&4&5&6\\ 6&7&1&2&3&4&5\\ 5&6&7&1&2&3&4\\ 3&4&5&6&1&7&2\\ 4&3&6&5&7&2&1\\ 2&5&4&7&6&1&3 \end{bmatrix}
至于这样为什么一定能得到合法方案，我暂时还不会证明，但是它确实过了。如果你会的话可以评论区提出或私信我，我会给你磕头的。
此外注意一些无解的 corner cases。
尽管 n≤50n\le 50，时间复杂度却是 O(n2)O(n^2)。
CPP
#include<bits/stdc++.h>
#define N 55
#define ll long long
#define mod 
using namespace std;

int n,m,ans[N][N],a[N];
bool fl[N][N];

void sol()
{
    static int cas=0;
    cin>>n>>m;
    cout<<"Case #"<<++cas<<": ";
    if(m<n||m==n+1||m==n*n-1||n==3&&m==5||n==3&&m==7)
    {
        cout<<"IMPOSSIBLE\n";
        return;
    }
    int p=1,q=1,r=1;
    m-=n;
    while(m--)
    {
        if(q+r==n*2)
        {
            p++;
            q-=n-2;
        }
        if(++q>r) swap(q,r);
    }
    if(p==r) swap(q,r);
    if(p==q&&q!=r)
    {
        if(r==n) p++,r-=n-2;
        q--,r++;
    }
    // cerr<<p<<','<<q<<','<<r<<'\n';
    iota(a+1,a+n+1,1);
    sort(a+1,a+n+1,[&](int x,int y){return x==p?1:y==p?0:x==q?1:y==q?0:x==r?1:y==r?0:x<y;});
    memset(fl,0,sizeof(fl));
    memset(ans,0,sizeof(ans));
    ans[n-1][n-1]=q;
    ans[n][n]=r;
    fl[n-1][q]=fl[n][r]=1;
    for(int id=1;id<=n;id++)
    {
        int x=a[id];
        stack<int>st;
        for(int i=1,j=id;i<=n;i++)
        {
            if(ans[i][i]==x) continue;
            if(!st.empty()&&!ans[i][st.top()])
            {
                ans[i][st.top()]=x;
                fl[st.top()][x]=1;
                st.pop();
                continue;
            }
            while(ans[i][j]||fl[j][x])
            {
                // cerr<<i<<','<<j<<' ';
                if(!fl[j][x]) st.push(j);
                j=j%n+1;
            }
            ans[i][j]=x;
            fl[j][x]=1;
        }
    }
    cout<<"POSSIBLE\n";
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            cout<<ans[i][j]<<' ';
        }
        cout<<'\n';
    }
}

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t;
    cin>>t;
    while(t--) sol();
    return 0;
}

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...