当前位置: 首页 > news >正文

数据结构与算法:博弈类问题

前言

终于到博弈了,博弈问题在cf里还挺常见的。

一、博弈类问题

1.内容

博弈类问题分为公平组合游戏、非公平组合游戏(棋类)和反常游戏。反常游戏可以看作公平组合游戏的变形,所以我们只需要研究公平组合游戏(ICG)即可。

在博弈类问题里,两玩家都只会做出最优的选择。而且博弈类问题没有随机成分,当局面确定时,结果必然是注定的。

2.公平组合游戏(ICG)

公平组合游戏有四个条件:两个玩家轮流行动且行动方式一致、两个玩家对状况完全了解、游戏一定会在有限步内分出胜负和游戏必然以某玩家无法行动结束。

二、经典博弈

1.巴什博弈

(1)内容

一共有n颗石子,两个人轮流拿,每次可以拿1~m颗石子,拿到最后一颗石子的人获胜。

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//结论:只要n不等于m+1的整倍,则必然先手赢//动态规划验证
int MAXN=1001;
vector<vector<string>>dp(MAXN,vector<string>(MAXN));
string bash1(int n,int m)
{if(n==0){return "后手";}if(dp[n][m]!=""){return dp[n][m];}string ans="后手";for(int p=1;p<=m;p++){if(bash1(n-p,m)=="后手"){ans="先手";break;}}dp[n][m]=ans;return ans;
}//正解
string bash2(int n,int m)
{return n%(m+1)!=0?"先手":"后手";
}void test()
{srand(time(0));int testTime=5000;int V=500;cout<<"Start"<<endl;for(int i=1;i<=testTime;i++){int n=rand()%V;int m=rand()%V+1;string ans1=bash1(n,m);string ans2=bash2(n,m);if(ans1!=ans2){cout<<"Wrong"<<endl;}}cout<<"Over"<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;//cin>>t;// while(t--)// {//     solve();    // }test();return 0;
}

观察可以发现,只要n初始不为m+1的整数倍,则必然是先手赢。

举个例子,当n等于4,m等于3时,此时先手不管拿几个,后手都可以一次拿完,那么先手是必输的。当n等于5,m依然为3时,此时先手可以先拿一个,然后让后手面对n等于4的情况,那么此时先手就是必胜的。所以推广到一般情况,只要初始n不等于m+1的整数倍,则先手必然可以每次让后手面对等于m+1整数倍的情况,则先手必胜。

(2)扩展——Roy&October之取石子

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;void solve()
{int n;cin>>n;//只要n不是6的整数倍,先手赢cout<<(n%6!=0?"October wins!":"Roy wins!")<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

从n等于1开始举例并观察规律,可以发现,直到当n等于6时先手才是必输的。而当n处于7到11时,先手总可以让后手面对n等于6的状态,直到n等于12时先手必输。所以只要n不等于6的整数倍,先手就是必胜的。

2.尼姆博弈——Nim 游戏

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//异或和不等于0,先手赢void solve()
{int n;cin>>n;int a;int eor=0;for(int i=0;i<n;i++){cin>>a;eor^=a;}   cout<<(eor!=0?"Yes":"No")<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--){solve();    }return 0;
}

尼姆博弈这个结论完全是通过后面的sg定理推出来的,纯靠找规律基本不太可能想到……

规律就是只要所有堆的石头数的异或和不等于0,那先手就是必胜的。

硬推这个原理的话就是,若异或和不等于0,则必存在至少一位上有奇数个1,这样异或起来才会导致该位的结果为1。那么必然存在一种拿法使得先手可以在所有1的个数为奇数的位上使1的个数变为偶数,从而让后手面对异或和等于0的必败态。

3.反尼姆博弈——小约翰的游戏

这就是一个反常游戏了。

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
typedef pair<int,int> pii;//当每堆都是1时,偶数堆先手赢,奇数堆后手赢//当只有一堆大于
http://www.lryc.cn/news/582466.html

相关文章:

  • 服务器经常出现蓝屏是什么原因导致的?如何排查和修复?
  • node.js中yarn、npm、cnpm详解
  • npm : 无法加载文件 D:\Node\npm.ps1,因为在此系统上禁止运行脚本。
  • 【QT】-隐式转换 explicit用法
  • React18+TypeScript状态管理最佳实践
  • 说说SpringBoot常用的注解?
  • 【Nginx】Nginx代理WebSocket
  • Ollama+OpenWebUI 0.42+0.3.35 最新版一键安装教程,解决手动更新失败问题
  • kafka如何让消息均匀的写入到每个partition
  • OpenWebUI(5)源码学习-后端socket通信模块
  • App Trace功能实战:一键拉起应用实践
  • 【保姆级图文详解】RAG 实战(Spring AI + 本地知识库)旅游知识库问答
  • 微软上线 Deep Research 预览版:o3+必应赋能研究自动化
  • OGRE 3D----6. 背景图片渲染实现详解
  • 【Unity3D】微信小游戏适配安全区域或胶囊控件(圆圈按钮)水平高度一致方案
  • element el-table渲染二维对象数组
  • 什么是 3D 文件?
  • 开源 python 应用 开发(三)python语法介绍
  • 【电脑】主要组成部分
  • 装备制造数字孪生底座平台
  • 【网络】Linux 内核优化实战 - net.ipv4.tcp_syn_retries
  • 利用AI技术快速提升图片编辑效率的方法
  • 数据结构 --- 栈
  • django-ckeditor配置html5video实现视频上传与播放
  • word中的单位详解
  • 算法化资本——智能投顾技术重构金融生态的深度解析
  • 使用阿里云/腾讯云安装完成mysql使用不了
  • 分库分表之实战-sharding-JDBC广播表
  • JavaScript基础篇——第二章 类型转换与常见错误解析
  • 《UE5_C++多人TPS完整教程》学习笔记42 ——《P43 瞄准(Aiming)》