51nod Bash游戏(V1,V2,V3,V4(斐波那契博弈))
A B两个人轮流拿。A先拿。每次最少拿1颗。最多拿K颗。拿到最后1颗石子的人获胜。如果A B都很聪明,拿石子的过程中不会出现失误。给出N和K,问最后谁能赢得比赛。
第1行:一个数T。表示后面用作输入測试的数的数量。(1 <= T <= 10000)
第2 - T + 1行:每行2个数N,K。中间用空格分隔。(1 <= N,K <= 10^9)
共T行。假设A获胜输出A,假设B获胜输出B。
4
3 2
4 2
7 3
8 3
B
A
A
B
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std; int main()
{
int n,k,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&k);
if(n%(k+1))
printf("A\n");
else
printf("B\n");
}
return 0;
}
A仅仅能拿1颗,所以B能够拿到最后1颗石子。
第1行:一个数T,表示后面用作输入測试的数的数量。(1 <= T <= 10000)
第2 - T + 1行:每行1个数N。(1 <= N <= 10^9)
共T行,假设A获胜输出A。假设B获胜输出B。
3
2
3
4
B
A
A
const int maxn=45;
bool vis[maxn];
int sg[maxn];
int a[5]={1,3,4};
void sgs()
{
for(int i=0;i<maxn;i++)
{
memset(vis,false,sizeof(vis));
for(int j=0;j<3;j++)
{
if(i>=a[j])
vis[sg[i-a[j]]]=true;
}
for(int j=0;;j++)
{
if(!vis[j])
{
sg[i]=j;
break;
}
}
printf("%d %d\n",i,sg[i]);
}
}
通过打表发现,7的整数倍和n%7==2的是必败态。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std; int main()
{
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
if(n%7==0||n%7==2)
printf("B\n");
else
printf("A\n");
}
return 0;
}
如果A B都很聪明,拿石子的过程中不会出现失误。给出N。问最后谁能赢得比赛。
A仅仅能拿1颗或2颗,所以B能够拿到最后1颗石子。(输入的N可能为大数)
第1行:一个数T,表示后面用作输入測试的数的数量。 (1 <= T <= 1000)
第2 - T + 1行:每行1个数N。 (1 <= N <= 10^1000)
共T行。假设A获胜输出A,假设B获胜输出B。
3
2
3
4
A
B
A
const int maxn=1000+100;
int sg[maxn];
bool vis[maxn];
int main()
{
for(int i=0;i<50;i++)
{
memset(vis,false,sizeof(vis));
for(int j=0;(1<<j)<=i;j++)
{
int s=i-(1<<j);
vis[sg[s]]=true;
}
for(int j=0;;j++)
{
if(!vis[j])
{
sg[i]=j;
break;
}
}
printf("%d ",sg[i]);
}
return 0;
}
发现仅仅要是3的整数倍就能够。
证明:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
char s[maxn];
int main()
{
int t;
scanf("%d",&t);
while(t--)
{
scanf("%s",s);
int n=strlen(s);
int ans=0;
for(int i=0;i<n;i++)
{
ans=ans+(s[i]-'0');
}
if(ans%3)
printf("A\n");
else
printf("B\n");
}
return 0;
}
A仅仅能拿1颗或2颗,所以B能够拿到最后1颗石子。
第1行:一个数T,表示后面用作输入測试的数的数量。 (1 <= T <= 1000)
第2 - T + 1行:每行1个数N。(1 <= N <= 10^9)
共T行,假设A获胜输出A,假设B获胜输出B。
3
2
3
4
B
B
A
这个游戏叫做Fibonacci Nim,肯定和Fibonacci数列:f[n]:1,2,3,5,8,13,21,34,55,89,… 有密切的关系。假设试验一番之后,能够推測:先手胜当且仅当n不是Fibonacci数。
换句话说。必败态构成Fibonacci数列。
这里须要借助“Zeckendorf定理”(齐肯多夫定理):不论什么正整数能够表示为若干个不连续的Fibonacci数之和。
先看看FIB数列的必败证明:
1、当i=2时。先手仅仅能取1颗,显然必败,结论成立。
2、如果当i<=k时。结论成立。
则当i=k+1时,f[i] = f[k]+f[k-1]。
则我们能够把这一堆石子看成两堆,简称k堆和k-1堆。
(一定能够看成两堆,由于假如先手第一次取的石子数大于或等于f[k-1],则后手能够直接取完f[k],由于f[k] < 2*f[k-1])
对于k-1堆。由如果可知,不论先手如何取,后手总能取到最后一颗。以下我们分析一下后手最后取的石子数x的情况。
假设先手第一次取的石子数y>=f[k-1]/3。则这小堆所剩的石子数小于2y。即后手能够直接取完。此时x=f[k-1]-y,则x<=2/3*f[k-1]。
我们来比較一下2/3*f[k-1]与1/2*f[k]的大小。即4*f[k-1]与3*f[k]的大小,由数学归纳法不难得出,后者大。
所以我们得到,x<1/2*f[k]。
即后手取完k-1堆后。先手不能一下取完k堆,所以游戏规则没有改变,则由如果可知,对于k堆,后手仍能取到最后一颗,所以后手必胜。
即i=k+1时。结论依旧成立。
对于不是FIB数,首先进行分解。
分解的时候,要取尽量大的Fibonacci数。
比方分解85:85在55和89之间。于是能够写成85=55+30,然后继续分解30,30在21和34之间,所以能够写成30=21+9,
依此类推,最后分解成85=55+21+8+1。
则我们能够把n写成 n = f[a1]+f[a2]+……+f[ap]。
(a1>a2>……>ap)
我们令先手先取完f[ap],即最小的这一堆。因为各个f之间不连续。则a(p-1) > ap + 1,则有f[a(p-1)] > 2*f[ap]。即后手仅仅能取f[a(p-1)]这一堆,且不能一次取完。
此时后手相当于面临这个子游戏(仅仅有f[a(p-1)]这一堆石子。且后手先取)的必败态。即先手一定能够取到这一堆的最后一颗石子。
同理可知。对于以后的每一堆,先手都能够取到这一堆的最后一颗石子,从而获得游戏的胜利。
代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn=50;
long long f[50];
int main()
{
f[1]=1,f[2]=2;
for(int i=3;i<maxn;i++)
f[i]=f[i-1]+f[i-2];
int t;
scanf("%d",&t);
while(t--)
{
int n;
scanf("%d",&n);
int sign=1;
for(int i=1;i<maxn;i++)
{
if(f[i]>n)
break;
if(f[i]==n)
{
sign=0;
break;
}
}
if(sign)
printf("A\n");
else
printf("B\n");
}
return 0;
}
最新文章
- JavaScript数据类型 typeof, null, 和 undefined
- sprint3个人总结
- (斐波那契总结)Write a method to generate the nth Fibonacci number (CC150 8.1)
- CSS DIV 独占一行,清除左右两边的浮动
- 最全的前端开发面试题及答案(js,css等等)
- POJ 2387 Til the Cows Come Home --最短路模板题
- 设置button不同状态下的背景色,即把这个颜色变成图片设置成,背景图片
- Uploadify在MVC中使用方法案例(上传单张图片)
- .NET中 MEF应用于IOC
- Android GradientDrawable类的详解,设置activity的背景颜色渐变效果
- centos升级python到2.7
- Thinkphp中distinct的用法
- keepalived+mysql双主复制高可用方案
- php 学习笔记 数组1
- 【集美大学1411_助教博客】团队作业1——团队展示&;选题 成绩
- GDB 资料汇总
- Web Service入门简介(一个简单的WebService示例)
- 32.Mysql Cluster
- Jmeter接口测试——跨线程组调用参数(token为例)
- Power BI 与 Azure Analysis Services 的数据关联:3、还原备份文件到Azure Analysis Services
热门文章
- 转:IOS的推送。是一个强大的功能
- [易飞]一张领料单单身仓库&;quot;飞了&;quot;引起的思考
- Android 学习笔记之Bitmap位图的缩放
- Material Design控件使用学习 toolbar+drawerlayout+ Snackbar
- Elasticsearch之REST
- Kinect 开发 —— 面部追踪
- C语言-常量指针与指针常量
- POJ 1061 青蛙的约会 数论水题
- Myeclipse学习总结(2)——MyEclipse快捷键大全
- Spring中提供的集合工具类util CollectionUtils