手机网站改版,ui设计做app网站要学什么,gps建站教程视频,外贸网站建设网公平组合游戏#xff08;ICG) 满足一下几个特征#xff1a; 1.两名玩家交替行动。 2.在游戏进程的任意时刻#xff0c;可以执行的合法行动与轮到哪名玩家无关。 3.不能行动的玩家判为失败 如果满足以上特征#xff0c;那么就是一个公平组合游戏 另一种游戏叫做有向图游戏ICG) 满足一下几个特征 1.两名玩家交替行动。 2.在游戏进程的任意时刻可以执行的合法行动与轮到哪名玩家无关。 3.不能行动的玩家判为失败 如果满足以上特征那么就是一个公平组合游戏 另一种游戏叫做有向图游戏 给定一个有向无环图图中有一个唯一的起点在起点上放有一枚棋子两名玩家交替的把这枚棋子沿有向边进行移动每次可以一定一步最终无法移动的人判为失败
其中Nim游戏属于公平组合游戏
AcWing.891.Nim游戏 给定 n n n 堆石子两位玩家轮流操作每次操作可以从任意一堆石子中拿走任意数量的石子可以拿完但不能不拿最后无法进行操作的人视为失败。
问如果两人都采用最优策略先手是否必胜。
输入格式 第一行包含整数 n n n。 第二行包含 n n n 个数字其中第 i i i 个数字表示第 i i i 堆石子的数量。
输出格式 如果先手方必胜则输出 Yes。否则输出 No。
数据范围 1 ≤ n ≤ 1 0 5 , 1 ≤ 每堆石子数 ≤ 1 0 9 1≤n≤10^{5},1≤每堆石子数≤10^{9} 1≤n≤105,1≤每堆石子数≤109
输入样例
2
2 3输出样例
Yes先手必败状态是指遇到了无法操作的情况必然会输掉游戏。 先手必胜状态是指当我们进行完了这一步操作之后对手一定会陷入必败状态
结论 如果n堆的数量为 a 1 , a 2 , . . . . . . , a n a_{1},a_{2},......,a_{n} a1,a2,......,an那么 使得 a a a1 ^ a a a2 ^… a a an 如果结果为0那么先手必败如果不为0那么先手必胜
证明过程详见AcWing算法基础课数学知识四1:11:00
代码
#includeiostream
using namespace std;int main() {int n; cin n;int res 0;while (n--) {int x; cin x;res ^ x;}if (res)cout Yes;else cout No;return 0;
}AcWing.892.台阶-Nim游戏 现在有一个 n n n 级台阶的楼梯每级台阶上都有若干个石子其中第 i i i 级台阶上有 a i a_{i} ai 个石子 ( i ≥ 1 ) (i≥1) (i≥1)。
两位玩家轮流操作每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中不能不拿。
已经拿到地面上的石子不能再拿最后无法进行操作的人视为失败。
问如果两人都采用最优策略先手是否必胜。
输入格式 第一行包含整数 n n n。
第二行包含 n n n 个整数其中第 i i i 个整数表示第 i i i 级台阶上的石子数 a i a_{i} ai。
输出格式 如果先手方必胜则输出 Yes。 否则输出 No。
数据范围 1 ≤ n ≤ 105 , 1≤n≤105, 1≤n≤105, 1 ≤ a i ≤ 109 1≤ai≤109 1≤ai≤109
输入样例
3
2 1 3输出样例
Yes过于抽象可以参照详情 详细过程AcWing算法基础课习题课week7——18:00
在分析中我们可得知保证最优解且先手必胜的前提为能够保证每次先手操作前的时候看到的都是奇数级台阶的石子数一定是有不同的也就是在操作后对手看到的奇数级台阶的石子数都是相同的这样可以保证先手必胜。
故我们只需要求出奇数级台阶的石子数量的抑或值如果为0那么就必败如果不为0那么必胜。
#includeiostream
using namespace std;int main() {int n; int res 0;cin n;for (int i 1; i n; i) {int x; cin x;if (i % 2)res ^ x;}if (res)puts(Yes);else puts(No);return 0;
}—————————————————————————————————————————————————
接下来是SG函数
定义Mex运算为找到一个集合里面最小的不存在的自然数
从一个局面可以通过不同的操作衍生出很多其他的局面比如果从一堆石子中拿一个会走向一种局面拿两个就是另一种局面以此类推 对于SG函数我们首先把终点状态的SG函数值定义为0 对于过程中任意一个局面假如现在处于 x x x局面且 x x x局面可以衍生出 y 1 , y 2 , y 3 . . . y k y_{1},y_{2},y_{3}...y_{k} y1,y2,y3...yk等局面那么在 x x x局面的SG函数值就等于 SG( x x x) Mex{ SG( y y y1), SG( y y y2), SG( y y y3)…SG( y y yk) }。
比如说有一个局面指向且仅指向终点那么他的SG函数值就只能为 1 1 1
最终对于一系列局面起点的SG(x) 0时就是必败SG(x) ≠ 0时就是必胜
因为如果先手保证了当前SG值不为0那么就是一定是可以到达0的也就是说在双方绝顶聪明的前提下一定能使得对手处于SG值等于0的局面相反如果先手的SG值等于0那么就会让对手使得自己最终处于SG值等于0的局面
而且应用SG函数时我们都会有多个图需要考虑也就是说先手会从多个图里面选如果所有的图都无法胜利那么就导致最终的失败但是如果有一个图可以胜利那么就可以导致最终胜利
在多个图的情形下只需要把多个图的SG的起点的值抑或起来就可以如果最终得到结果是0那么必败如果不为0那么必胜
AcWing.893.集合-Nim游戏 给定 n n n 堆石子以及一个由 k k k 个不同正整数构成的数字集合 S S S。
现在有两位玩家轮流操作每次操作可以从任意一堆石子中拿取石子每次拿取的石子数量必须包含于集合 S S S 最后无法进行操作的人视为失败。
问如果两人都采用最优策略先手是否必胜。
输入格式 第一行包含整数 k k k表示数字集合 S 中数字的个数。 第二行包含 k k k 个整数其中第 i i i 个整数表示数字集合 S S S 中的第 i i i 个数 s s si。 第三行包含整数 n n n。 第四行包含 n n n 个整数其中第 i i i 个整数表示第 i i i 堆石子的数量 h h hi。
输出格式 如果先手方必胜则输出 Yes。 否则输出 No。
数据范围 1 ≤ n , k ≤ 100 , 1 ≤ s i , h i ≤ 10000 1≤n,k≤100,1≤s_{i},h_{i}≤10000 1≤n,k≤100,1≤si,hi≤10000
输入样例
2
2 5
3
2 4 7输出样例
Yes根据上述的SG函数我们可以把每一堆石子的局面的各种选法的集合看成一个图那么在样例中我们就有三个图分别求出这三个图的起点的SG函数值将其抑或起来就可以得到最终的结果
代码
#includeiostream
#includecstring
#includeunordered_set
using namespace std;const int N 110;
const int M 10010;int n, m;
int s[N],f[M]; //s可以选的石子个数fSG函数值int sg(int x) {if (f[x] ! -1)return f[x]; //如果某个状态算过那么就直接返回这个状态的值unordered_setint S; //哈希表存所有可以到达的值for (int i 0; i m; i) {int sum s[i];if (x sum)S.insert(sg(x - sum)); //如果这堆石子的数量是大于拿走的数量的//那么才能够存进去}for (int i 0;; i) { //找集合中不存在的最小的自然数if (!S.count(i)) //如果这个数在S中找不到return f[x] i;//那么就返回这个数作为其SG函数值}
}int main() {cin m;for (int i 0; i m; i)cin s[i]; //能够选的石子数cin n; //石子堆数memset(f, -1, sizeof f); //初始化f数组以进行记忆化搜索int res 0; //存答案for (int i 0; i n; i) {int x; //输入n堆石子各有多少个石子cin x;res ^ sg(x); //对每堆石子求其SG函数值并进行抑或操作}if (res)puts(Yes);//如果最后非0那么必胜else puts(No); //否则必败return 0;
}AcWing.894.拆分-Nim游戏 给定 n n n 堆石子两位玩家轮流操作每次操作可以取走其中的一堆石子然后放入两堆规模更小的石子新堆规模可以为 0 0 0且两个新堆的石子总数可以大于取走的那堆石子数最后无法进行操作的人视为失败。
问如果两人都采用最优策略先手是否必胜。
输入格式 第一行包含整数 n n n。
第二行包含 n n n 个整数其中第 i i i 个整数表示第 i i i 堆石子的数量 a i a_{i} ai。
输出格式 如果先手方必胜则输出 Yes。 否则输出 No。
数据范围 1 ≤ n , a i ≤ 100 1≤n,a_{i}≤100 1≤n,ai≤100
输入样例
2
2 3输出样例
Yes可以将n堆石子看作n个局面集合对于每个局面求SG值之后把他们抑或起来求结果即可
对于每个局面我们只需要找到其所有能到的值然后再去找不存在的最小自然数在过程中会出现一堆分成两堆的情况两堆的局面的SG值就等于两堆各自的SG值抑或起来
#includeiostream
#includeunordered_set
#includecstring
using namespace std;const int N 110;int f[N]; //存sg值int sg(int x) { //sg函数if (f[x] ! -1)return f[x]; //如果已经搜过了就不用再算了unordered_setintS; //哈希表存各种局面的sg值//插入两堆for (int i 0; i x; i) { //第一堆插入小于总石子数的石子for (int j 0; j i; j) { //避免重复使第二堆小于等于第一堆的石子数S.insert(sg(i)^sg(j)); //两堆的sg值等于两堆各自的sg值抑或起来}}for (int i 0;; i) //找到集合中不存在的自然数if (!S.count(i))return f[x] i;
}int main() {int n; cin n;memset(f, -1, sizeof f);int res 0; //答案for (int i 0; i n; i) {int x; cin x;res ^ sg(x); //输入每堆石子数量并抑或上它}if (res)puts(Yes);else puts(No);return 0;
}
