frankchenfu 的博客

frankchenfu 的博客

题解 CF803A 【Maximal Binary Matrix】

posted on 2018-02-15 21:22:40 | under 题解 |

这道题目贪心即可。首先我们考虑如何贪心。


由于矩阵是字典序越小越优,所以我们要尽量填满前几行。对应的,由于填上了前几行,我们就要填上前几列。接下来,我们考虑当剩下的$1$不足以填满整行时($rest$表示剩余的可填充的$1$的数量)应该怎么办。假设对于以下矩阵,我们还可以填充$4$个$1$($rest=4$)。

$$\begin{bmatrix} 1&1&1&1\\1&0&0&0\\1&0&0&0\\1&0&0&0\end{bmatrix}\quad(rest=4)$$

这样,我们一定需要先填充$0$的部分的左上角,以确保字典序最小。就像这样:

$$\begin{bmatrix} 1&1&1&1\\1&1&0&0\\1&0&0&0\\1&0&0&0\end{bmatrix}\quad(rest=3)$$

然后我们再考虑,接下来的$3$个$1$,我们为了确保对称性,事实上只能在同一行放一个(对称到列再放一个)。就是这样:$$\begin{bmatrix} 1&1&1&1\\1&1&1&0\\1&1&0&0\\1&0&0&0\end{bmatrix}\quad(rest=1)$$

这个时候,我们发现$rest=1$。为了对称,我们只好把它放在对角线上。于是,最终的矩阵就被我们排好了。也就是说,如果填充不满,是奇数就直接填充本行(本列),否则还有在下一行填充。

$$\begin{bmatrix} 1&1&1&1\\1&1&1&0\\1&1&1&0\\1&0&0&0\end{bmatrix}\quad(rest=0)$$

再如当$rest=5$的时候,因为是奇数,没有不对称的问题,不需要把$1$强制放到对角线上,所以最终矩阵如下:

$$\begin{bmatrix} 1&1&1&1\\1&1&1&1\\1&1&0&0\\1&1&0&0\end{bmatrix}$$


根据上面这两个例子,我们可以看出一个最佳的排列方法:

设递归函数$f(p,rest)$用于填充矩阵,其中$p$为右下方没有填充的全$0$矩阵的宽度,$rest$含义同上。

  1. 当$rest> 2p-1$时,直接填满当前行,递归调用$f(p-1,rest-2p+1)$.
  2. 当$rest\le 2p-1$时,尝试尽可能在对称的情况下填充,由于有奇偶性,调用$f(p-1,k+1\!\mod 2)$。

注意边界条件有$2$个:

  • 当$rest=1$的时候,需要标记一个位置之后再直接返回。
  • 当$rest=0$的时候,直接返回。

注意-1的情况只有当需要填充的$k> n^{2}$的时候才会出现,不会由于对称而产生其他的-1情况。


代码如下。为了方便填充,代码中的递归函数还有一个$pos$表示全$0$矩阵左上角所在的行。

#include<cstdio>
#include<cstring>
const int MAXN=110;
int a[MAXN][MAXN];

void solve(int n,int pos,int k)
{
    if(k==1)
    {
        a[pos][pos]=1;
        return;
    }
    if(k==0)
        return;
    if(k<=(n<<1)-1)
    {
        for(int i=pos;i<=pos+(k-1>>1);i++)
            a[pos][i]=a[i][pos]=1;
        solve(n-1,pos+1,(k&1)^1);
    }
    else
    {
        for(int i=pos;i<=pos+n-1;i++)
            a[pos][i]=a[i][pos]=1;
        solve(n-1,pos+1,k-(n<<1)+1);
    }
    return; 
}

int main()
{
    int n,k;scanf("%d%d",&n,&k);
    if(k>n*n)
    {
        puts("-1");
        return 0;
    }
    solve(n,1,k);
    for(int i=1;i<=n;i++,puts(""))
        for(int j=1;j<=n;j++)
            printf("%d ",a[i][j]);
    return 0;
}