codeforce：800-900分段刷题总结
1.博弈论
Wallet Exchange
爱丽丝和鲍勃很无聊，于是他们决定用自己的钱包玩一个游戏。爱丽丝的钱包里有 a 枚硬币，而鲍勃的钱包里有 b 枚硬币。
双方轮流玩，由爱丽丝先走棋。在每个回合中，玩家将按顺序执行以下步骤：
- 选择与对手交换钱包，或保留现有钱包。
- 从玩家当前钱包中取出 1 个硬币。在执行此步骤之前，当前钱包中不能有 0 枚硬币。
无法在自己的回合中做出有效举动的玩家输。如果爱丽丝和鲍勃都以最佳方式下棋，则决定谁将赢得游戏。
分析
首先每个人必须取出 1 枚硬币，在取出硬币之前可以选择是否需要交换钱包，说明这种钱包的交换一定是有利于自己的。
那么我们可以忽略钱包的交换，直接看硬币总数。
因为爱丽丝先手，那么如果硬币总数为偶数，爱丽丝输，否则爱丽丝获胜。
从另一个角度说，只有硬币为0的时候，游戏才结束，说明我们更加应该关心硬币，而不是钱包的交换。
点击查看代码
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int _;
cin >> _;
while (_--) {
int a, b;
cin >> a >> b;
if ((a+b) & 1)
cout << "Alice" << endl;
else
cout << "Bob" << endl;
}
return 0;
}
Game with Integers
Vanya 和 Vova 正在玩一个游戏。游戏者得到一个整数 n 。轮到自己时，玩家可以在当前整数上加上 1 或减去 1 。玩家轮流下棋，万亚先下。如果万亚移动后整数能被 3 整除，那么他获胜。如果 10 步已过而万亚没有获胜，则沃瓦获胜。
请根据整数 n 编写一个程序，以确定在双方都下得最好的情况下谁会获胜。
分析
首先从整数n入手，如果n模3为0，先手必须移动，导致先手失败。
否则，如果n模3为1或2，都可以通过+1，-1的操作，使n模3为0。
用博弈论术语来讲，如果初始状态n%3==0，则此时为先手必败状态，除开此情况，其它情况都是先手必胜状态。
点击查看代码
#include <iostream>
using namespace std;
int main() {
int t, n;
cin >> t ;
while (t--) {
cin >> n;
if (n == 1) {
cout << "First" << endl;
continue;
}
if (!(n % 3)) {
cout << "Second" << endl;
continue;
} else {
cout << "First" << endl;
}
}
return 0;
}
Mahmoud and Ehab and the even-odd game
马哈茂德和埃哈布在玩一个叫偶数游戏的游戏。Ehab 选择他最喜欢的整数 n ，然后他们从 马哈茂德 开始轮流玩。
在每个玩家的回合中，他必须选择一个整数 a ，并从 n 中减去它，使得：
1 ≤ a ≤ n 。
如果轮到马哈茂德， a 必须是偶数，但如果轮到埃哈布， a 必须是奇数。
如果当前玩家无法选择任何满足条件的数字，那么他就输了。如果他们都以最佳方式下棋，你能确定胜负吗？
分析
如果n为偶数，那么可以直接选a=n，直接令n=0，获胜，否则的话，n为奇数，先手操作后必为奇数，同理得到后手获胜
点击查看代码
#include <iostream>
#include <string>
#include <cmath>
#include <algorithm>
typedef long long ll;
#define endl '\n';
using namespace std;
ll t[110];
int main() {
// int _;
// cin >> _;
// while (_--) {
//
// }
int n;
cin >> n;
if (n & 1) {
cout << "Ehab";
} else {
cout << "Mahmoud";
}
return 0;
}
Game With Sticks
在 2014 年国际奥林匹克运动会上摘金夺银后，阿克沙特和马尔维卡想找点乐子。现在，他们正在一个由 n 根水平棍和 m 根垂直棍组成的网格上玩游戏。
交点是网格上由一根水平木棒和一根垂直木棒的交点组成的任意一点。
游戏规则非常简单。玩家轮流移动。Akshat 赢得了金币，所以他先走一步棋。
在他/她移动的过程中，玩家必须选择任何剩余的交叉点，并从网格中移除所有经过此点的木棒。如果玩家无法移动(即在他/她移动时，网格上没有剩余的交叉点)，他/她将输掉游戏。
假设两位棋手都以最佳状态下棋。谁会赢得比赛？
分析
首先我们要考虑多种情况，
1.一条水平，一条竖直
2.一条水平（竖直），多条竖直（水平）
3.多条水平，多条竖直
第1，2种情况，我们只能移动一步，即先手必胜，
第3种情况，每移动一步，水平数-1，竖直数-1，最后会化为情况1，2（类似于化归，递归）
也就是说我们只用考虑1，2情况，然后把第3种情况用解决第1，2种情况的方法解决。
显然，一条水平（竖直）的时候，先手必胜，拓展一下，因为每一回合，水平和竖直木棒都-1，同时决定游戏结束的为数量最少的那一种木棒（水平或竖直），
那么数量较少的那个方向的木棒，如果为奇数，则先手必胜，否则，先手必败
点击查看代码
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int a[110000];
//vector<int>m;
int m = 1000000;
int main() {
int n, m;
cin >> n >> m;
int sum = min(m, n);
if (sum & 1) {
cout << "Akshat" << endl;
} else {
cout << "Malvika";
}
return 0;
}
这些题目告诉我们，可以从最简单的问题入手考虑，考虑什么是必败态，什么是必胜态，然后拓展到多种情况，值得注意的是，需要将问题情况考虑全面才不容易出错，否则代码就会因为遗漏情况二出错
————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
数论
Odd Divisor
给你一个整数 n 。请检查 n 是否有一个奇数除数(是否存在这样的数 x ( x > 1 )，即 n 能被 x 整除，且 x 是奇数)。
例如，如果有 n=6 ，那么就有 x=3 。如果是 n=4 ，则不存在这样的数。
分析
首先我们得想到
- 偶*偶=偶
- 偶*奇=偶
- 奇*奇=奇
如果数字 x 有奇数除数，那么它就有奇数质数除数。
如果 x 没有奇数除数，那么 x 就为2的幂，因为合数一定是素数的倍数嘛（类似于线性筛的原理），偶数中只有2为素数。
所以有奇数除数，必有奇数素数除数。
所以现在我们能得出结论，如果 x 为2的幂，则不存在，否则存在。
点击查看代码
#include <algorithm>
#include <iostream>
#include <vector>
#include <cmath>
#include <string>
using namespace std;
typedef long long ll;
int a[110000];
//vector<int>m;
int m = 1000000;
int main() {
int T;
cin >> T;
while (T--) {
ll n;
cin >> n;
if ((n & (n - 1)) == 0) {//注意运算符优先级
cout << "NO" << endl;
} else {
cout << "YES" << endl;
}
}
return 0;
}
/*
如果数字 n 是 2 的幂，那么它在二进制符号中只包含一个单位1。那么除了 n 中的单位所在的位置外，
(n−1)的所有位置都包含单位1。因此，它们的比特 "AND "(&)不包含单位1。
*/