2020-2021:teams:legal_string:组队训练比赛记录:contest12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest12 [2021/08/13 13:00] 王智彪 |
2020-2021:teams:legal_string:组队训练比赛记录:contest12 [2021/08/14 10:56] (当前版本) lgwza [补题情况] |
||
|---|---|---|---|
| 行 8: | 行 8: | ||
| | C | 0 | 0 | 0 | | | C | 0 | 0 | 0 | | ||
| | D | 0 | 0 | 0 | | | D | 0 | 0 | 0 | | ||
| - | | E | 0 | 0 | 2 | | + | | E | 1 | 0 | 2 | |
| | G | 0 | 0 | 0 | | | G | 0 | 0 | 0 | | ||
| | J | 2 | 2 | 0 | | | J | 2 | 2 | 0 | | ||
| - | | K | 2 | 0 | 0 | | + | | K | 2 | 1 | 0 | |
| ====== 题解 ====== | ====== 题解 ====== | ||
| 行 183: | 行 183: | ||
| ==== 题意 ==== | ==== 题意 ==== | ||
| - | 给了 $n$ 堆石子和 $m$ 个可以取走的石子的数量，除了这 $m$ 种石子，还可以取莫比乌斯函数值为 $1$ 的数量石子。同时给出这 $n$ 堆石子的数量范围 $[l_{i},r_{i}]$ ，求所有的情况中，先手必胜的局数，局面不同当且仅当存在一堆石子在两个局面中数量不同。 | + | 给了 $n$ 堆石子和 $m$ 个可以取走的石子的数量，记为 $x_{i}$ ，除了这 $m$ 种石子，还可以取莫比乌斯函数值为 $1$ 的数量石子。同时给出这 $n$ 堆石子的数量范围 $[l_{i},r_{i}]$ ，求所有的情况中，先手必胜的局数，局面不同当且仅当存在一堆石子在两个局面中数量不同。 |
| + | |||
| + | $1≤n≤10^{6},1≤l_{i},r_{i}≤10^{5},1≤m≤5,1≤x_{i}≤10^{5}$ | ||
| ==== 题解 ==== | ==== 题解 ==== | ||
| 行 434: | 行 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.1628830819.txt.gz · 最后更改: 2021/08/13 13:00 由 王智彪
