2020-2021:teams:legal_string:组队训练比赛记录:contest12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest12 [2021/08/13 14:54] jxm2001 |
2020-2021:teams:legal_string:组队训练比赛记录:contest12 [2021/08/14 10:56] (当前版本) lgwza [补题情况] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| | G | 0 | 0 | 0 | | | G | 0 | 0 | 0 | | ||
| | J | 2 | 2 | 0 | | | J | 2 | 2 | 0 | | ||
| - | | K | 2 | 0 | 0 | | + | | K | 2 | 1 | 0 | |
| ====== 题解 ====== | ====== 题解 ====== | ||
| 行 436: | 行 436: | ||
| 对每次询问的 $a[l\sim r]$，令 $a_{l-1}=0,a_{r+1}=0$，设 $b_i=a_i-a_{i-1}(l\le i\le r+1)$。 | 对每次询问的 $a[l\sim r]$，令 $a_{l-1}=0,a_{r+1}=0$，设 $b_i=a_i-a_{i-1}(l\le i\le r+1)$。 | ||
| - | 于是每次操作等价于选取一对 $l\le i,j\le r+1$，$b_i\equiv b_i+1\bmod k,b_j\equiv b_j+1\bmod k$。 | + | 于是每次操作等价于选取一对 $l\le i,j\le r+1$，$b_i\equiv b_i+1\bmod k,b_j\equiv b_j-1\bmod k$。 |
| 同时，$\sum_{i=l}^{r+1} b_i=a_{r+1}-a_{l-1}=0$，最终目标是将 $b_i$ 全部变为 $0$。在不考虑取模的情况下，最小费用显然为 $\cfrac {\sum_{i=l}^{r+1}|b_i|}2$。 | 同时，$\sum_{i=l}^{r+1} b_i=a_{r+1}-a_{l-1}=0$，最终目标是将 $b_i$ 全部变为 $0$。在不考虑取模的情况下，最小费用显然为 $\cfrac {\sum_{i=l}^{r+1}|b_i|}2$。 | ||
2020-2021/teams/legal_string/组队训练比赛记录/contest12.1628837686.txt.gz · 最后更改: 2021/08/13 14:54 由 jxm2001
