题意:
输入:
四个正整数n,m,a,b
问是否能在n行m列的值全为零列表中填充数1使得:
1.对于每一行严格满足1的个数为a
2.对于每一列严格满足1的个数为b
输出:
若满足条件矩阵存在输入"YES\n"以及填充后的矩阵
若不存在则输出"NO\n"
这是一道思维题!!!!!
在二维列表中我们一般要关心行列的关系
此题中因为因为每一行都有a个1,每一列都有b个1。
有m行,n列。那么矩阵中1的总个数为a*n == b*m
如若不满足该等式则不可能构造出相应矩阵。
那么接下来我们如何构造矩阵呢?
同样对于等式a*n==b*m 我们对其进行移动
a*n/m == b这意味着在对每一行填充a个1后总填充的个数一定是列m的倍数!!
这意味着什么呢?
如果给我们1m的一维列表,a\n/m==b则意味着我们对这一行列表从头开始填充
遇到末尾就回到开头这样反复填充a*n/m次,最终一定会在末尾结束!且每一格都被
填充了b次。
这样就简单了,对于原题n*m列表,从第一行第一列开始向右填充,填充到a个1时停止,
如果到末尾,就回到开头。下一行紧接着上一行的列开始填充。
这样由我们之前的分析每一列都会有b个1!!
下面代码:
#include<iostream>; #include<algorithm>; using namespace std; int res[55][55]; int main() { ios::sync_with_stdio(0); int t;cin >> t;int n, m, a, b; while (t--) { cin >> n >> m >> a >> b; if (n * a != m * b) { cout << "NO\n";continue; } cout << "YES\n"; memset(res, 0, sizeof(res)); int i = 1;int j = 1; for (i = 1;i <= n;i++) { for (int row = a;row > 0;row--) { res[i][j] = 1;j++; if (j > m)j = 1; } }for (i = 1;i <= n;i++) { for (j = 1;j <= m;j++) cout << res[i][j]; cout << "\n"; } } }