891. Nim游戏
游戏 NIM
2023-09-27 14:27:31 时间
title: 891. Nim游戏
tags:
- Acwing
- 每日一题
- 博弈论
categories: - 2023大四下学期
toc: true
quicklink: true
math: true
sidebar: true
copyright: true
reward: true
date: 2023-03-21 10:05:07
{% note info %}
摘要
Title: 891. Nim游戏
Tag: 博弈论
Memory Limit: 64 MB
Time Limit: 1000 ms
{% endnote %}
Powered by:NEFU AB-IN
文章目录
891. Nim游戏
-
题意
给定 n堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。 -
思路
- 终止状态,也就是必败态,是 a 1 ⊕ a 2 . . . ⊕ a n = 0 a_1 \oplus a_2 ...\oplus a_n= 0 a1⊕a2...⊕an=0
- 如果当前异或值不是0,那么一定可以通过某种方式,使得拿完之后的异或值变成0
- 即拿 a i − ( x ⊕ a i ) a_i-(x \oplus a_i) ai−(x⊕ai)个, x = a 1 ⊕ a 2 . . . ⊕ a n x = a_1 \oplus a_2 ... \oplus a_n x=a1⊕a2...⊕an,这样那一堆石子就剩 x ⊕ a i x \oplus a_i x⊕ai个,这样所有的异或值就为0了
- 为什么
x
⊕
a
i
x \oplus a_i
x⊕ai一定小于x呢?
- 一定存在一个 a i a_i ai使得满足 x ⊕ a i x \oplus a_i x⊕ai小于 a i a_i ai
- 假设:x(用二进制表示)最高位是第 k k k位,此时只需要找一个第 k k k位同样为 1 1 1的 a i a_i ai即可,这样他俩异或后,第 k k k位一定变成0,一定会比 a i a_i ai小,这样找到的 a i a_i ai一定满足上述条件
- 如果当前的异或值是0,那么不管怎么拿,拿完之后的异或值一定不是0
-
代码
''' Author: NEFU AB-IN Date: 2023-03-21 10:19:25 FilePath: \Acwing\891\891.py LastEditTime: 2023-03-21 10:22:32 ''' read = lambda: map(int, input().split()) from collections import Counter, deque from heapq import heappop, heappush from itertools import permutations N = int(1e3 + 10) INF = int(2e9) n = int(input()) lst = list(read()) res = 0 for i in lst: res ^= i print("Yes" if res != 0 else "No")
相关文章
- 单款游戏收入第二、多款游戏进入增长榜,三七互娱出海再上新台阶
- Python游戏开发:pygame游戏开发常用数据结构
- 游戏用户该如何选择公有云
- 台球游戏的核心算法和AI(2)
- 学海无涯!java怎么开发游戏,Java校招面试指南
- Windows 10总是自动安装游戏,怎么解决?
- 【Rust】猜数字游戏
- 《R语言游戏数据分析与挖掘》一3.3 高级绘图函数
- leetcode292. Nim 游戏
- 892. 台阶-Nim游戏
- 最新游戏陪玩语音聊天系统源码+视频搭建教程
- 巧用 ARKit 和 SpriteKit 从零开始做 AR 游戏
- 使用C++和Directx开发游戏GUI(四)
- AcWing 894. 拆分-Nim游戏
- AcWing 893. 集合-Nim游戏
- AcWing 892. 台阶-Nim游戏
- 微信小游戏开发怎么选游戏引擎
- unityRPG游戏攻击的判定
- 复习java逻辑---实现猜数字游戏