金融企业网站php源码,注册域名 不建网站,网站制作文案杭州,赌粉在哪个平台引流忽然发现博弈论是个很好玩的东西哎 之前假期学长讲课的时候就发现这种必胜的战略可以用来坑人做题 这两天终于做了第一道博弈论的题#xff0c;写篇博客纪念一下 灵感来源#xff1a;洛谷P1247 Pre-scene 众所周知#xff0c;李明和Jenny都喜欢Danny#xff0c;为了争夺Dan…忽然发现博弈论是个很好玩的东西哎 之前假期学长讲课的时候就发现这种必胜的战略可以用来坑人做题 这两天终于做了第一道博弈论的题写篇博客纪念一下 灵感来源洛谷P1247 Pre-scene 众所周知李明和Jenny都喜欢Danny为了争夺Danny的所有权他们决定玩一个游戏。规则是这样的 有k堆扑克牌不成套两人轮流从某一堆中拿出x张牌不能不拿也不能跨堆拿牌拿走最后一张(堆)牌的一方获胜。 命运当然是不公平的李明来向你请教有没有必胜的方法你聪明的能告诉他么 0X10 知识 先来了解一下什么是Nim博弈 通常的Nim游戏的定义是这样的有若干堆石子每堆石子的数量都是有限的合法的移动是“选择一堆石子并拿走若干颗不能不拿”如果轮到某个人时所有的石子堆都已经被拿空了则判负因为他此刻没有任何合法的移动。 ——百度百科 了解Nim游戏之后我们会发现这是一个经典的ICG游戏不要问我什么是ICG因为我百度百科也不知道 显然游戏有两种局面先手必败和先手必胜我们分别定义他们为P-position和N-position两种其中P代表PreviousN代表Next那么我们可以得出从N-position转移而来的一定是P-position反之也成立。 0X20 简单的证明 我们先来手玩一组小数据一共有2堆石子每一堆都有3个你是先手的话会怎么拿由规则我们知道玩家的目标是拿走最后一个石子所以先手的你一定不会把某一堆全部拿走因为如果这样后手将会拿走另一堆先手必败但是如果你先拿1个后手会跟着你从另一堆也拿一个你拿2个后手仍可以做和你一样的操作先手必败。至此我们发现33是一个P-position的局面。 推论1.当a1^a2^a3^……a^n0时为P-position即先手必败。 2.当a1^a2^a3^……a^n!0时一定存在某个移动使得局面变成一个P-position即此局面为N-position。 0X30 实现 直接异或运算即可代码过于简单就不放了。 0X40 题解 传送门 了解了上述知识后这道题几乎就是一个裸的板子了就是加了一个输出怎么取和取完的状态而已这也很好实现。 0X41 怎么取 由于我们发现异或和不等于0我们就要考虑怎么取使得其等于0了。 设ka1^a2^a3^……a^n因为k!0而显然k^k0所以要使a1^a2^a3^……a(n-1)^an^k0只需要把其中一个ai变成ai^k即可又因必须要取可得ai^kai 0X42 取完的状态 直接更改即可 0X43 代码 1 //2 // main.cpp3 // Luogu4 //5 // Created by gengyf on 2019/5/16.6 // Copyright © 2019 yifan Geng. All rights reserved.7 //8 9 #include cstdio
10 int n;
11 int a[500005];
12 int main(){
13 scanf(%d,n);
14 int check0;
15 for(int i1; in; i){
16 scanf(%d,a[i]);
17 check^a[i];
18 }
19 if(!check){
20 printf(lose\n);
21 return 0;
22 }
23 for(int i1; in; i){
24 if((check^a[i])a[i]){
25 printf(%d %d\n,a[i]-(check^a[i]),i);
26 for(int j1; jn; j)
27 if(j!i)
28 printf(%d ,a[j]);
29 else printf(%d ,check^a[i]);
30 break;
31 }
32 }
33 return 0;
34 } 转载于:https://www.cnblogs.com/gengyf/p/10878126.html
