https://vjudge.net/problem/HDU-3980
题意: 两个人在一个由 n 个玻璃珠组成的一个圆环上玩涂色游戏,游戏的规则是:
1、每人一轮,每轮选择一个长度为 m 的连续的、没有涂过色的玻璃珠串涂色
2、不能涂色的那个人输掉游戏
题解:第一个人涂色之后就把环变成了一个长度为 n-m 的链。
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
int fx[1010],g[1010];;
int n,m;
void init()
{
memset(fx,0,sizeof(fx));
fx[m]=1;
for(int i=m+1;i<=n;i++)
{
memset(g,0,sizeof(g));
for(int k=m;k<=i;k++)
{
int t=fx[k-m]^fx[i-k];
g[t]=1;
}
for(int j=0;j<=n;j++)
if(!g[j])
{
fx[i]=j;
break;
}
}
}
int main()
{
int t;
scanf("%d",&t);
int cas=0;
while(t--)
{
scanf("%d%d",&n,&m);
init();
printf("Case #%d: ",++cas);
if(fx[n-m]||n<m) printf("abcdxyzk\n");
else printf("aekdycoin\n");
}
return 0;
}
https://vjudge.net/problem/POJ-3537
题意:在1*n的方格表中两人轮流画‘x’,谁先让三个‘x’连在一起,谁胜。
题解:在第i个位置放一个X,即可分为两个子游戏,i-3和n-i-2
#include<cstdlib>
#include<stdio.h>
#include<string.h>
using namespace std;
int fx[2010],g[2010];;
int n;
void init()
{
memset(fx,0,sizeof(fx));
fx[1]=fx[2]=fx[3]=fx[4]=fx[5]=1;
for(int i=6;i<=2000;i++)
{
memset(g,0,sizeof(g));
g[fx[i-3]]=g[fx[i-4]]=g[fx[i-5]]=1;
//在位置1,2,3放置时,只能分解为长度为i-3,i-4,i-5的一个区间。
for(int j=1;j<=i-(j+5);j++)
{
//设j为分解后的左区间长度,则i-(j+5)为分解后的右区间长度。
//保证左区间<=右区间,避免重复计算。
g[fx[j]^fx[i-(j+5)]]=1;
}
for(int j=0;;j++)
if(!g[j])
{
fx[i]=j;
break;
}
}
}
int main()
{
init();
while(scanf("%d",&n)!=EOF)
{
if(fx[n]) puts("1");
else puts("2");
}
return 0;
}
https://vjudge.net/problem/HDU-1536
题意:输入K表示一个集合的大小,之后输入集合表示对于这对石子只能去这个集合中的元素个数。输入一个m表示接下来对于这个集合要进行m次询问。接下来m行 每行输入一个n,表示有n个堆,每堆有ni个石子,问这一行所表示的状态是赢还是输 如果赢输出W否则L
#include <cstdio>
#include<string.h>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=10010;
int fx[maxn],step[110],num;
int getSG(int val)
{
if(fx[val]!=-1) return fx[val];
int g[110];
memset(g,0,sizeof(g));
for(int j=0;j<num;j++)
{
if(val>=step[j]) {
getSG(val-step[j]);
g[fx[val-step[j]]]=1;
}
}
for(int j=0;j<=val;j++)
{
if(!g[j]) {
return fx[val]=j;
}
}
}
int main()
{
int n,m,tmp,res;
while(scanf("%d",&num)!=EOF,num)
{
for(int i=0;i<num;i++)
{
scanf("%d",step+i);
}
sort(step,step+num);
scanf("%d",&m);
memset(fx,-1,sizeof(fx));
while(m--)
{
scanf("%d",&n);
res=0;
for(int i=0;i<n;i++)
{
scanf("%d",&tmp);
res^=getSG(tmp);
}
if(!res) printf("L");
else printf("W");
}
printf("\n");
}
return 0;
}
https://vjudge.net/problem/HDU-1848
题意:
1、 这是一个二人游戏;
2、 一共有3堆石子,数量分别是m, n, p个;
3、 两人轮流走;
4、 每走一步可以选择任意一堆石子,然后取走f个;
5、 f只能是菲波那契数列中的元素(即每次只能取1,2,3,5,8…等数量);
6、 最先取光所有石子的人为胜者;
#include <cstdio>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1010;
int fx[maxn];
int fibo[16]={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987};
int main()
{
memset(fx,0,sizeof(fx));
for(int i=0;i<=1000;i++)
{
int g[maxn];
memset(g,0,sizeof(g));
for(int j=0;fibo[j]<=i&&j<15;j++)
{
g[fx[i-fibo[j]]]=1;
}
for(int j=0;j<=i;j++)
{
if(!g[j]){
fx[i]=j;
break;
}
}
}
int m,n,p;
while(scanf("%d%d%d",&n,&m,&p)!=EOF,m+n+p)
{
int res=0;
res^=fx[n];
res^=fx[m];
res^=fx[p];
if(!res) printf("Nacci\n");
else printf("Fibo\n");
}
return 0;
}
#include <cstdio>
#include<string.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=1010;
int fx[maxn],g[maxn];
int fibo[16]={1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987};
int getSG(int n)
{
if(fx[n]!=-1) return fx[n];
int g[110];
memset(g,0,sizeof(g));
for(int i=0;i<=15&&fibo[i]<=n;i++)
{
getSG(n-fibo[i]);
g[fx[n-fibo[i]]]=1;
}
for(int i=0;i<=n;i++)
{
if(!g[i])
{
return fx[n]=i;
}
}
}
int main()
{
memset(fx,-1,sizeof(fx));
int m,n,p;
while(scanf("%d%d%d",&n,&m,&p)!=EOF,m+n+p)
{
int res=0;
res^=getSG(n);
res^=getSG(m);
res^=getSG(p);
if(!res) printf("Nacci\n");
else printf("Fibo\n");
}
return 0;
}
http://blog.csdn.net/qinmusiyan/article/details/8016033
https://vjudge.net/problem/HDU-1517
题意:2 个人玩游戏,给定一个数n,从 1 开始,轮流对数进行累乘一个数(2~9中取),
第一次大于等于n的人赢。
题解:P/N分析。
必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。
必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。
步骤1:将所有终结位置标记为必败点(P点);(终结位置指的是不能将游戏进行下去的位置)
步骤2:将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)
步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ;
步骤4:如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。
P/N分析 Version
#include <cstdio>
#include<string.h>
using namespace std;
int getSG(long long val,long long targe)
{
if(val>=targe) return 0;//必败点
if(val*2>=targe) return 1;//必胜点
for(int i=9;i>=2;i--)
{
if(getSG(val*i,targe)==0) return 1;
}
return 0;
}
int main()
{
long long n;
while(scanf("%lld",&n)!=EOF)
{
printf(getSG(1,n)?"Stan wins.\n":"Ollie wins.\n");
}
return 0;
}
一般规律
#include<stdio.h>
int main()
{
double n;
while(scanf("%lf",&n)!=EOF)
{
while(n>18) n/=18;
printf(n<=9?"Stan wins.\n":"Ollie wins.\n");
}
return 0;
}
https://vjudge.net/problem/HDU-1079
题意:亚当和夏娃玩一个游戏,给定一个开始时间y-m-d,轮流进行操作,谁先到达2001-11-4,谁就获胜。每次操作可以前进一天y-m-d+1或者前进一个月y-m+1-d,前进的时间必须合法(在2001-11-4之前且日期合法)。亚当先走,亚当获胜输出YES,否则输出NO。
题解:P/N分析
方法一:
#include <cstdio>
#include<string.h>
using namespace std;
const int YEAR=2100,MONTH=13,DAY=32;
int fx[YEAR][MONTH][DAY];
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool isLeap(int y){
if(y%400==0||(y%100!=0&&y%4==0))return true;
return false;
}
void getNextDate(int &y,int &m,int &d)
{
if(isLeap(y)&&m==2){
d++;
if(d==30){
m=3;
d=1;
}
}
else{
d++;
if(d>month[m])
{
m++;
d=1;
if(m>12){
y++;
m=1;
}
}
}
}
bool isGood(int y,int m,int d)
{
if(m>12||m<1||d>31||d<1||y>2001) return false;
if(y==2001)
{
if(m>11) return false;
else if(m==11){
if(d>4) return false;
}
}
if(isLeap(y)&&m==2)
{
return d<=month[m]+1;
}
else return d<=month[m];
}
void getNextMonth(int &y,int &m,int &d)
{
m++;
if(m>12){
y++;
m=1;
}
}
int getSG(int y,int m,int d)
{
if(fx[y][m][d]!=-1) return fx[y][m][d];
if(y==2001&&m==11&&d==4) return fx[y][m][d]=0;//必败点
else if(y==2001&&m==10&&d==4) return fx[y][m][d]=1;//必胜点
else if(y==2001&&m==11&&d==3) return fx[y][m][d]=1;
//第一个分支
int curry=y,currm=m,currd=d;
getNextDate(curry,currm,currd);
if(isGood(curry,currm,currd)&&getSG(curry,currm,currd)==0) return fx[y][m][d]=1;
//第二个分支
curry=y;currm=m;currd=d;
getNextMonth(curry,currm,currd);
if(isGood(curry,currm,currd)&&getSG(curry,currm,currd)==0) return fx[y][m][d]=1;
//两种走的方法都没能赢,则说明自己输
return fx[y][m][d]=0;
}
int main()
{
int t,y,m,d;
scanf("%d",&t);
memset(fx,-1,sizeof(fx));
while(t--)
{
scanf("%d%d%d",&y,&m,&d);
if(getSG(y,m,d)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
方法二:
#include <cstdio>
#include<string.h>
using namespace std;
const int YEAR=2100,MONTH=13,DAY=32;
int fx[YEAR][MONTH][DAY];
int month[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
bool isLeap(int y){
if(y%400==0||(y%100!=0&&y%4==0))return true;
return false;
}
void getNextDate(int &y,int &m,int &d)
{
if(isLeap(y)&&m==2){
d++;
if(d==30){
m=3;
d=1;
}
}
else{
d++;
if(d>month[m])
{
m++;
d=1;
if(m>12){
y++;
m=1;
}
}
}
}
bool isGood(int y,int m,int d)
{
if(m>12||m<1||d>31||d<1) return false;
if(isLeap(y)&&m==2)
{
return d<=month[m]+1;
}
else return d<=month[m];
}
void getNextMonth(int &y,int &m,int &d)
{
m++;
if(m>12){
y++;
m=1;
}
}
int getSG(int y,int m,int d)
{
if(fx[y][m][d]!=-1) return fx[y][m][d];
//如果自己面对布局(2001,11,4),说明对手已经走到了(2001,11,4),自己必败
if(y==2001&&m==11&&d==4) return fx[y][m][d]=0;
//如果自己面对超过(2001,11,4)的日期,则自己赢
else if(y>2001) return fx[y][m][d]=1;
else if(y==2001&&m>11) return fx[y][m][d]=1;
else if(y==2001&&m==11&&d>4) return fx[y][m][d]=1;
//第一个分支
int curry=y,currm=m,currd=d;
getNextDate(curry,currm,currd);
if(getSG(curry,currm,currd)==0) return fx[y][m][d]=1;
//第二个分支
curry=y;currm=m;currd=d;
getNextMonth(curry,currm,currd);
if(isGood(curry,currm,currd)&&getSG(curry,currm,currd)==0) return fx[y][m][d]=1;
//两种走的方法都没能赢,则说明自己输
return fx[y][m][d]=0;
}
int main()
{
int t,y,m,d;
scanf("%d",&t);
memset(fx,-1,sizeof(fx));
while(t--)
{
scanf("%d%d%d",&y,&m,&d);
if(getSG(y,m,d)) printf("YES\n");
else printf("NO\n");
}
return 0;
}
https://vjudge.net/problem/HDU-2147
题意:给你n*m表格,初始在右上角,每次在上个人移动后的基础上移动一步(向左or向下or向左下),先到左下角则获胜。
题解:先用P/N分析,然后得出规律:n,m都为奇数时,先手输;否则,后手输。
#include <cstdio>
using namespace std;
int to[3][2]={{1,-1},{0,-1},{1,0}};
int n,m;
bool isGood(int x,int y)
{
if(x<1||x>n||y<1||y>m) return false;
return true;
}
int getSG(int x,int y)
{
if(x==n&&y==1) return 0;
if(x==n-1&&y==1||x==n&&y==2||x==n-1&&y==2) return 1;
for(int i=0;i<3;i++)
{
if(isGood(x+to[i][0],y+to[i][1])&&getSG(x+to[i][0],y+to[i][1])==0) return 1;
}
return 0;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF,n+m)
{
/*
if(getSG(1,m)) printf("Wonderful!\n");
else printf("What a pity!\n");
*/
if( n&1&&m&1) printf("What a pity!\n");
else printf("Wonderful!\n");
}
return 0;
}
https://vjudge.net/problem/HDU-1404
题意:一串由0~9组成的数字,可以进行两个操作:
(1)把其中一个数变为比它小的数;(2)把其中一个数字0及其右边的所以数字删除。
两人轮流进行操作,最后把所以数字删除的人获胜,问前者胜还是后者胜。字符串长度为1-6,前者胜输出Yes,否则输出No.
#include<cstdio>
#include<cstring>
#include<string.h>
#include<iostream>
using namespace std;
const int MAXN=1000000;
int sg[MAXN];
int length(int n)//得到的整数的位置
{
int sum=0;
while(n)
{
sum++;
n/=10;
}
return sum;
}
int fastPow(int a,int b)
{
int res=1;
while(b)
{
if(b&1) res=res*a;
b>>=1;
a=a*a;
}
return res;
}
void fun(int n)//假设sg[n]=0;则为P态;则所有一步可以变为n的都是N态;
{
int len=length(n);
int sum=0;
for(int i=1;i<=len;i++)
{
int tmp=n,m=n;
for(int j=1;j<i;j++)
tmp/=10;
int base=fastPow(10,i-1);
tmp=tmp%10;
for(int j=1;j<=9-tmp;j++)
{
// cout<<m+j*base<<endl;
sg[m+j*base]=1;
sum++;
}
}
if(len<6)
{
int t=6-len,m=n;
for(int i=1;i<=t;i++)
{
m*=10;
int val=fastPow(10,i-1);
for(int j=0;j<val;j++)
{
sg[m+j]=1;
// cout<<m+j<<endl;
sum++;
}
}
}
// cout<<sum<<endl;
}
void getSG()
{
memset(sg,0,sizeof(sg));
sg[0]=1;
for(int i=1;i<MAXN;i++)
{
if(!sg[i]){
fun(i);
}
}
}
int toInt(char *ss)
{
int len=strlen(ss);
int res=0;
for(int i=0;i<len;i++)
res=res*10+(ss[i]-'0');
return res;
}
int main()
{
getSG();
char str[8];
int n;
while(scanf("%s",str)!=EOF)
{
if(str[0]=='0') {
printf("Yes\n");
continue;
}
if(sg[toInt(str)]){
printf("Yes\n");
}
else printf("No\n");
}
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=3032
题意:Alice和Bob轮流取N堆石子,每堆S[i]个,Alice先,每一次可以从任意一堆中拿走任意个石子,也可以将一堆石子分为两个小堆。先拿完者获胜。
题解:先用SG函数打表发现规律。sg( 4k+1 ) = 4k+1; sg( 4k+2 ) = 4k+2; sg( 4k+3 ) = 4k+4; sg( 4k+4 ) = 4k+3。遗憾的是,自己的SG函数只有一个小地方错了,然后WA了好几次!
一个错误的打表:
void getSG()
{
memset(fx,0,sizeof(fx));
for(int i=0;i<100;i++)
{
memset(g,0,sizeof(g));
for(int j=1;j<=i;j++)
{
g[fx[i-j]]=1;
}
for(int j=1;j<=i-j;j++)
{
g[fx[j]^fx[i-j]]=1;
}
//这里写成j<=i,然后就错了!!!!循环不应该加条件限制,
//因为总有比i大的j,使得g[j]==0!!!
for(int j=0;j<=i;j++)
{
if(!g[j]){
fx[i]=j;
break;
}
}
printf("i:%d SG():%d\n",i,fx[i]);
}
}
正确的打表:
#include<cstdio>
#include<string.h>
using namespace std;
const int maxn=1000010;
int fx[maxn],g[maxn];
void getSG()
{
memset(fx,0,sizeof(fx));
for(int i=1;i<100;i++)
{
memset(g,0,sizeof(g));
for(int j=1;j<=i;j++)
{
g[fx[i-j]]=1;
}
for(int j=1;j<=i-j;j++)
{
g[fx[j]^fx[i-j]]=1;
}
for(int j=0;;j++)
{
if(!g[j]){
fx[i]=j;
break;
}
}
printf("i:%d SG():%d\n",i,fx[i]);
}
}
My Solution
#include<cstdio>
#include<string.h>
using namespace std;
int main()
{
int t,n,res,tmp,mod;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
res=0;
for(int i=0;i<n;i++)
{
scanf("%d",&tmp);
mod=tmp%4;
if(mod==3) res^=(tmp+1);
else if(mod==0) res^=(tmp-1);
else res^=tmp;
}
if(res) printf("Alice\n");
else printf("Bob\n");
}
return 0;
}
http://acm.hdu.edu.cn/showproblem.php?pid=3537
题意:已知一排硬币中有n个硬币正面朝上,输入正面朝上的硬币的位置ai。两人轮流操作,每次操作可以翻转1,2,或则3枚硬币,其中翻转的最右的硬币必须是正面朝上的,最后不能翻转的为负。
题解:有这样的结论:局面的SG 值为局面中每个正面朝上的棋子单一 存在时的SG 值的异或和。即一个有k个硬币朝上,朝上硬币位置 分布在的翻硬币游戏中,SG值是等于k个独立的开始时只有一个硬 币朝上的翻硬币游戏的SG值异或和。比如THHTTH这个游戏中,2号、 3号6号位是朝上的,它等价于TH、TTH、TTTTTH三个游戏和, 即sg[THHTTH]=sg[TH]sg[TTH]sg[TTTTTH].。用SG函数打表,发现sg[x]=2x或sg[x]=2x+1。其中,x的二进制数中1的个数为奇数时,sg[x]=2x;否则sg[x]=2x+1;
打表SG函数
const int maxn=1010;
int fx[maxn],g[maxn];
void getSG()
{
memset(fx,0,sizeof(fx));
for(int i=0;i<=100;i++)
{
memset(g,0,sizeof(g));
g[0]=1;//翻一个硬币,先手必赢,但没有分解成任何子局面,所以用0替代。
for(int j=0;j<i;j++)//翻两个硬币
{
g[fx[j]]=1;
}
for(int j=0;j<i;j++)//翻三个硬币
{
for(int k=0;k<j;k++)
{
g[fx[j]^fx[k]]=1;
}
}
for(int j=0;;j++)
{
if(!g[j])
{
fx[i]=j;
break;
}
}
printf("i:%d SG(): %d\n",i,fx[i]);
}
}
My Solution
#include<cstdio>
#include<string.h>
#include<set>
using namespace std;
int sumOfOne(int x)
{
int sum=0;
while(x)
{
if(x&1) sum++;
x>>=1;
}
return sum;
}
int main()
{
int n,tmp,res;
while(scanf("%d",&n)!=EOF)
{
set<int> ss;
res=0;
for(int i=0;i<n;i++)
{
scanf("%d",&tmp);
if(ss.find(tmp)==ss.end())
{
if(sumOfOne(tmp)&1) res^=tmp*2;
else res^=(tmp*2+1);
ss.insert(tmp);
}
}
if(res) printf("No\n");
else printf("Yes\n");
}
return 0;
}