欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C++實(shí)現(xiàn)涂色游戲(博弈)

 更新時(shí)間:2020年02月05日 08:33:59   作者:LSC_333  
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)涂色游戲,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下

在一個(gè)2*N的格子上,Alice和Bob又開(kāi)始了新游戲之旅。 

這些格子中的一些已經(jīng)被涂過(guò)色,Alice和Bob輪流在這些格子里進(jìn)行涂色操作,使用兩種涂色工具,第一種可以涂色任意一個(gè)格子,第二種可以涂色任意一個(gè)2*2的格子。每一輪游戲里,他們可以選擇一種工具來(lái)涂色尚未被染色的格子。需要注意,涂色2*2的格子時(shí),4個(gè)格子都應(yīng)當(dāng)未被涂色。最后一步涂滿所有格子的玩家獲勝。 

一如既往,Alice先手,最優(yōu)策略,誰(shuí)是贏家? 
Input輸入第一行為T(mén),表示有T組測(cè)試數(shù)據(jù)。 
每組數(shù)據(jù)包含兩個(gè)數(shù)字,N與M,M表示有多少個(gè)已被染色的格子。接下來(lái)的M行每行有兩個(gè)數(shù)字Xi與Yi,表示已經(jīng)被涂色的格子坐標(biāo)。 

[Technical Specification] 

1. 1 <= T <= 74 
2. 1 <= N <= 4747 
3. 0 <= M <= 2 * N 
4. 1 <= Xi <= 2, 1 <= Yi <= N,格子坐標(biāo)不會(huì)重復(fù)出現(xiàn) 
Output對(duì)每組數(shù)據(jù),先輸出為第幾組數(shù)據(jù),然后輸出“Alice”或者“Bob”,表示這輪游戲的贏家。 Sample Input
2
2 0
2 2
1 1
2 2
Sample Output
Case 1: Alice
Case 2: Bob

思路:

可以先考慮有連續(xù)n列的空格的sg值是多少。

n=0時(shí)顯然sg[0]=0,之后就是普通的sg函數(shù)打表,只不過(guò)是要將格子分區(qū)而已。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <queue>
#include <algorithm>
#include <vector>
#include <stack>
#define INF 0x3f3f3f3f
#pragma comment(linker, "/STACK:102400000,102400000")
using namespace std;
const int maxn=5000;
int sg[maxn];
bool pl[2][maxn];
int get_sg(int x)
{
 if(sg[x]!=-1)
  return sg[x];
 bool vis[maxn];
 memset(vis, false , sizeof(vis));
 for(int i=0; i<=x-1-i; i++)
 {
  int t=get_sg(i)^1^get_sg(x-1-i); //只涂這一列的其中一個(gè)格子
  vis[t]=true;
 }
 for(int i=0; i<=x-2-i; i++)
 {
  int t=get_sg(i)^get_sg(x-i-2); //這一列的格子都涂
  vis[t]=true;
 }
 for(int i=0; ; i++)
 {
  if(!vis[i])
  {
   sg[x]=i;
   break;
  }
 }
 return sg[x];
}
int main()
{
 memset(sg, -1, sizeof(sg));
 sg[0]=0;
 for(int i=1; i<maxn; i++)
  sg[i]=get_sg(i);
 int t;
 scanf("%d", &t);
 for(int cas=1; cas<=t; cas++)
 {
  int n, m;
  scanf("%d%d", &n, &m);
  memset(pl, false, sizeof(pl));
  int ans=0;
  for(int i=1; i<=m; i++)
  {
   int x, y;
   scanf("%d%d", &x, &y);
   pl[--x][--y]=true; 
  }
  int cnt=0;
  for(int i=0; i<n; i++) //將格子分區(qū)
  {
   if(pl[0][i]&&pl[1][i])  //如果某一列的格子都涂了,那么異或這一列格子之前的連續(xù)空格子的sg值
   {
    ans^=sg[cnt];
    cnt=0;
    continue;
   }
   if(pl[0][i]^pl[1][i]) //如果這一列之涂了一個(gè)格子,那么異或這一列格子之前的連續(xù)空格子的sg值再異或1
   {
    ans=ans^sg[cnt]^1;
    cnt=0;
    continue;
   }
   cnt++;  //如果這一列沒(méi)有格子被涂,那么連續(xù)空格子的長(zhǎng)度+1
  }
  ans^=sg[cnt];
  if(ans)
   printf("Case %d: Alice\n", cas);
  else
   printf("Case %d: Bob\n", cas);
 }
 return 0;
}

以上就是本文的全部?jī)?nèi)容,希望對(duì)大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。

相關(guān)文章

  • C++如何獲取本機(jī)的IP地址

    C++如何獲取本機(jī)的IP地址

    這篇文章主要為大家詳細(xì)介紹了C++如何獲取本機(jī)IP地址小程序,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2018-01-01
  • 在C語(yǔ)言中比較兩個(gè)字符串是否相等的方法

    在C語(yǔ)言中比較兩個(gè)字符串是否相等的方法

    這篇文章主要介紹了在C語(yǔ)言中比較兩個(gè)字符串是否相等的方法,分別介紹了strcmp()函數(shù)和strcasecmp()函數(shù),注意功能區(qū)分,需要的朋友可以參考下
    2015-08-08
  • C C++ LeetCode題解在二叉樹(shù)中增加一行示例詳解

    C C++ LeetCode題解在二叉樹(shù)中增加一行示例詳解

    這篇文章主要為大家介紹了C C++ LeetCode題解在二叉樹(shù)中增加一行示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-10-10
  • C++實(shí)現(xiàn)圖書(shū)館系統(tǒng)

    C++實(shí)現(xiàn)圖書(shū)館系統(tǒng)

    這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)圖書(shū)館系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • 讓?xiě)?yīng)用程序只運(yùn)行一個(gè)實(shí)例的實(shí)現(xiàn)方法

    讓?xiě)?yīng)用程序只運(yùn)行一個(gè)實(shí)例的實(shí)現(xiàn)方法

    我們?cè)谑褂谩?60軟件管家》時(shí)發(fā)現(xiàn),在《360軟件管家》已經(jīng)運(yùn)行了的情況下,再次點(diǎn)擊《360軟件管家》的圖標(biāo),那么它不會(huì)再運(yùn)行另外一個(gè)《360軟件管家》,而是將已有的《360軟件管家》給激活,始終只能運(yùn)行一個(gè)《360軟件管家》的實(shí)例
    2013-05-05
  • OpenCV實(shí)現(xiàn)雙邊濾波算法

    OpenCV實(shí)現(xiàn)雙邊濾波算法

    這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)雙邊濾波算法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-10-10
  • OpenCV中Grabcut算法的具體使用

    OpenCV中Grabcut算法的具體使用

    本文主要介紹了OpenCV中Grabcut算法的具體使用,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2022-08-08
  • C語(yǔ)言實(shí)現(xiàn)俄羅斯方塊課程設(shè)計(jì)

    C語(yǔ)言實(shí)現(xiàn)俄羅斯方塊課程設(shè)計(jì)

    這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)俄羅斯方塊課程設(shè)計(jì),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2021-06-06
  • C++使用TinyXml實(shí)現(xiàn)讀取XMl文件

    C++使用TinyXml實(shí)現(xiàn)讀取XMl文件

    常見(jiàn)C/C++?XML解析器有Tinyxml、XERCES、squashxml、xmlite、pugxml、libxml等等,本文為大家介紹的是使用TinyXml實(shí)現(xiàn)讀取XMl文件,需要的可以參考一下
    2023-06-06
  • 基于C++自制屠夫躲貓貓小游戲

    基于C++自制屠夫躲貓貓小游戲

    這篇文章主要為大家詳細(xì)介紹了如何基于C++自制屠夫躲貓貓小游戲,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2024-01-01

最新評(píng)論