题解 CF803A 【Maximal Binary Matrix】

frankchenfu

2018-02-15 21:22:40

Solution

这道题目贪心即可。首先我们考虑如何贪心。 ------------ 由于矩阵是字典序越小越优,所以我们要尽量填满前几行。对应的,由于填上了前几行,我们就要填上前几列。接下来,我们考虑当剩下的$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; } ```