当前位置: 首页> 汽车> 车展 > 莆田seo_简阳seo排名优化培训_线上电商怎么做_专业推广引流团队

莆田seo_简阳seo排名优化培训_线上电商怎么做_专业推广引流团队

时间:2025/8/12 0:54:01来源:https://blog.csdn.net/sin1810335764/article/details/142185241 浏览次数: 0次
莆田seo_简阳seo排名优化培训_线上电商怎么做_专业推广引流团队

Nim游戏

重点结论:对于一个Nim游戏的局面(a1,a2,...,an),它是P-position当且仅当a1^a2^...^an=0,其中^表示位异或(xor)运算。

(本篇只做简单的结论描述,详细证明过程请看这篇博客)

Nim和

 堆物品,每堆 ai 个,两个玩家轮流取走任意一堆的任意个物品,但不能不取,取走最后一个物品的人获胜。

结论:

定义 Nim 和 =ai⊕a2⊕⋯an

当且仅当 Nim 和为 0 时,先手必败,反则先手必胜。

简单证明:

三个定理

  1. 没有后继状态的状态是必败状态。
  2. 一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
  3. 一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。

例题:

一.P2197 【模板】Nim 游戏

 题目思路:Nim游戏的板子题,可以直接套出结论,Nim 和 =ai⊕a2⊕⋯an当且仅当 Nim 和为 0 时,先手必败,反则先手必胜。

 代码实现:

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
typedef long long ll;
ll a, b, c, n, m, t;
ll f[N], dp[N];
ll ans;
int main() 
{cin >> t;while (t--) {ans = 0;cin >> n;for (int i = 1; i <= n; i++){cin >> f[i];ans = ans ^ f[i];}if (ans) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

 

二.P1247 取火柴游戏

 

思路:

本题和Nim板子题很像,但是,多了一个输出先手必赢的第一次操作,及其结果.先手必胜,即先手可以拿走一些火柴,使得后手必败,而必败态是火柴堆的异或和为零;那么我们求的,就是先手拿走一些火柴后,新的火柴堆异或和为零的方案.

代码实现:

#include<bits/stdc++.h>
using namespace std;
#define N 2000005
typedef long long ll;
ll n, m, t, a, b, c;
ll f[N], dp[N];
ll ans, maxx, minn = 1e9;
int main()
{cin >> n;for (int i = 1; i <= n; i++) cin >> f[i];for (int i = 1; i <= n; i++) {ans = ans ^ f[i];}if (ans) {for (int i = 1; i <= n; i++) {if ((ans ^ f[i]) >= f[i]) continue;cout << (f[i] - (ans ^ f[i])) << " " << i << endl;f[i] =ans ^ f[i];break;}for (int i = 1; i <= n; i++)cout << f[i] << " ";cout << endl;}else {cout << "lose" << endl;}return 0;
}

 

三.P7589 黑白棋(2021 CoE-II B)

题目思路:

一个 nim 游戏,双方还可以选择每次给每堆石子 +d 个,每人可以添加 k 次。问先手能否获胜。发现一旦先手必胜,后手每添加 d 个,先手都可以选择减少 d 个,而添加次数有限,所以先手必胜。后手同理。

代码实现:

#include<bits/stdc++.h>
using namespace std;
#define N 2000005
typedef long long ll;
ll n, m, t, a, b, c, k, d;
ll f[N], dp[N];
ll ans, maxx, minn = 1e9;
int main()
{cin >> t;while (t--) {ans = 0;cin >> n >> k >> d;for (int i = 1; i <= n; i++) {cin >> a >> b >> c;ans ^= abs(b - c) - 1;}if (ans) cout << "Yes" << endl;else cout << "No" << endl;}return 0;
}

 

关键字:莆田seo_简阳seo排名优化培训_线上电商怎么做_专业推广引流团队

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: