前言
模拟赛原题。。
好好一道送分被我硬打成爆蛋。。
(sf{Solution})
看了一波数据范围，感觉能 dfs 骗分。
骗成正解了。
大概就是将这个 (n imes 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<<"
")
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<<"
")
for(int j=1;j<=n;++j)
cout<<m[i][j]<<" ";
else cout<<"-1";
return 0;
}