Luogu – P2148 – [SDOI2009]E&D

$\rm{Description}$

有 $2n$ 堆石子,编号分别为 $1, 2, \cdots, 2n$。将第 $2k-1$ 和 $2k$ 堆 $(1\leq k\leq n)$,归为同一组。第 $i$ 堆石子的个数是正整数 $s_i$.

定义分割操作:

  1. 任取一堆石子,不妨为第 $i$ 堆,将其全移走;
  2. 从和第 $i$ 堆同一组的石子中,取出若干正整数个石子,放到第 $i$ 堆的位置上。操作后,两堆石子数都要大于 $0$。

给定状态,问先手是否有必胜策略。

$n\leq 2\times 10^4, 1\leq s_i\leq 2\times 10^9$.

$\rm{Solution}$

https://www.luogu.com.cn/blog/Sooke/solution-p2148

定义

$f(x)$ 为 $x$ 的二进制末尾首个 $0$ 的出现位置(标号从 $0$ 开始)。比如 $f(5)=(101)_2=1$.

$\operatorname{sg}(x, y)$ 为一组分别有 $x+1, y+1$ 个石子的 $\operatorname{sg}$ 值。

$S_z$ 表示满足 $x+y+1=z$ 的 $\operatorname{sg}(x, y)$ 构成的自然数集合。$s_0=\emptyset$.

引理

  1. 终止局面的 $\operatorname{sg}$ 值为 $0$,即 $\operatorname{sg}(0, 0)=0$.
  2. $\operatorname{sg}(x, y)=mex($ 所有后继的 $\operatorname{sg}$ 值 $)=mex(S_x\cup s_y)$.

结论

  1. $S_z$ 等同于 $z$ 二进制下 $1$ 的位置集合。比如 $s_5=(101)_2={0, 2}$.
  2. $\operatorname{sg}(x, y)=f(x\mid y)$. 比如 $sg(1, 4)=f(5)=1$.

证明

考虑归纳证明。逐步放大 $z$,证明对于任意的 $z$,结论 $1$ 成立,且对于任意的 $x+y=z$,结论 $2$ 成立。

根据引理 $1$,结论 $2$ 在 $z=0$ 时正确。

假设已经证明结论 $2$ 在 $z-1$ 正确,考虑 $S_z$ 包含元素 $p$ 的条件。

由 $S_z$ 的定义,需要 $x+y=z-1$,由结论 $2$,需要 $f(x\mid y)=p$.

因此,$(x\mid y)$ 的二进制第 $p$ 位是 $0$,$0\sim p-1$ 位都是 $1$. 所以 $x+y$ 的 $0\sim p-1$ 位都是 $1$,第 $p$ 位是 $0$.

又因为 $x+y+1=z$,所以当包含元素 $p$ 时,无论如何,二进制下 $z$ 的第 $p$ 位总为 $1$.

所以,当且仅当 $z$ 的二进制第 $p$ 位为 $1$ 时,$S_z$ 包含元素 $p$,结论 $1$ 得证。

因为结论 $1$ 成立,所以 $\operatorname{sg}(x, y)=mex(S_x\cup S_y)=mex(S_{x\mid y})$.

又因为 $x\mid y\leq x+y=z$ 在已经证明的 $z$ 的范围内,根据 $S$ 和 $f$ 的定义,显然 $mex(S_{x\mid y})=f(x\mid y)$.

故结论 $1, 2$ 得证。

解法

根据上述结论,$\operatorname{sg}(x, y)=f(x\mid y)$,可以快速地求出每组的 $sg$ 值。将所有组的 $\operatorname{sg}$ 值异或起来,即可判断是否必胜。

$\rm{Code}$

#include<bits/stdc++.h>
using namespace std;
int T, n;
int lowzero(int x){
    for (int i = 0;; i++, x >>= 1) {
        if (!(x & 1)) return i;
    }
}
int main() {
	scanf("%d", &T);
	while(T--) {
        int ans = 0;
        scanf("%d", &n); n >>= 1;
        while(n--) {
            int x, y;
            scanf("%d%d", &x, &y);
            ans ^= lowzero((x - 1) | (y - 1));
        }
        if(ans) printf("YES\n");
        else printf("NO\n");
    }
    return 0;
}
暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇
window.pjaxLoaded = function(){ } window.pjaxLoaded();