hexo-blog/source/_posts/oi/rectangle.md

---

title: +/- Rectangle tags:

• Constructive Algorithm
• Greedy id: "621" categories:
• - OI
  • Common Skill date: 2017-06-23 12:55:22 ---

题目描述

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;
}