Codechef March Challenge 2021 Div2 Consecutive Adding(CONSADD)
Codechef March Challenge 2021 Div2 Consecutive Adding(CONSADD)
题目大意:
给定两个 \(n\times m\) 矩阵 \(A\) , \(B\) 和一个常数 \(x\)
现在对于 \(A\) 操作,每次可以选择一行或者一列连续的 \(x\) 个,一起改变同一个数值 \(v\in \Z\)
判断是否可以由 \(A\) 变成 \(B\)
显然可以先将 \(A,B\) 作差,转化为操作成0矩阵
进一步,我们将 \(A\) 矩阵行内差分,使得每次行操作变为一个单点 \(A_{i,j}+v\) ,一个单点 \(A_{i,j+x}-v\)
在此基础上,继续差分即可将行列操作都转化为单点操作
此时容易发现, \(A_{i,j}\) 的数值有关联的部分都是 \(A_{i,j},A_{i+x,j},A_{i,j+x}\cdots A_{i+ax,j+bx}\)
也就是相差 \(x\) 的,考虑可以将这一部分子矩形提取出来,这样问题变成了
每次操作一个数 \(A_{i,j}+v\) ,可以选择相邻一个数 \(A_{i,j+1}\) 或 \(A_{i+1,j}\) 去 \(-v\)
对于每个这样的子问题,容易发现有解的充要条件:子矩阵元素和为0
(可以依次考虑每个元素贪心构造方案)
如此可以 \(O(nm)\) 判定
1 |
|