https://vjudge.net/problem/HDU-3980
題意: 兩個人在一個由 n 個玻璃珠組成的一個圓環(huán)上玩涂色游戲掏膏,游戲的規(guī)則是:
1馒疹、每人一輪颖变,每輪選擇一個長度為 m 的連續(xù)的、沒有涂過色的玻璃珠串涂色
2腥刹、不能涂色的那個人輸?shù)粲螒?br>
題解:第一個人涂色之后就把環(huán)變成了一個長度為 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的一個區(qū)間梢褐。
for(int j=1;j<=i-(j+5);j++)
{
//設(shè)j為分解后的左區(qū)間長度旺遮,則i-(j+5)為分解后的右區(qū)間長度渤弛。
//保證左區(qū)間<=右區(qū)間依溯,避免重復(fù)計算。
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表示一個集合的大小须眷,之后輸入集合表示對于這對石子只能去這個集合中的元素個數(shù)鱼响。輸入一個m表示接下來對于這個集合要進行m次詢問鸣剪。接下來m行 每行輸入一個n筐骇,表示有n個堆,每堆有ni個石子告唆,問這一行所表示的狀態(tài)是贏還是輸 如果贏輸出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堆石子夏伊,數(shù)量分別是m, n, p個盯孙;
3歌溉、 兩人輪流走;
4、 每走一步可以選擇任意一堆石子,然后取走f個;
5识窿、 f只能是菲波那契數(shù)列中的元素(即每次只能取1肘迎,2,3,5加叁,8…等數(shù)量);
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 個人玩游戲系奉,給定一個數(shù)n,從 1 開始萌踱,輪流對數(shù)進行累乘一個數(shù)(2~9中取)咏闪,
第一次大于等于n的人贏稳诚。
題解:P/N分析。
必敗點(P點) :前一個選手(Previous player)將取勝的位置稱為必敗點。
必勝點(N點) :下一個選手(Next player)將取勝的位置稱為必勝點勒奇。
步驟1:將所有終結(jié)位置標(biāo)記為必敗點(P點)劈彪;(終結(jié)位置指的是不能將游戲進行下去的位置)
步驟2:將所有一步操作能進入必敗點(P點)的位置標(biāo)記為必勝點(N點)
步驟3:如果從某個點開始的所有一步操作都只能進入必勝點(N點) 滔吠,則將該點標(biāo)記為必敗點(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;
}
一般規(guī)律
#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
題意:亞當(dāng)和夏娃玩一個游戲馁蒂,給定一個開始時間y-m-d谁鳍,輪流進行操作,誰先到達2001-11-4澜掩,誰就獲勝。每次操作可以前進一天y-m-d+1或者前進一個月y-m+1-d蝙云,前進的時間必須合法(在2001-11-4之前且日期合法)氓皱。亞當(dāng)先走,亞當(dāng)獲勝輸出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),說明對手已經(jīng)走到了(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表格,初始在右上角抡医,每次在上個人移動后的基礎(chǔ)上移動一步(向左or向下or向左下)躲因,先到左下角則獲勝。
題解:先用P/N分析忌傻,然后得出規(guī)律:n,m都為奇數(shù)時大脉,先手輸;否則水孩,后手輸镰矿。
#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組成的數(shù)字,可以進行兩個操作:
(1)把其中一個數(shù)變?yōu)楸人〉臄?shù)俘种;(2)把其中一個數(shù)字0及其右邊的所以數(shù)字刪除秤标。
兩人輪流進行操作,最后把所以數(shù)字刪除的人獲勝宙刘,問前者勝還是后者勝苍姜。字符串長度為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)//得到的整數(shù)的位置
{
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)//假設(shè)sg[n]=0悬包;則為P態(tài)衙猪;則所有一步可以變?yōu)閚的都是N態(tài);
{
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函數(shù)打表發(fā)現(xiàn)規(guī)律。sg( 4k+1 ) = 4k+1预伺; sg( 4k+2 ) = 4k+2茫船; sg( 4k+3 ) = 4k+4琅束; sg( 4k+4 ) = 4k+3。遺憾的是算谈,自己的SG函數(shù)只有一個小地方錯了,然后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,然后就錯了H谎邸!?埂高每!循環(huán)不應(yīng)該加條件限制,
//因為總有比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。兩人輪流操作烤惊,每次操作可以翻轉(zhuǎn)1,2,或則3枚硬幣乔煞,其中翻轉(zhuǎn)的最右的硬幣必須是正面朝上的,最后不能翻轉(zhuǎn)的為負柒室。
題解:有這樣的結(jié)論:局面的SG 值為局面中每個正面朝上的棋子單一 存在時的SG 值的異或和渡贾。即一個有k個硬幣朝上,朝上硬幣位置 分布在的翻硬幣游戲中雄右,SG值是等于k個獨立的開始時只有一個硬 幣朝上的翻硬幣游戲的SG值異或和空骚。比如THHTTH這個游戲中,2號擂仍、 3號6號位是朝上的囤屹,它等價于TH、TTH防楷、TTTTTH三個游戲和牺丙, 即sg[THHTTH]=sg[TH]sg[TTH]sg[TTTTTH].。用SG函數(shù)打表复局,發(fā)現(xiàn)sg[x]=2x或sg[x]=2x+1冲簿。其中,x的二進制數(shù)中1的個數(shù)為奇數(shù)時亿昏,sg[x]=2x;否則sg[x]=2x+1峦剔;
打表SG函數(shù)
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;
}