2020-2021:teams:wangzai_milk:cf2100-2800泛做1
| 两侧同时换到之前的修订记录 前一修订版 | |||
|
2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/05 15:23] zars19 |
2020-2021:teams:wangzai_milk:cf2100-2800泛做1 [2020/08/05 15:24] (当前版本) zars19 [1332E - Height All the Same] |
||
|---|---|---|---|
| 行 656: | 行 656: | ||
| * 当 $n\times m$ 为奇数时，必然是偶数个奇数奇数个偶数/偶数个偶数奇数个奇数，答案是总数 $\mathrm{total}=(r-l+1)^{nm}$ 。 | * 当 $n\times m$ 为奇数时，必然是偶数个奇数奇数个偶数/偶数个偶数奇数个奇数，答案是总数 $\mathrm{total}=(r-l+1)^{nm}$ 。 | ||
| - | |||
| * 当 $n\times m$ 为偶数时，奇偶都是偶数个可以，奇偶都是奇数个不行。pikmike提供了一个直觉法： | * 当 $n\times m$ 为偶数时，奇偶都是偶数个可以，奇偶都是奇数个不行。pikmike提供了一个直觉法： | ||
| - | - 当 $r-l+1$ 为偶数时，答案是 $\frac{\mathrm{total}}2$ | + | |
| - | - 当 $r-l+1$ 为奇数时，可行将会比不可行多 $1$ 。这是因为 $[l,r]$ 中必定有 $k\in[l,r]且 k\oplus1\notin[l,r]$ 。每一种方案，我们可以选第一个不为 $k$ 的位置给 $a_{i,j}$ 异或 $1$ ，这样可以使可行方案与不可行方案两两配对，除了全部为 $k$ 的一个方案可行。答案 $\frac{\mathrm{total}+1}{2}$ | + | * 当 $r-l+1$ 为偶数时，答案是 $\frac{\mathrm{total}}2$ |
| + | * 当 $r-l+1$ 为奇数时，可行将会比不可行多 $1$ 。这是因为 $[l,r]$ 中必定有 $k\in[l,r]且 k\oplus1\notin[l,r]$ 。每一种方案，我们可以选第一个不为 $k$ 的位置给 $a_{i,j}$ 异或 $1$ ，这样可以使可行方案与不可行方案两两配对，除了全部为 $k$ 的一个方案可行。答案 $\frac{\mathrm{total}+1}{2}$ | ||
| <hidden><code cpp> | <hidden><code cpp> | ||
2020-2021/teams/wangzai_milk/cf2100-2800泛做1.1596612224.txt.gz · 最后更改: 2020/08/05 15:23 由 zars19
