题解 CF803A 【Maximal Binary Matrix】
frankchenfu
2018-02-15 21:22:40
这道题目贪心即可。首先我们考虑如何贪心。
------------
由于矩阵是字典序越小越优,所以我们要尽量填满前几行。对应的,由于填上了前几行,我们就要填上前几列。接下来,我们考虑当剩下的$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$矩阵左上角所在的行。
```cpp
#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;
}
```