2020-2021:teams:legal_string:组队训练比赛记录:contest12
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:组队训练比赛记录:contest12 [2021/08/13 12:59] 王智彪 |
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 | |
| ====== 题解 ====== | ====== 题解 ====== | ||
| 行 179: | 行 179: | ||
| </hidden> | </hidden> | ||
| - | 3.[[https://ac.nowcoder.com/acm/contest/11258/E|牛客第七场E]] | + | ===== E. xay loves nim ===== |
| ==== 题意 ==== | ==== 题意 ==== | ||
| - | 给了 $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}$ | ||
| ==== 题解 ==== | ==== 题解 ==== | ||
| 行 199: | 行 201: | ||
| 然后 $oi-wiki$ 上一段话刷新了我对 $FWT$ 的认知：若我们令 $i\&j$ 中 $1$ 的奇偶性为 $i$ 与 $j$ 的奇偶性，于是 $i$ 与 $k$ 的奇偶性异或 $j$ 与 $k$ 的奇偶性等于 $i$ ^ $j$ 与 $k$ 的奇偶性。然后可以得到异或的 $FWT$ ： $A_{i}=\sum_{C_{1}}A_{j}-\sum_{C_{2}}A_{j}$ ， $C_{1}$ 表示 $i\&j$ 的奇偶性为偶， $C_{2}$ 表示 $i\&j$ 的奇偶性为奇。（其实记住就行...） | 然后 $oi-wiki$ 上一段话刷新了我对 $FWT$ 的认知：若我们令 $i\&j$ 中 $1$ 的奇偶性为 $i$ 与 $j$ 的奇偶性，于是 $i$ 与 $k$ 的奇偶性异或 $j$ 与 $k$ 的奇偶性等于 $i$ ^ $j$ 与 $k$ 的奇偶性。然后可以得到异或的 $FWT$ ： $A_{i}=\sum_{C_{1}}A_{j}-\sum_{C_{2}}A_{j}$ ， $C_{1}$ 表示 $i\&j$ 的奇偶性为偶， $C_{2}$ 表示 $i\&j$ 的奇偶性为奇。（其实记住就行...） | ||
| - | 又因为 $sg$ 的范围有限，所以我们可以先预处理出每个数的二进制有多少位为 $1$ （或者直接 $__builtin_popcount$ 也可以）。 | + | 又因为 $sg$ 的范围有限，所以我们可以先预处理出每个数的二进制有多少位为 $1$ （或者直接 $\_\_builtin\_popcount$ 也可以）。 |
| 然后对于前缀和数组，就不能直接暴力加一了，判断两者与的奇偶性，如果为偶，则加一，不然减一。然后这样就直接把每一堆的 $FWT$ 数组给求完了，复杂度变成 $O(256n)$ ，而不是原来的 $O(2048n)$ ，再全乘起来求一个 $IFWT$ 就可以了，整个这部分的复杂度都是 $O(256n)$ 的，最后对于所有 $sg$ 值不为 $0$ 的结果都加起来就是答案了。 | 然后对于前缀和数组，就不能直接暴力加一了，判断两者与的奇偶性，如果为偶，则加一，不然减一。然后这样就直接把每一堆的 $FWT$ 数组给求完了，复杂度变成 $O(256n)$ ，而不是原来的 $O(2048n)$ ，再全乘起来求一个 $IFWT$ 就可以了，整个这部分的复杂度都是 $O(256n)$ 的，最后对于所有 $sg$ 值不为 $0$ 的结果都加起来就是答案了。 | ||
| 行 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.1628830753.txt.gz · 最后更改: 2021/08/13 12:59 由 王智彪
