首页 > 代码库 > 【BZOJ】1299: [LLH邀请赛]巧克力棒
【BZOJ】1299: [LLH邀请赛]巧克力棒
【算法】博弈论
【题解】这道题不是典型的SG函数题了。
不把它当成游戏看待,那么这道题是在说n个石子堆,每次可以加入若干个或进行Nim游戏。
我们当前先手,则考虑构造必败态来获胜。
当前已加入的NIm游戏SG=0,则必须考虑加入石子堆,若加入m堆构造出SG=0,对方有两种选择:
加入新的石子堆,则必须是SG=0。
进行Nim游戏,但是目前SG=0,先手必败。
所以只要把n堆中异或和=0的最长子序列在第一次操作时移入即可先手必胜。
#include<cstdio> #include<algorithm> #include<cstring> using namespace std; int a[20],n,tot; bool dfs(int x,int ans) { if(x==n+1) { if((!ans)&&tot)return 1; return 0;//!!! } else { tot++; bool ok=dfs(x+1,ans^a[x]); tot--; if(!ok)ok=dfs(x+1,ans); return ok; } } int main() { int T=10; while(T--) { scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d",&a[i]); tot=0; if(dfs(1,0))printf("NO\n");else printf("YES\n"); } return 0; }
【BZOJ】1299: [LLH邀请赛]巧克力棒
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。