[HNOI2007]分裂游戏题解

中考+研学+放假 7 天，历经 18 天狂暴颓废后第一次碰 OI 的第一道题

SG 定理

Statement

给定 \(n(\le 21)\) 堆石头，每次可以选择一个堆，减去其中一个，然后使得两个编号所选择堆分别增加一个石头。

轮流操作，不能操作者输

求必胜方案数和字典序最小的第一步方案

Solution

naive 想法：

前 30 min 经典读错题，没有看到 \(i 的限制。

然后也很蠢，想到这个游戏可能会无限进行下去（无限？ \(\to\) 莫名其妙想到说，哈，那肯定是形成了一个环

乱 gb 想了一下如何在有向有环图中做 SG ，发现不太刑

仔细想想发现石子总和肯定是不断增加的，所以不存在环，只能是说无限长的链

那么干脆约定一下不能有这种反哺的情况，也就是默认反哺会进入一个必胜态

然后回头一看，很好，经典读错题，没事，太久没碰 OI 了，可以理解

（但是现在不能理解的是为什么这么久都不碰 OI ，也许现在正是考验我快速恢复能力的时候）

然后发现这个状态数吓人，模拟之后发现不会处理

正解：参考 lhm 的题解

仔细分析整个过程，考虑使用 SG 定理分解游戏

考虑每一个单独的石子颠沛流离最终到达位置 n 的过程，产生了无数的子子孙孙

我们可以直接认为对这些子子孙孙进行的操作依旧是对原来放置在 x 位置的石头的博弈，容易发现每一颗石头的博弈过程是相互独立的

所以我们直接设 \(sg[x]\) 表示在位置 x 的一个石头的博弈状态即可

容易发现可以对原问题中每一个位置的石头数量 \(\mod 2\)

SG 直接 \(O(n^3)\) 即可

Code

#include
using namespace std;
const int N = 25;

char buf[1<<23],*p1=buf,*p2=buf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
int read(){
    int s=0,w=1; char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
    while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
    return s*w;
}

int sg[N],a[N];
int T,n,ans,cnt,fg;

int dfs(int n){
    if(sg[n]!=-1)return sg[n];
    bool vis[5005]={0};
    for(int i=1;i

[HNOI2007]分裂游戏题解

Statement

Solution

Code

相关

标签

[HNOI2007]分裂游戏 题解

Statement

Solution

Code

相关

标签

[HNOI2007]分裂游戏题解