- [CTSC2007] 矩阵Matrix
洛谷 题面
- 2025-3-8 19:35:03 @
P5910 [CTSC2007] 矩阵Matrix 【征集 SPJ】
题目描述
给定一个整数 , 行 列的实数矩阵 ,其第 行第 列的元素是 ,且 (,)。希望你能由此提供一个 行 列的 矩阵 ,第 行 第 列的元素是 (,), 非 即 。
对于给定的 矩阵和你提供的 矩阵,可以求出
$$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}|\} $$在不同的测试例子中,我们希望提供的 矩阵能使 或 尽量小。
输入格式
第一行有一个整数 ,有两种取值: 表示我们的最小化目标是 , 则表示希望 尽量小。
第二行有3个整数 ,,,相邻的两个数字间用一个空格隔开, 的含义如上文所述, 和 分别表示 矩阵的行数和列数。
以下有 行,每行 个实数,描述 矩阵。其中第 行第 列的实数表示 ,相邻的数字用一个空格隔开。
输出格式
仅包含一个 行 列的 矩阵 ,表示你求出的使 尽量小的答案。其中第 行第 列的数字表示 。相邻的整数之间用一个空格隔开。
输入输出样例 #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
说明/提示
对于 的数据,;
对于 的数据,;
对于 的数据,,。
2 条评论
-
Han_Si_Ying LV 5 @ 2025-3-14 22:22:52
# P5910 [CTSC2007] 矩阵Matrix 【征集 SPJ】 ## 题目描述 给定一个整数 $D$,$n$ 行 $m$ 列的实数矩阵 $A$,其第 $i$ 行第 $j$ 列的元素是 $a_{ij}$,且 $0 \le a_{ij} \le D$($1 \le i \le n$,$1 \le j \le m$)。希望你能由此提供一个 $n$ 行 $m$ 列的 $01$ 矩阵 $B$,第 $i$ 行 第 $j$ 列的元素是 $b_{ij}$($1 \le i \le n$,$1 \le j \le m$),$b_{ij}$ 非 $0$ 即 $1$。 对于给定的 $A$ 矩阵和你提供的 $B$ 矩阵,可以求出 $$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}|\}$$ 在不同的测试例子中,我们希望提供的 $B$ 矩阵能使 $p_1$ 或 $p_2$ 尽量小。 ## 输入格式 第一行有一个整数 $c$,有两种取值:$c=1$ 表示我们的最小化目标是 $p_1$,$c=2$ 则表示希望 $p_2$ 尽量小。 第二行有3个整数 $D$,$n$,$m$,相邻的两个数字间用一个空格隔开,$D$ 的含义如上文所述,$n$ 和 $m$ 分别表示 $A$ 矩阵的行数和列数。 以下有 $n$ 行,每行 $m$ 个实数,描述 $A$ 矩阵。其中第 $i$ 行第 $j$ 列的实数表示 $a_{ij}$,相邻的数字用一个空格隔开。 ## 输出格式 仅包含一个 $n$ 行 $m$ 列的 $01$ 矩阵 $B$,表示你求出的使 $p_c$ 尽量小的答案。其中第 $i$ 行第 $j$ 列的数字表示 $b_{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\%$ 的数据,$c=1$; 对于 $60\%$ 的数据,$c=2$; 对于 $100\%$ 的数据,$2 \le n ,m \le 700$,$1 \le D \le 10^9$。
-
2025-3-12 11:32:12@
放个源码我好复制
- 1
信息
- ID
- 697
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 1
- 已通过
- 0
- 上传者