2020CCPC綿陽站Game of Cards （SG函式）
- 題目描述
- 思路
- 代碼
題目描述
小兔子和小馬喜歡玩奇怪的紙牌游戲，現在，他們正在玩一種叫做0123游戲的紙牌游戲，桌子上有幾張牌，其中c0標記為0，c1標記為1，c2標記為2，c3標記為3，小兔子和小馬輪流玩游戲，小兔子先走，在每一回合中，玩家應選擇兩張牌，條件是兩張牌上的數字之和不超過3，然后將這兩張牌換成標有其和的牌，不能移動的玩家將輸掉比賽，小兔子和小馬在想誰會贏這場比賽，（百度翻譯）
思路
找出必敗態：
- c0 == 0 && c1 ==0
- c0 == 1 && c1 == 0 && c2 == 0 && c3 == 0
- c1 == 1 && c0 == 0 && c2 == 0
然后，SG函式打表，
代碼
#include<bits/stdc++.h>
#define ll long long
#define ms(x,a) memset(x,a,sizeof(x))
using namespace std;
int sg(int c0,int c1,int c2,int c3) //1必勝 -1必敗
{
if(c0 == 0 && c1 == 0) //只有c2,c3必敗
return -1;
if(c0 == 1 && c1 == 0 && c2 == 0 && c3 == 0) //只有一張0必敗
return -1;
if(c1 == 1 && c0 == 0 && c2 == 0) //只有一張1必敗
return -1;
int f = 1;
if(c0 > 0) //一張0和其他任意一張牌組合
{
f = min(f,sg(c0 - 1,c1,c2,c3));
}
if(c1 >= 2) //用一張2替換兩張1
f = min(f,sg(c0,c1 - 2,c2 + 1,c3));
if(c1 > 0 && c2 > 0) //用一張3替換一張1和一張2
f = min(f,sg(c0,c1 - 1,c2 - 1,c3 + 1));
if(f == -1) //后繼存在必敗，當前必勝；否則，必敗
return 1;
return -1;
}
int ck(ll c0,ll c1,ll c2,ll c3)
{
if(c0 == c1 && c1 == c2 && c2 == c3 && c3 == 0)
{
return -1;
}
else
{
int f = 1;
if(c3 == 0)
{
if(c1 == 0 && c2 == 0)
{
if(c0 == 0 || c0 % 2)
{
f = -1;
}
}
else
{
if(c0 % 2 == 0)
{
if(c1 % 3 == 0)
{
f = -1;
}
else
{
if(c1 % 3 == 1 && c2 == 0)
{
f = -1;
}
}
}
else
{
if(c1 % 3 == 1 && c2 > 0)
{
f = -1;
}
else if(c1 % 3 == 2 && c2 <= 1)
{
f = -1;
}
}
}
}
else
{
if(c0 % 2 == 0)
{
if(c1 % 3 == 0)
{
f = -1;
}
else
{
if(c1 % 3 == 1 && c2 == 0)
{
f = -1;
}
}
}
else
{
if(c1 % 3 == 1 && c2 > 0)
{
f = -1;
}
else if(c1 % 3 == 2 && c2 <= 1)
{
f = -1;
}
}
}
return f;
}
}
int main()
{
int t;
scanf("%d",&t);
for(int ca = 1; ca <= t; ++ca)
{
ll c0,c1,c2,c3;
scanf("%lld%lld%lld%lld",&c0,&c1,&c2,&c3);
printf("Case #%d: ",ca);
if(ck(c0,c1,c2,c3) == 1)
{
puts("Rabbit");
}
else
{
puts("Horse");
}
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/202143.html
標籤：其他
上一篇：c語言掃雷簡化版小游戲