P5910 [CTSC2007] 矩阵Matrix 【征集 SPJ】

题目描述

给定一个整数 DDnnmm 列的实数矩阵 AA,其第 ii 行第 jj 列的元素是 aija_{ij},且 0aijD0 \le a_{ij} \le D1in1 \le i \le n1jm1 \le j \le m)。希望你能由此提供一个 nnmm 列的 0101 矩阵 BB,第 ii 行 第 jj 列的元素是 bijb_{ij}1in1 \le i \le n1jm1 \le j \le m),bijb_{ij}0011

对于给定的 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_1p2p_2 尽量小。

输入格式

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

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

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

输出格式

仅包含一个 nnmm 列的 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\% 的数据,2n,m7002 \le n ,m \le 7001D1091 \le D \le 10^9

2 条评论

  • @ 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
      上传者