#P1147. [CTSC2007]矩阵Matrix

    ID: 151 传统题 3000ms 256MiB 尝试: 42 已通过: 11 难度: 10 上传者: 标签>CF3100NOI/NOI+/CTS多轮协同舍入矩阵构造二分图建模广度优先搜索局部修复鸽巢原理等比数列求和

[CTSC2007]矩阵Matrix

[CTSC2007] 矩阵Matrix

题目描述

给定一个整数 DD,nn 行 mm 列的实数矩阵 AA,其第 ii 行第 jj 列的元素是 aija_{ij},且 0≤aij≤D0 \le a_{ij} \le D(1≤i≤n1 \le i \le n,1≤j≤m1 \le j \le m)。希望你能由此提供一个 nn 行 mm 列的 0101 矩阵 BB,第 ii 行 第 jj 列的元素是 bijb_{ij}(1≤i≤n1 \le i \le n,1≤j≤m1 \le j \le m),bijb_{ij} 非 00 即 11。

对于给定的 AA 矩阵和你提供的 BB 矩阵,可以求出

$$p_1=\max \begin{cases}\max\limits_{ 1 \le j \le m} \{ |\sum_{i=1}^n (b_{ij}-\frac{a_{ij}}{D})|\}\\\max\limits_{1 \le i \le n} \{ |\sum_{j=1}^m (b_{ij}-\frac{a_{ij}}{D})|\}\end{cases}$$$$p_2=\max_{1 \le i \le n,1 \le j \le m} \{|b_{i,j}+b_{i-1,j}+b_{i,j-1}+b_{i-1,j-1}-\frac{a_{i,j}+a_{i-1,j}+a_{i,j-1}+a_{i-1,j-1}}{D}|\}$$

在不同的测试例子中,我们希望提供的 BB 矩阵能使 p1p_1 或 p2p_2 尽量小。

输入格式

第一行有一个整数 cc,有两种取值:c=1c=1 表示我们的最小化目标是 p1p_1,c=2c=2 则表示希望 p2p_2 尽量小。

第二行有3个整数 DD,nn,mm,相邻的两个数字间用一个空格隔开,DD 的含义如上文所述,nn 和 mm 分别表示 AA 矩阵的行数和列数。

以下有 nn 行,每行 mm 个实数,描述 AA 矩阵。其中第 ii 行第 jj 列的实数表示 aija_{ij},相邻的数字用一个空格隔开。

输出格式

仅包含一个 nn 行 mm 列的 0101 矩阵 BB,表示你求出的使 pcp_c 尽量小的答案。其中第 ii 行第 jj 列的数字表示 bijb_{ij}。相邻的整数之间用一个空格隔开。

样例 #1

样例输入 #1

1
7 3 4
1 6 4 6
7 0 3 3
2 5 1 5

样例输出 #1

0 1 0 1
1 0 1 0
0 1 0 1

样例 #2

样例输入 #2

2
7 3 4
1 6 4 6
7 0 3 3
2 5 1 5

样例输出 #2

0 1 0 1
1 0 1 0
0 1 0 1

提示

对于 40%40\% 的数据,c=1c=1;

对于 60%60\% 的数据,c=2c=2;

对于 100%100\% 的数据,2≤n,m≤7002 \le n ,m \le 700,1≤D≤1091 \le D \le 10^9。

本站评测标准与公式修订

本站保留的原始特殊评测器 spj.cpp 采用以下判定,并非要求计算每个输入的全局最优值:

  • c=1 时,每行、每列的舍入误差绝对值均不超过1(数值比较容差为10^{-6})。
  • c=2 时,每个完整2乘2子矩阵的舍入误差绝对值不超过1.5(同样容差10^{-6})。因此原p2的下标范围应为 2≤i≤n,2≤j≤m2\le i\le n,2\le j\le m,不存在对第0行/列的访问。

原始评测器逐个用整数读取 aija_{ij};本站当前数据及评测接口中的A为整数矩阵,0≤aij≤D0\le a_{ij}\le D。输出的每个元素必须是0或1。