本文主要是介绍UVa Live 7278 - Game of Cards 博弈,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目传送门:https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=701&page=show_problem&problem=5330
n堆牌,每个牌上有数字1到10,每次可以先取0到k个牌不等,再取最上面的卡片的编号数量的牌,不能取的人失败。
sg函数暴力推理。
找不到规律的时候,暴力试试,大力出奇迹。
#include <cstdio>
#include <iostream>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <bitset>
#define mem0(a) memset(a,0,sizeof(a))
#define meminf(a) memset(a,0x3f,sizeof(a))
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxn=1005,inf=0x3f3f3f3f;
const ll llinf=0x3f3f3f3f3f3f3f3f;
const ld pi=acos(-1.0L);
int a[1005],sg[1005];
int k;int getsg(int top) {if (sg[top]!=-1) return sg[top];bool visit[1005];mem0(visit);for (int i=0;i<=min(k,top-1);i++) {if (top-i-a[top-i]>=0) visit[getsg(top-i-a[top-i])]=1;}for (int i=0;;i++) {if (!visit[i]) {sg[top]=i;return i;}}
}int main() {int i,n,cas,sum=0;scanf("%d%d",&cas,&k);while (cas--) {scanf("%d",&n);for (i=1;i<=n;i++) {scanf("%d",&a[i]);}memset(sg,-1,sizeof(sg));sg[0]=0;int ans=getsg(n);sum=sum^ans;}if (sum) printf("Alice can win.\n"); else printf("Bob will win.\n");return 0;
}
这篇关于UVa Live 7278 - Game of Cards 博弈的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!