题解 CF803A Maximal Binary Matrix

Luogu

codeforces

前言

模拟赛原题。。

好好一道送分被我硬打成爆蛋。。

\(\sf{Solution}\)

看了一波数据范围，感觉能 dfs 骗分。

骗成正解了。

大概就是将这个 \(n\times n\) 的矩阵全扫一遍，可以选择填 \(1\) 或不填。回溯一下就行啦。

位置问题

假设现在的坐标为 \((x,y)\)

若 \(x>n\) ，则结束 dfs ，比较一下矩阵字典序，较为简单不题。

若 \(y>n\) ，则 \(x→x+1,y=1\) ，即跳到下一行第一位。

对称处理 （定义 \(a_{x,y}\) 为当前搜到的地方）

在对角线上

只填这个地方。

其他

填 \(a_{x,y}\) 和 \(a_{y,x}\) 。

填 \(1\) 的话就要相应处理 \(k\) 。

特判

\(k=0\) ，输出全 \(0\) 矩阵。

\(\sf{Code}\)

写得有点麻烦。。

#include<iostream>

#include<cstdio>

using namespace std;

int n,k;

bool flag,m[105][105],q[105][105];

inline bool p()

{

	for(int i=1;i<=n;++i)

		for(int j=1;j<=n;++j)

			if(m[i][j]<q[i][j])

				return flag=true;

	return false;

}

inline void dfs(int x,int y,int d)

{

	if(y>n)

		++x,y=1;

	if(d==0)

	{

		if(p())

			for(int i=1;i<=n;++i)

				for(int j=1;j<=n;++j)

					m[i][j]=q[i][j];

		return ;

	}

	if(x>n)

		return ;

	if(x==y&&d>=1&&!q[x][y])

			q[x][y]=1,dfs(x,y+1,d-1),q[x][y]=0;

	else if(x!=y&&d>=2&&(!q[x][y]||!q[y][x]))

	{

		if(q[x][y]==0&&q[y][x]==0)

			q[x][y]=1,q[y][x]=1,dfs(x,y+1,d-2),q[x][y]=0,q[y][x]=0;

		else if(q[x][y]==1&&q[y][x]==0)

			q[y][x]=1,dfs(x,y+1,d-1),q[y][x]=0;

		else if(q[x][y]==0&&q[y][x]==1)

			q[x][y]=1,dfs(x,y+1,d-1),q[x][y]=0;

	}

	else dfs(x,y+1,d);

	return ;

}

signed main()

{

	ios::sync_with_stdio(false);

	cin>>n>>k;

	if(k==0)

	{

		for(int i=1;i<=n;++i,cout<<"\n")

			for(int j=1;j<=n;++j)

				cout<<"0 ";

		return 0;

	}

	if(k>n*n)

	{

		cout<<-1;

		return 0;

	}

	q[1][1]=1;

	dfs(1,2,k-1);

	if(flag)

		for(int i=1;i<=n;++i,cout<<"\n")

			for(int j=1;j<=n;++j)

				cout<<m[i][j]<<" ";

	else cout<<"-1";

	return 0;

}

题解 CF803A Maximal Binary Matrix的相关教程结束。