尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
博弈论讲解
简单图上博弈博弈树其实就是记录你每一步决策的状态。比如5 个石子Alice 和 Bob 轮流取每次取 1 到 2 颗取到最后一颗的入人胜Alice 先手问她的必胜决策。5 Start | \ 4 3 Alice | \ \ \ 3 2- 2- 1 Bob | \ \ \ \ \ \ 2 1 1 0 1 0 0 Alice |\ \ \ \ 1 0 0 0 0 Bob | 0 A其中旁边的字母代表现在轮到了谁数字表示当前还剩几颗这就差不多是博弈树。然后求答案就从出边为 0 的开始计算有点类似 Topo 排序。题目P4096P7135这里我认为第二道题不那么像模板题第一道题就是模板题因此我讲第二道P7135这是我做的第一道交互题只不过它也不是很难。如果你发现的仔细的话你就可以填出一个幻方这里不展示包含这几个数字每一行、每一列、每一条对角线都是 15因此我们发现这不就是井字棋吗于是直接建出博弈树就做完了。如果你玩过井字棋的的话你也可以直接写程序暴力和交互库下棋。code不好意思的是我是直接和他下棋并没有建博弈树。提示先手下角网上有说为什么后手堵桥就把交互库第一步下的位置直接提前每个出一套对策直接干。有向图博弈这玩意很好做博弈方式直接建出树只不过有可能有两个父节点同时拥有同一个子节点继父只不过这问题也不大父母离异问题还不大孩子心理会有问题。划掉的部分是我同学说的但我想回一句你是不知道红黑树是吧孙子的孙子秒变爷爷的爷爷这是数据结构和家谱没有问题。但是DAG只存在于有向无环图有环怎么办啥孙子结婚生了爷爷见过基环树吗也有环没关系我们可以发现只要这种情况出现了肯定平局不然跳出这个环外的人就输了题目CF786AP6560P9169都是模板题没必要讲。公平组合游戏Nim 游戏博弈论部分由于以思维为主很少作为一个知识点用来考察。但以nim 游戏为代表的公平组合游戏是一个很容易考场的知识点。公平博弈impartial game指满足如下条件的组合博弈在任意确定状态下所有参与者可选择的行动完全相同仅取决于当前状态与身份无关博弈中的同一个状态不可能多次抵达博弈以参与者无法行动为结束且博弈一定会在有限步后以非平局结束。nim 游戏有堆石子第堆石子有颗石头先后手轮流操作每次可以选择一堆石子然后从中选大于 0 个石头扔掉。谁在操作后场上所有石头清空谁获胜。所有的公平组合游戏都可以转化 为nim 游戏。我们直接给出结论一个状态为先手必败当且仅当所有石子的异或和为 0。证明是这样的不妨把上述状态称为必败。显然当时这就是一个必败态。现在对于任意一个非必败态可以证明一定存在一种操作方案使得一次操作之后转化为必败态且对于一个必败态操作一次必然成为一个非必败态因此证明完毕。于是我们可以线性复杂度判断一局 nim 游戏的状态了。这个理论可以把所有的公平组合游戏转化为nim 游戏。首先公平组合游戏有很多不同的“局”比如nim 游戏中就有局游戏每一局游戏都是一堆石子虽然单堆石子很简单但是它也可以看做一张有向无环图博弈连边为必败点。而所有的“局”都是一张有向无环图。我们定义图上一个点的函数值为所有它可以到达的点的值的 mex。且必败态的值为 0。把所有游戏起点的异或起来不为 0 则为必胜态。knim 游戏与 nim 游戏的区别在于每次可以至多拿堆石子。阶梯nim每次可以在一堆里面选出大于 0 个石子然后放到下一堆特殊的对于第一堆选出来的石子会直接扔掉。树上nim选出来的石子放到父节点上根上的直接扔掉。树上博弈给你若干个有根森林每次删掉一颗子树根不能删谁不能操作谁输。题目听懂了就会做因为都是模板题P2148P2575P6639P13114此处不讲题如果实在要我讲我会另出一篇文章讲要讲在评论区说。后记反正你在考场上遇到这类题要不是思维题要不是模板题都不是就想想其他做法吧。如果你想再做点这类题的话可以尝试做这道题。这道题和 P7135 一样也是比较有意思的题目可以好好想一想也提升了能力你水了一道黑题巨佬爆切黑题巨~~~膜拜~~~。对了你们想不想看 DEVC 的神秘用法想看在评论区里说。
RELATED

相关推荐

PDF导入RAG后乱码、空白或顺序错乱怎么办?文档解析完整排查

PDF导入RAG后乱码、空白或顺序错乱怎么办?文档解析完整排查

文章摘要 PDF导入知识库后出现乱码、空白、文字顺序错乱,是企业RAG项目最常见的数据源故障。根因可能是扫描件没有文本层、字体使用自定义编码、双栏版式阅读顺序错误、表格被拆散、OCR语言配置不正确,或者解析结果未经质量校验就直接分块。本文给出从PDF类型识别、文本层检…

📅 2026/9/17 15:27:10
C语言文件相关操作

C语言文件相关操作

一、文件操作的基本概念文件的定义与分类(文本文件、二进制文件)文件指针(FILE结构体)的作用文件打开与关闭的必要性文件的定义:磁盘(硬盘)上的⽂件是⽂件。分类:程序⽂件(源程序⽂件…

📅 2026/8/8 13:18:27
GPT-5.6显式缓存断点怎么用?RAG长Prompt成本优化与失效策略

GPT-5.6显式缓存断点怎么用?RAG长Prompt成本优化与失效策略

文章摘要 GPT-5.6在API中引入更可预测的Prompt缓存机制,包括显式缓存断点和至少30分钟的缓存生命周期。对于RAG、Agent和企业知识助手,这意味着稳定的System Prompt、工具定义、输出Schema和公共知识上下文可以复用,从而减少重复计算和输入成本。但缓存并不是把整个请求永久…

📅 2026/8/8 9:30:51
MORE NEWS

更多资讯

📰

CNN图像项目复现指南:从源码到训练管线全流程

简介:这份资源是围绕卷积神经网络实现端到端数字图像处理的论文复现项目,包含完整Python源码与配套文档说明,面向计算机相关专业正在做毕业设计、期末大作业或课程设计的学生,以及需要项目实战练习的学习者。项目经导师指导并获评…

📰

阿里云一键抠图C#落地:批量处理与并发避坑实战

简介:阿里PicDemo.zip 是一份基于阿里开放平台实现一键抠图功能的 C#/.NET 示例项目,面向希望在 .NET 环境中快速集成云端图像处理服务的开发者,尤其适合刚接触阿里云 API 的初学者。压缩包约 12.31MB,共 305 个文件,以…

📰

C++职责链模式高级实战:从动态编排到协程异步化

职责链模式在C里属于那种拿起来容易、用好了很难的设计模式。很多人知道它的教科书写法:一个抽象Handler类,每个子类维护一个next指针,handle的时候要么自己处理,要么丢给下一个处理器。但真到了生产环境,你会发现这套…

📰

AI赋能班主任:考勤、量化考核、家校沟通与学情分析实战

1. 先解决最耗时间的考勤与信息统计说起班主任的工作量,我相信每位同行都能列举出一堆"看不见的活":每天早上催交作业、检查出勤、登记迟到早退,月底还要对着几十张表格手工统计全勤率、缺勤次数、请假天数。这些事单次只需要几分钟…

📰

VSCode搭建Verilog仿真环境:iVerilog+GTKWave快速验证指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📰

Ubuntu 24.04 U盘启动失败原因与Rufus精准配置指南

1. 项目概述:为什么Ubuntu 24.04的U盘安装,现在比以往任何时候都更需要“一次做对”Ubuntu 24.04 LTS(代号Noble Numbat)发布后,我身边至少有7位朋友在装系统时卡在了U盘这一步——不是镜像下错了,就是写入…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬