題目鏈接：點(diǎn)擊查看

題目大意：給出一個(gè)日期，兩個(gè)人輪流按照規(guī)則操作，具體規(guī)則如下：

每次可以增加一天

每次可以增加一個(gè)月到下一個(gè)月的當(dāng)天

首先到達(dá)2001年11月4日的人獲勝，問(wèn)誰(shuí)能獲勝

題目分析：因?yàn)槭菑?900年1月1日開始的，最多只跨越了100年，也就是100*365天，大概也就1e5的分支，我們可以直接用dfs進(jìn)行sg打表，每一次至多有兩個(gè)分支，可以用兩個(gè)if套上好多個(gè)if else就好了。。這樣的話時(shí)間復(fù)雜度我不太會(huì)算，但因?yàn)橛昧藄g打表，也相當(dāng)于是記憶化搜索了，避免了重復(fù)分支的多次調(diào)用，所以交上去之后15毫秒就過(guò)了，還要吐槽一點(diǎn)，我的筆記本太不給力了。。在本地T掉了，本來(lái)很失望的交上去卻A掉了，emmm

最后再感謝zx學(xué)長(zhǎng)的思路，直接上代碼了：

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=4e5+100;int sg[2020][15][35];//sg函數(shù)，類似于記憶化搜索const int mon[2][13]={{0,31,28,31,30,31,30,31,31,30,31,30,31},{0,31,29,31,30,31,30,31,31,30,31,30,31}};bool is_year(int year)//判斷是否為閏年 {if(year%4==0&&year%100!=0||year%400==0)return true;return false; }bool check(int a,int b,int c)//判斷是否越界 {if(a>2001||a==2001&&b>11||a==2001&&b==11&&c>4)return false;return true; }bool dfs(int a,int b,int c)//記憶化搜索 {if(sg[a][b][c]!=-1)return sg[a][b][c];if(a==2001&&b==11&&c==4)return sg[a][b][c]=false;int pos=is_year(a);if(c<mon[pos][b]&&check(a,b,c+1))//下一天 {if(!dfs(a,b,c+1))return sg[a][b][c]=true;}else if(c==mon[pos][b]&&b!=12&&check(a,b+1,1))//跨月不跨年 {if(!dfs(a,b+1,1))return sg[a][b][c]=true;}else if(c==mon[pos][b]&&b==12&&check(a+1,1,1))//跨年{if(!dfs(a+1,1,1))return sg[a][b][c]=true;} if(b<12)//下一個(gè)月的同一天{if(c<=mon[pos][b+1])//確保下一個(gè)月中有這一天 if(check(a,b+1,c))if(!dfs(a,b+1,c))return sg[a][b][c]=true;}else if(b==12)//跨年{if(check(a+1,1,c))//12月和1月都是31天，所以不用特判 if(!dfs(a+1,1,c))return sg[a][b][c]=true;} return sg[a][b][c]=false; }int main() { // freopen("input.txt","r",stdin);memset(sg,-1,sizeof(sg));int w;cin>>w;while(w--){int a,b,c;scanf("%d%d%d",&a,&b,&c);if(dfs(a,b,c))printf("YES\n");elseprintf("NO\n");}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的HDU - 1079 Calendar Game(博弈打表sg函数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。