题目描述
You are given four integers: $H, W, h$ and $w$. Determine whether there exists a matrix such that all of the following conditions are held, and construct one such matrix if the answer is positive:
- The matrix has $H$ rows and $W$ columns.
- Each element of the matrix is an integer between $-10^9$ and $10^9$ (inclusive).
- The sum of all the elements of the matrix is positive.
- The sum of all the elements within every subrectangle with $h$ rows and $w$ columns in the matrix is negative.
题意概述
构造一个$H \times W$的矩阵,使得这个矩阵中所有数字的和为正数,而其任意一个$h \times w$的子矩阵中所有数字的和为负数。
数据范围:$1 \le h \le H \le 500, \; 1 \le w \le W \le 500$。
算法分析
由于只要构造一个符合要求的矩阵,因此我们可以这么想:
在一个$(2h-1) \times (2w-1)$的矩阵中,如果其正中间的数为$-hwn+n-1$,其他所有数均为$n$,那么对于这个矩阵任意一个$h \times w$的子矩阵来说,其所有数字的和均为$-1$,而整个矩阵所有数字的和为正数。
根据贪心策略,$n$越大,整个矩阵所有数字的和也就越大(因为任意一个$h \times w$的子矩阵所有数字的和均为$-1$)。因为所有数字的绝对值都不能超过$10^9$,所以$n$应不超过$10^9/500/500=4000$。
若构造完矩阵后所有数字的和为负数,则不存在构造方案。
代码
#include <iostream> using namespace std; long long H, W, h, w, t, ans, a[501][501]; int main() { cin >> H >> W >> h >> w; for (int i = 1; i <= H; ++i) { for (int j = 1; j <= W; ++j) { a[i][j] = 4000; } } t = - h * w * 4000 + 3999; for (int i = 0; i <= H; i += h) { for (int j = 0; j <= W; j += w) { a[i][j] = t; } } for (int i = 1; i <= H; ++i) { for (int j = 1; j <= W; ++j) { ans += a[i][j]; } } if (ans < 0) { cout << "No" << endl; } else { cout << "Yes" << endl; for (int i = 1; i <= H; ++i) { for (int j = 1; j <= W; ++j) { cout << a[i][j] << ' '; } cout << endl; } } return 0; }