Nim石子游戏


Nim石子游戏

$\rm{Description}$

给定数列 $n_1, n_2, \cdots, n_k$,表示有 $k$ 堆物品,第 $i$ 堆物品的数量为 $n_i$。

两人轮流从中取物品,规则:每次可以从一堆中拿走任意正整数个物品。先拿走最后一根的人胜利。

对于给定的数列,判断先手是否必胜,若必胜,输出第一次应该在哪堆取多少物品。

$\rm{Solution}$

必胜必败分析

先手必胜,当且仅当 $n_1\oplus n_2\oplus\cdots\oplus n_k\neq 0$。

对于其他 nim游戏 ,假设状态表示为 $(a_1, a_2, \cdots,a_n)$,那么先手必胜,当且仅当 $\operatorname{sg}(a_1)\oplus \operatorname{sg}(a_2)\oplus\cdots\oplus \operatorname{sg}(a_n)$,证明BFS。

本题中 $\operatorname{sg}(i)=i$,所以有上面的结论。

证明

设 $s=n_1\oplus n_2\oplus\cdots\oplus n_k$.

也就是证明:

  1. 当 $s \neq 0$ 时,存在一种取法,使得 $s=0$.
  2. 当 $s=0$ 时,无论怎么取物品,$s$ 都不等于 $0$.

命题一

因为 $s\neq 0$,根据异或的定义,存在一堆物品 $i$,满足 $n_i\oplus s

此时,$s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_k\oplus s=s\oplus s=0$.

所以命题一成立。

命题二

反证法。若否,则 $s=0$ 时,存在一种取物品的方法使得 $s_{\rm{new}}=0$.

设取走第 $i$ 堆的若干物品,第 $i$ 堆剩余 $n_i’$ 个物品。

所以 $s_{\rm{new}}=n_1\oplus n_2\cdots\oplus n_i’\oplus\cdots\oplus n_k=0=s$.

把 $s$ 的定义式代入,得到 $n_i=n_i’$,产生矛盾。

所以命题二成立。

找方案的方法

利用命题一。找到一堆 $i$,满足 $n_i\oplus s < n_i$,将这一堆拿走 $n_i-(n_i\oplus s)$ 个物品,使得新的异或和为 $0$,满足题意。

$\rm{Code}$

#include <bits/stdc++.h>

using namespace std;
const int MAXN = 1000008;
int T, n;
int a[MAXN];
int main() {
    scanf("%d", &n);
    int res = 0;
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        res ^= a[i];
    }
    if(res == 0) {
        cout << "lose" << endl;
    } else {
    	for(int i = 1; i <= n; i++) {
    		if((res ^ a[i]) < a[i]) {
    			cout << a[i] - (res ^ a[i]) << " " << i << endl;
    			a[i] = res ^ a[i];
    			break;
    		}
    	}
    	for(int i = 1; i <= n; i++) {
    		cout << a[i] << " ";
    	}
    	cout << endl;
    }
    return 0;
}

 

暂无评论

发送评论 编辑评论

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