strGame:博弈论,trie
挺有意思的一道题。初探博弈论。
最好自己思考?
我们先考虑只有1轮游戏的情况。
这题明显要在字符串上一位一位地走,所以对字符串建立起trie。
最终建立起的trie的叶节点就是必败位置了。
对于非叶节点,如果它有一个儿子是必败节点,那么这个节点就是必胜节点了。(类似与mex函数)
那么如果根节点必胜,那么就是先手必胜,否则就是后手必胜了。
如果最后一轮后手必胜,那么两个人就需要争夺最后一轮的后手,所以他们要赢倒数第二轮。
而倒数第二轮和最后一轮是一样的,那么倒数第二轮也是后手必胜。倒数第二轮的后手整场游戏也必胜。
以此类推到倒数第三轮,倒数第四轮。。。直到第一轮,都一样。
所以,如果某一轮中后手必胜,那么整场游戏后手Dirty必胜。
剩下的情况就是先手必胜,那么就是要争夺先手,那么就要尽量输掉倒数第二轮。
如何判定先手能否必定让自己输掉一轮游戏?
只要把trie树的叶节点改为必胜节点就好了,再跑一遍。
那么如果先手可以必定让自己输掉一轮游戏,也能必定让自己赢一轮游戏。
那么除了最后一轮以外他都可以让自己输掉以取得先手,直到最后一轮让自己取胜。
所以,如果某一轮中先手必胜,先手在相反游戏中也必胜(即可以让自己必定输掉),那么整场游戏先手Pure必胜。
剩下的就是先手在一轮游戏中必胜,但是不能在相反游戏中取胜(即自己不能必定输掉)。
最后一轮是先手必胜。
倒数第二轮中要争夺最后一轮的先手,故要输掉,所以倒数第二轮中的后手在整场游戏中必胜。
倒数第三轮中要争夺倒数第二轮的后手,要赢,所以倒数第三轮的先手在整场游戏中必胜。
以此类推。。。
所以,如果一轮游戏先手必胜,而相反游戏后手必胜(即先手不能让自己输掉),总轮数为奇数时,先手Pure必胜。否则,后手Dirty必胜。
好题。
自己思考酣畅淋漓(数学自习灵感++)
#include<cstdio>
#include<cstring>
using namespace std;
int k,trie[][],w[][],cnt,n,rt,len;char s[];
void insert(int &p,int al){
if(!p)p=++cnt;if(al==len)return;
insert(trie[p][s[al]-'a'],al+);
}
void dfs(int p){
int hs=;w[][p]=w[][p]=;
for(int i=;i<=;++i)if(trie[p][i]){hs=;break;}
if(!hs){w[][p]=;w[][p]=;return;}
for(int i=;i<=;++i)if(trie[p][i]){
dfs(trie[p][i]);
if(!w[][trie[p][i]])w[][p]=;
if(!w[][trie[p][i]])w[][p]=;
}
}
int main(){
int t;scanf("%d",&t);
while(t--){
scanf("%d%d",&n,&k);rt=cnt=;memset(trie,,sizeof trie);
for(int i=;i<=n;++i)scanf("%s",s),len=strlen(s),insert(rt,);
dfs(rt);//for(int i=1;i<=cnt;++i)printf("%d %d\n",w[0][i],w[1][i]);
if(!w[][rt])puts("Dirty");
else if(w[][rt])puts("Pure");
else if(k&)puts("Pure");
else puts("Dirty");
}
}
最新文章
- Kali 使用ssh,安装vmware tools 和字体重叠
- 读jQuery源码 - Callbacks
- JAVA项目JDK版本修改
- UIButton详解
- 10款让你心动的 HTML5 &; CSS3 效果
- html 表单笔记
- Asp.net MVC 4 异步方法
- Swift数组的加法运算符用法:array1 += array2
- html表单 第四节
- VS2010与VAssistX
- python lcd 时间显示
- 新手笔记-tftp与yum
- <;input type=button>; 跳转页面
- white-space详解
- Java IO流学习总结(2)
- Java常用类之【日期相关类】
- Android-Chart
- vue 跨域问题
- html5 canvas arcTo()
- OpenCV处理直方图
热门文章
- ELK 学习笔记之 Kibana入门使用
- 关于SpringBoot 1.x和2.x版本差别
- 最近学到的Git知识,大厂的Git机制还是很方便的
- ES(Elastic Search)update操作设置无 docment时进行insert
- Linux配置python
- Java11月9日的动手动脑
- 使用malloc函数或new运算符为链表结点分配内存空间
- Spring Boot2 系列教程(十三)Spring Boot 中的全局异常处理
- 配置code::blocks的glut环境
- npm install bcrypt报错