2020-2021:teams:legal_string:jxm2001:contest:cf_mar21
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:legal_string:jxm2001:contest:cf_mar21 [2021/03/29 18:39] jxm2001 创建 |
2020-2021:teams:legal_string:jxm2001:contest:cf_mar21 [2021/03/29 21:22] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 43: | 行 43: | ||
| } | } | ||
| enter(ans); | enter(ans); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| + | </code> | ||
| + | </hidden> | ||
| + | |||
| + | ===== Consecutive Adding ===== | ||
| + | |||
| + | ==== 题意 ==== | ||
| + | |||
| + | 给定两个 $r\times c$ 的矩阵 $A$ 和 $B$，每次操作可以选择 $A$ 中某行或某列中连续的 $x$ 个元素同时加上 $v$。 | ||
| + | |||
| + | 问能否经过有限次操作将 $A$ 转化为 $B$。 | ||
| + | |||
| + | ==== 题解 ==== | ||
| + | |||
| + | 首先我们证明题目所给操作与以下两种操作等效： | ||
| + | |||
| + | - $a_i+=v,a_{i+x}-=v$ | ||
| + | - 仅对原矩阵左上角 $x\times x$ 的矩阵进行原操作 | ||
| + | |||
| + | 首先不难发现可以通过题目原操作得到操作 $1$ 和操作 $2$。接下来考虑怎么用操作 $1$ 和操作 $2$ 得到原操作。 | ||
| + | |||
| + | 假设原操作是对某行中连续的元素加上 $v$，则可以先通过操作 $1$ 对该行前 $x$ 个元素加上 $v$，再通过操作 $2$ 转移到对应位置。 | ||
| + | |||
| + | 然后不难发现操作顺序与结果无关，于是不妨假设先只进行操作 $2$，然后再进行操作 $1$。 | ||
| + | |||
| + | 因为之后只能进行操作 $1$，于是必须先通过操作 $2$ 将除左上角 $x\times x$ 的矩阵以外的位置全部变成 $0$。 | ||
| + | |||
| + | 接下来只考虑 $x\times x$ 的矩阵，将行操作和列操作视为 $2n$ 的结点，$a_{i,j}$ 相当于在行操作的第 $i$ 个结点和列操作的第 $j$ 个结点连一条权值 $a_{i,j}$ 的边。 | ||
| + | |||
| + | 于是最终只需要保证每条边的两个端点的数值和等于该边的权值即可。 | ||
| + | |||
| + | 另外我们发现如果存在合法解，可以对每个行操作加上 $v$，每个列操作减去 $v$ 仍然是合法解。 | ||
| + | |||
| + | 于是我们不妨假设行操作的第一个结点对应的值为 $0$，然后跑一遍 $\text{dfs}$ 即可。时间复杂度 $O(rc+x^2)$。 | ||
| + | |||
| + | <hidden 查看代码> | ||
| + | <code cpp> | ||
| + | const int MAXN=1e3+5; | ||
| + | LL a[MAXN][MAXN],s[2][MAXN]; | ||
| + | bool vis[2][MAXN]; | ||
| + | int x; | ||
| + | bool dfs(int t,int p,LL v){ | ||
| + | if(vis[t][p]) | ||
| + | return s[t][p]==v; | ||
| + | vis[t][p]=true; | ||
| + | s[t][p]=v; | ||
| + | bool flag=true; | ||
| + | _for(i,0,x){ | ||
| + | if(t==0) | ||
| + | flag&=dfs(!t,i,a[p][i]-v); | ||
| + | else | ||
| + | flag&=dfs(!t,i,a[i][p]-v); | ||
| + | } | ||
| + | return flag; | ||
| + | } | ||
| + | int main() | ||
| + | { | ||
| + | int T=read_int(); | ||
| + | while(T--){ | ||
| + | int r=read_int(),c=read_int(); | ||
| + | x=read_int(); | ||
| + | _for(i,0,x)_for(j,0,x)a[i][j]=0; | ||
| + | _for(i,0,r)_for(j,0,c)a[i%x][j%x]+=read_int(); | ||
| + | _for(i,0,r)_for(j,0,c)a[i%x][j%x]-=read_int(); | ||
| + | _for(i,0,x)s[0][i]=s[1][i]=0,vis[0][i]=vis[1][i]=false; | ||
| + | if(dfs(0,0,0)) | ||
| + | puts("YES"); | ||
| + | else | ||
| + | puts("NO"); | ||
| } | } | ||
| return 0; | return 0; | ||
2020-2021/teams/legal_string/jxm2001/contest/cf_mar21.1617014348.txt.gz · 最后更改: 2021/03/29 18:39 由 jxm2001
