首页 > 代码库 > 【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;
}
View Code

 

【BZOJ】1299: [LLH邀请赛]巧克力棒