bnu Game 博弈。
2024-08-25 22:27:54
Game
Time Limit: 10000ms
Case Time Limit: 10000ms
Memory Limit: 65536KB
64-bit integer IO format: %lld Java class name: Main
Alice and Bob invented a new game again, as they usually did.
The rule of the new game is quite simple. There is an n*n matrix and at the very beginning of the game, some of ceil contain stone, and others contain nothing. Then they take turns (Alice first) to play the game.
Each time one person should choose two empty ceils which are on the same line, and the number of their columns’ difference is exactly 2(which means the absolute value of difference is 2). And then the people should put stones on each of the two ceil. The game ends when one people cannot do the operation above and thus lose the game.
Here's the problem: Who will win the game if both use the best strategy? Find it out quickly, before they get bored of the game again!
Input
The first line contains a single integer T, indicating the number of test cases.
The first line of each test case contains an integer n (1<=n<=1000), and n lines follow. Each line contains n integers 0 or 1, which means there exist a stone or not (1 means exist).
The first line of each test case contains an integer n (1<=n<=1000), and n lines follow. Each line contains n integers 0 or 1, which means there exist a stone or not (1 means exist).
Output
For each test case, output the case number first, then “Alice” if Alice will win otherwise output “Bob”.
Sample Input
2
3
0 0 0
0 0 0
1 0 0
4
0 0 0 1
1 0 1 0
1 1 1 1
1 0 1 0
3
0 0 0
0 0 0
1 0 0
4
0 0 0 1
1 0 1 0
1 1 1 1
1 0 1 0
Sample Output
Case 1: Bob
Case 2: Alice
Case 2: Alice
这道题,是一道博弈题。
每一行是可以单独考虑的,这个是很好理解的。
奇数和偶数行也是可以单独考虑的。推一推。
"1"的存在,用来分割他们进行讨论。
题目的转化为 n 堆石头子,每次从每一堆取出2个连续堆的方案。
这里就简单了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std; int SG[];
bool use[];
void prepare()
{
int i,j;
SG[]=;SG[]=;
for(i=;i<=;i++)
{
memset(use,false,sizeof(use));
for(j=;j<i;j++)
{
use[ (SG[j-] ^ SG[i-j-]) ]=true;
}
for(j=;;j++)
if(use[j]==false)
{
SG[i]=j;
break;
}
}
}
int main()
{
int T,n,ans[],t;
int i,j,x,XOR;
prepare();
scanf("%d",&T);
for(t=;t<=T;t++)
{
scanf("%d",&n);
XOR=;
for(i=;i<=n;i++)
{
ans[]=;ans[]=;
for(j=;j<=n;j++)
{
scanf("%d",&x);
if(x==)
ans[j%]++;
else
{
XOR=XOR^SG[ans[j%]];
ans[j%]=;
}
}
XOR=XOR^SG[ans[]];
XOR=XOR^SG[ans[]];
}
printf("Case %d: ",t);
if(XOR==)
printf("Bob\n");
else printf("Alice\n");
}
return ;
}
SG[ ] 使用map。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
using namespace std; int SG[];
map<int,int>Q;
void prepare()
{
int i,j,k,s;
SG[]=;SG[]=;
for(i=;i<=;i++)
{
while(!Q.empty())
{
Q.clear();
}
for(s=,j=;j<i;j++)
{
k=(SG[j-] ^ SG[i-j-]);
Q[k]=s++;
}
for(j=;;j++)
if(Q.find(j)==Q.end())
{
SG[i]=j;
break;
}
}
}
int main()
{
int T,n,ans[],t;
int i,j,x,XOR;
prepare();
scanf("%d",&T);
for(t=;t<=T;t++)
{
scanf("%d",&n);
XOR=;
for(i=;i<=n;i++)
{
ans[]=;ans[]=;
for(j=;j<=n;j++)
{
scanf("%d",&x);
if(x==)
ans[j%]++;
else
{
XOR=XOR^SG[ans[j%]];
ans[j%]=;
}
}
XOR=XOR^SG[ans[]];
XOR=XOR^SG[ans[]];
}
printf("Case %d: ",t);
if(XOR==)
printf("Bob\n");
else printf("Alice\n");
}
return ;
}
最新文章
- 【ORACLE】MD5加密
- Equls 和==的区别
- Hibernate创建hqll时报错
- git分支使用
- NIO与传统IO的区别
- 42.JTAG接口使用注意
- POJ3034+DP
- EF 的 霸气配置
- 【转】“/usr/bin/ld: cannot find -lz”
- Yii 多表关联relations,需要与with()方法联合使用
- DbConnectionFactory 数据库连接
- libsvm中的dec_values以及分类结果评分问题
- 数据结构学习之栈求解n皇后问题
- Java+selenium之WebDriver的常用方法封装(八)
- ABOUT ME/OI回忆录
- seo 基础
- tomcat限制ip访问
- 会话追踪(session tracking)
- GLSL 内建函数
- jquery在IE8上使用find的问题