首页 > 其他分享 >博弈论练习3 Palindrome Game (hard version) (人类智慧题)

博弈论练习3 Palindrome Game (hard version) (人类智慧题)

时间:2022-11-20 10:04:32浏览次数:78  
标签:博弈论 int MAX hard Game version cnt2 cnt1 回文

题目链接在这里:​​C-Palindrome Game (hard version)_牛客竞赛博弈专题班组合游戏基本概念、对抗搜索、Bash游戏、Nim游戏习题 (nowcoder.com)​

这题挺人类智慧的,但是也有博弈论的一般思想,就是二者在中间过程的时候一直做着对称的工作或者执行相同的策略,只在开头或者结尾的时候先手会根据形势作出不同的决策,以后在做博弈论问题的决策时要考虑到这一点。

对于这道题来说,我们可以先看回文的情况,如果字符串长度为偶数那一定是后手胜,因为后手可以一直保证下完以后是一个回文串,然后在串只剩下一个0的时候选择操作二。如果是奇数且最中间是0的话,那么先手把这个0下了剩下的就是前一种情况。

如果是非回文的情况,基本都是先手胜,因为先手可以一直选择操作2,直到快要成回文串的时候选择自己是先手还是后手进入回文串。唯一一种平局的情况就是字符串为奇数只有2个0且最中间的是0.这个点很重要。

 

1 #include "bits/stdc++.h"
2 using namespace std;
3 const int MAX=1005;
4 int t,n;
5 char s[MAX];
6 int cnt1,cnt2;
7 int main(){
8 int i,j;
9 scanf("%d",&t);
10 while (t--){
11 scanf("%d\n%s",&n,s+1);
12 cnt1=cnt2=0;
13 for (i=1;i<=(n-1)/2+1;i++){
14 if (s[i]!=s[n-i+1])
15 cnt1++;
16 }
17 for (i=1;i<=n;i++) if (s[i]=='0') cnt2++;
18 if (cnt1==0){
19 if (cnt2==1){
20 cout<<"BOB"<<endl;
21 continue;
22 }
23 if (cnt2%2==1){
24 cout<<"ALICE"<<endl;
25 continue;
26 }
27 cout<<"BOB"<<endl;
28 }
29 else{
30 if (cnt2==2 && n%2==1 && s[n/2+1]=='0')
31 cout<<"DRAW"<<endl;
32 else
33 cout<<"ALICE"<<endl;
34 }
35 }
36 return 0;
37 }

 

标签:博弈论,int,MAX,hard,Game,version,cnt2,cnt1,回文
From: https://blog.51cto.com/u_15793969/5871254

相关文章

  • Git reset 的hard、soft、mixed参数对比
    目录分区概念1.--soft参数2.--mixed参数3.--hard参数分区概念先要清楚在本地,git会分三个区:工作区、暂存区、本地库。当使用去做版本移动的时候,那么在使用【--hard】......
  • [Typescript] 111. Hard - String Join
    Createatype-safestringjoinutilitywhichcanbeusedlikeso:consthyphenJoiner=join('-')constresult=hyphenJoiner('a','b','c');//='a-b-c'Or......
  • hardhat 使用笔记
    1verify时需要clearnpxhardhatcleannpxhardhatverify--networkTESContract0x474407a7d6aE50e86A3C0055338A5D5188Fea032"100""0x01BE23585060835E02B77ef47......
  • 智能合约开发-hardhat、solidity和react的全栈开发
    创建react工程先通过npx创建react工程,工程名称full-stack-dappnpxcreate-react-appfull-stack-dapp 然后进入full-stack-dapp目录npmrunstart......
  • CF1610H Squid Game
    题面传送门首先定\(1\)为根节点,然后我们发现,如果全部的限制都是弯的,也就是\(x_i\)与\(y_i\)均不是两个点的LCA,则直接选择一个根节点就可以解决。然后如果全部限制都是直......
  • [Typescript] 110. Hard - Union to Tuple
    Implementatype, UnionToTuple,thatconvertsauniontoatuple.Asweknow,unionisanunorderedstructure,buttupleisanordered,whichimpliesthatwe......
  • Hardhat工程里用.env文件保护私钥
    在上一篇https://www.cnblogs.com/lyhero11/p/16892741.html里把私钥放在了hardhat.config.js里了,但是如果我们想把代码提交到git那么就会泄漏私钥,把这个文件不提交又破坏......
  • hardhat使用
    hardhat是智能合约开发框架 hardhat和truffle的对比truffle比较早期的开发工具,但对比hardhat比较难用.现在大多智能合约都会普遍使用hardhat.  ......
  • ESP32:Protocol version of client is unrecognized, expected Rev 1 (rosserial 0.5+
    问题通过​​Baize_ServoDriver_esp32​​这块开发板与ROS进行串口通信的过程中,发现出现了如下错误这个错误是在我运行了rosrunrosserial_pythonserial_node.py/dev/ttyU......
  • java 分布式游戏服务器框架,集群游戏服务器框架,游戏服务器网关框架 ioGame 网络游戏服
    ioGame国内首个基于蚂蚁金服SOFABolt的java网络游戏服务器框架;无锁异步化、事件驱动的架构设计通过ioGame可以很容易的搭建出一个集群无中心节点、有状态多进程的......