专做外贸库存的网站,企业标准化体系建设流程,阿里云网站打不开,网站推广营销开头先啰嗦一句#xff1a;想学好博弈#xff0c;必然要花费很多的时间#xff0c;深入学习#xff0c;不要存在一知半解#xff0c;应该是一看到题目#xff0c;就想到博弈的类型。 以及#xff0c;想不断重复不断重复#xff0c;做大量各大oj网站的题目#xff0c;最… 开头先啰嗦一句想学好博弈必然要花费很多的时间深入学习不要存在一知半解应该是一看到题目就想到博弈的类型。 以及想不断重复不断重复做大量各大oj网站的题目最后吃透它。 博弈 博弈论又被称为对策论Game Theory既是现代数学的一个新分支也是运筹学的一个重要学科。 博弈具体的例子就是下棋双方都考虑最有利于自已的步骤但是最终必有一方输一方赢。 博弈的策略参与者在行动之前所准备好的一套完整的行动方案就是想好下完这步棋对方会如何下 以及接下来该如何下最终得出结果。 常见的博弈有以下 1.博弈合作博弈和非合作博弈 合作博弈指参与者能够达成一种具有约束力的协议在协议范围内选择有利于双方的策略 非合作博弈指参与者无法达成这样一种协议2.博弈静态博弈和动态博弈 静态博弈指在博弈中参与者同时选择或虽非同时选择但是在逻辑时间 上是同时的。期末老师评分与同学给老师评分 动态博弈指在博弈中参与者的行动有先后顺序且后行动者能够观察 到先行动者的行动。下棋3.博弈完全信息博弈与不完全信息博弈 完全信息博弈指在博弈中每个参与者对其他参与者的类型策略空间及损益函数都有准确的信息。卖家与买家 不完全信息博弈:总有一些信息不是所有参与者都知道的4.博弈零和博弈与非零和博弈 零和博弈指博弈前的损益总和与博弈后的损益总和相等 非零和博弈指博弈后的损益大于小于博弈前的损益总和正和或负和 下面我主要讲一些关于算法比赛中用到的博弈类型 首先你要理解必胜状态和必败状态 对下先手来说 一个状态是必败状态当且仅当它的所有后继都是必败状态。 一个状态是必胜状态当且仅当它至少有一个后继是必败状态。 就是说博弈者一旦捉住了胜利的把柄必然最后胜利。 博弈中常常用到的 两个数不用中间变量实现交换。 a b; a a^b; b a^b; a a^b; 巴什博弈 百度百科 巴什博弈只有一堆n个物品两个人轮流从这堆物品中取物 规定每次至少取一个最多取m个。最后取光者得胜。 显然如果nm1那么由于一次最多只能取m个所以无论先取者拿走多少个后取者都能够一次拿走剩余的物品后者取胜。因此我们发现了如何取胜的法则如果nm1rsr为任意自然数s≤m),那么先取者要拿走s个物品如果后取者拿走k≤m)个那么先取者再拿走m1-k个结果剩下m1r-1个以后保持这样的取法那么先取者肯定获胜。总之要保持给对手留下m1的倍数就能最后获胜。这个游戏还可以有一种变相的玩法两个人轮流报数每次至少报一个最多报十个谁能报到100者胜。对于巴什博弈那么我们规定如果最后取光者输那么又会如何呢n-1%m10则后手胜利 先手会重新决定策略所以不是简单的相反行的 例如n15m3 后手 先手 剩余 0 2 13 1 3 9 2 2 5 3 1 1 1 0 0 先手胜利 输的人最后必定只抓走一个如果1个则必定会留一个给对手 请去刷下面的题目均是巴什博弈 算博弈题目时一定要算到一个周期结束防止出错很有可能像HDU2897那样。中途错的猝不及防 HDU1847 代码实现如下 package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin new Scanner(System.in);while(cin.hasNext()){int n cin.nextInt();PLG(n);}}static void PLG(int n){if(n%3 0){System.out.println(Cici);}else{System.out.println(Kiki);}}
} HDU2147 代码实现如下 import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin new Scanner(System.in);while(cin.hasNext()){int n cin.nextInt();int m cin.nextInt();if(n 0 m 0){return;}PLG(n,m);}}static void PLG(int n,int m){if(n%2 0 || m % 2 0){System.out.println(Wonderful!);}else{System.out.println(What a pity!);}}
} HDU2149 代码实现如下 package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin new Scanner(System.in);while(cin.hasNext()){int m cin.nextInt();int n cin.nextInt();PLG(m,n);}}static void PLG(int m,int n){if(m % (n1) 0){System.out.println(none);}else{if(m n){for(int i m; i n; i){if(i! m){System.out.print( );}System.out.print(i);}System.out.println();}else{int flag 0;for(int i 1; i n; i){if((m-i)%(n1) 0){if(flag 0){System.out.print(i);}else{System.out.print( i);}flag;}}System.out.println();}}}
} HDU2188 代码实现如下 package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin new Scanner(System.in);int C cin.nextInt();while(C ! 0){int n cin.nextInt();int m cin.nextInt();PLG(n,m);C--;}}static void PLG(int n,int m){if(n m){System.out.println(Grass);}else{if(n % (m1) 0){System.out.println(Rabbit);}else{System.out.println(Grass);}}}
} HDU2897 代码实现如下 package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{public static void main(String []args){Scanner cin new Scanner(System.in);while(cin.hasNext()){int n cin.nextInt();int p cin.nextInt();int q cin.nextInt();PLG(n,p,q);}}static void PLG(int n,int p,int q){if(n pq){if(n p){System.out.println(LOST);}else{System.out.println(WIN);}}else if(n%(pq) 0){System.out.println(WIN);}else//有坑{if(n % (pq) p)System.out.println(WIN);elseSystem.out.println(LOST);}}
} 威佐夫博弈 一定要去百度百科上面先理解透意思。 下面是一些威佐夫博弈的总结 威佐夫博弈Wythoffs game有两堆各若干个物品两个人轮流从某一堆取至少一个或同时从两堆中取同样多的物品规定每次至少取一个多者不限最后取光者得胜。 这种情况下是颇为复杂的。我们用a[k]b[k]a[k] ≤ b[k] ,k012...,n)表示两堆物品的数量并称其为局势如果甲面对00那么甲已经输了这种局势我们称为奇异局势。 前几个奇异局势是00、12、35、47、610、813、915、1118、1220。注k表示奇异局势的序号 第一个奇异局势k0。 可以看出,a[0]b[0]0,a[k]是未在前面出现过的最小自然数,而 b[k] a[k] k。 重要结论a,bb a的如果int)b-a*(Math.sqrt(5)1)/2 a,那么先手必输。 如果不等后者必输。 设当前局势为(a,b a b①ab同时从两堆取走a个石子转化为(0,0)②aa[k]bb[k]从第二堆取走b−b[k]个石子转化为(a,b[k])③aa[k]bb[k]同时从两堆取走a−a[b−a]个石子转化为(a[b−a],b−aa[b−a])④aa[k]bb[k]从第一堆取走a−a[k]个石子转化为(a[k],b)⑤aa[k]bb[k]若aa[j] (jk)则从第二堆取走b−b[j]个石子转化为(a,b[j]) 否则必有ab[j](jk)ab[j](jk)则从第二堆取走b−a[j]b−a[j]个石子转化为(a[j],a) 例如5 8 5a(8-5)a34 8b(8-5)b37 从两堆中取走a-a(b-a)5-41个变成奇异局势(4,7)。 例如4 6 4a(6-4)a23 6b(6-4)b25 从两堆中取走a-a(b-a)4-31个变成奇异局势(3,5)。 可以理解成变成差为b-a的奇异局势。 如果abk并且b-a!k则从b堆中取走b-ak个变成奇异局势(akbk). 例如5 10 5b2 10-55!2 则从10中取走10-a210-37个变成奇异局势(3,5)。 为什么要b-a!k呢例如7 10 7a310-73k 也可以变成奇异局势(4,7)。但这已经在4判断过了。 奇异局势就是当你面临这种情况的时候你必然是输的反之你必赢。 a,b,a,b两堆物品的重量此处是ba; 解题的技巧 if a b , 交换两个值。 c b-a; c int(c*(根号51)/2 if(c b) 先手必输 else 先手必赢 题目HDU1527 HDU2177特别要注意HDU2177这道题目。 HDU1527的代码实现如下 package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{static final double mid (Math.sqrt(5)1)/2;public static void main(String []args){Scanner cin new Scanner(System.in);while(cin.hasNext()){int a cin.nextInt();int b cin.nextInt();int MAX Math.max(a, b);int MIN Math.min(a, b);int temp (int) ((MAX-MIN)*mid);if(temp MIN){System.out.println(0);}else{System.out.println(1);}}}
} HDU2177的代码实现如下巧妙暴力分情况太麻烦了。 package Combat.com;import java.util.Arrays;import java.util.Scanner;public class Main{ static final double MID (Math.sqrt(5)1)/2; public static void main(String []args) { Scanner cin new Scanner(System.in); while(cin.hasNext()) { int a cin.nextInt(); int b cin.nextInt(); if(a 0 b 0) { return; } WTFGame(a,b); } } static void WTFGame(int a,int b) { int temp (int) ((b-a)*MID); if(temp a) { System.out.println(0); } else { System.out.println(1); for(int i 1; i a; i)//先取同样石子 { int n a-i; int m b-i; temp (int) ((m-n)*MID); if(temp n) { System.out.println(n m); } } for(int i a-1; i 0; i--)//从最小堆单取 { temp (int) ((b-i)*MID); if(temp i)//因为a越小temp就越大永远不可能等。 { break; } } for(int i b-1; i 0; i--)//从最大堆单取 { int n a; int m i; if(n m) { int t a; n m; m t; temp (int)((m-n)*MID); if(temp n)//这里充当优先当条件满足无需进行下去了。 { break; } } temp (int) ((m-n)*MID); if(temp n) { System.out.println(n m); } } } }} 尼姆博弈Nimm Game 尼姆博弈指的是这样一个博弈游戏 有任意堆物品每堆物品的个数是任意的双方轮流从中取物品每一次只能从一堆物品中取部分或全部物品最少取一件 取到最后一件物品的人获胜。 百度百科 有三堆各若干个物品两个人轮流从某一堆取任意多的物品规定每次至少取一个多者不限最后取光者得胜。 这种情况最有意思它与二进制有密切关系我们用abc表示某种局势首先000显然是奇异局势无论谁面对奇异局势都必然失败。第二种奇异局势是 0nn只要与对手拿走一样多的物品最后都将导致000。仔细分析一下123也是奇异局势无论自己如何拿接下来对手都可以将其变为0nn 的情形。 计算机算法里面有一种叫做按位模2加也叫做异或的运算我们用符号⊕表示这种运算先看123的按位模2加的结果 1 二进制01 2 二进制10 3 二进制11 ⊕ ——————— 0 二进制00 注意不进位 对于奇异局势0nn也一样结果也是0。 任何奇异局势abc都有a⊕b⊕c 0。 注意到异或运算的交换律和结合律及a⊕a0: a⊕b⊕(a⊕b)(a⊕a)⊕(b⊕b)0⊕00。 所以从一个非奇异局势向一个奇异局势转换的方式可以是 1使 a c⊕b 2使 b a⊕c 3使 c a⊕b 结论就是把每堆物品数全部异或起来如果得到的值为0那么先手必败否则先手必胜。 HDU2176 代码实现如下; package Combat.com;import java.util.Arrays;
import java.util.Scanner;public class Main
{static final int MAX 200005;static int array[] new int[MAX];public static void main(String []args){Scanner cin new Scanner(System.in);while(cin.hasNext()){int m cin.nextInt();if(m 0){return;}int sum 0;//异或的结果for(int i 0; i m; i){array[i] cin.nextInt();sum sum^array[i];}NIMGame(sum,m);}}static void NIMGame(int sum,int k){if(sum 0)//代表面临奇异情况必输{System.out.println(No);return;}else{System.out.println(Yes);for(int i 0; i k; i)//胜的第一次取法{int s sum^array[i];//结果s相当于,sum没与array[i]异或。if(s array[i]){System.out.println(array[i] s);}}}}
} HDU1850 也是一道尼姆博弈题目解法和上面相同。 HDU1907也是同样的做法 阶梯博弈 具体意思参照下面网址https://www.cnblogs.com/jiangjing/p/3849284.html 转载于:https://www.cnblogs.com/674001396long/p/9901811.html
