CF919F A Game With Numbers

能转移到必败态的状态就是必胜态，只能转移到必胜态的状态就是必败态。

首先我们可以把状态压缩，发现状态最多只有 495 种。

然后如果一方是全 0 ，那么这个状态对应的答案就可以很容易得出

然后反着思考，从上面说的这些已知状态逆向搜索

DFS(m1,m2,k) 表示 A 是 m1 状态，B 是 m2 状态，k=0/1 表示当前是 A/B 操作的回合

每一个 m1,m2,k 只需要被搜索一次，所以可以用一个 vis 数组记忆一下有没有搜过

注意，我们是从结果推到初始状态，所以这里的转移也是倒过来转移

如果当前状态是必败态，那么转移到下一个状态（其实是上一个）就一定是必胜态，因为 能转移到必败态的状态就是必胜态

如果当前状态是必胜态，那么就把能转移到的状态的计数器自增，如果某个状态的计数器到达了能转移到他的状态的个数，那么那个状态就成为了必败态，因为 只能转移到必胜态的状态就是必败态

如果当前状态不是必胜也不是必败，那就别转移给其他状态，因为不确定

到最后还是不确定的起始状态那就是 Deal

然后把所有状态都预处理好，查询直接输出即可

至于记搜的复杂度... \(\mathcal O(\text{能过})\)

\(\texttt{Code}\)

// This code wrote by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
#define mem(x,y) memset(x,y,sizeof x)
#define ln puts("")
using namespace std;
template <class t> inline void read(t &s){s=0;
reg int f=1;reg char c=getchar();while(!isdigit(c)){if(c==‘-‘)f=-1;c=getchar();}
while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();s*=f;return;}
template<class t,class ...A> inline void read(t &x,A &...a){read(x);read(a...);}
template <class t> inline void write(t x){if(x<0)putchar(‘-‘),x=-x;
int buf[21],top=0;while(x)buf[++top]=x%10,x/=10;if(!top)buf[++top]=0;
while(top)putchar(buf[top--]^‘0‘);return;}
int idx[9][9][9][9],idxcnt;
int rev[500][5];
bool win[500][500][2],vis[500][500][2];
int cnt[500][500][2],Sum[500];
inline void dfs(int m[2],int k)
{
	for(int i=0;i<=4;++i)
		for(int j=1;j<=4;++j)
			if(rev[m[k^1]][i]&&rev[m[k]][j])
			{
				reg int c=(i-j+5)%5;
				if(!c)
					continue;
				reg int t[5];memcpy(t,rev[m[k^1]],sizeof t);
				--t[i],++t[c];
				reg int nxtm[2];nxtm[0]=m[0],nxtm[1]=m[1];
				nxtm[k^1]=idx[t[0]][t[1]][t[2]][t[3]];
				if(vis[nxtm[0]][nxtm[1]][k^1])
					continue;
				if(!win[m[0]][m[1]][k])
					win[nxtm[0]][nxtm[1]][k^1]=vis[nxtm[0]][nxtm[1]][k^1]=true,
					dfs(nxtm,k^1);
				else
				{
					if(++cnt[nxtm[0]][nxtm[1]][k^1]==Sum[nxtm[0]]*Sum[nxtm[1]])
						vis[nxtm[0]][nxtm[1]][k^1]=true,dfs(nxtm,k^1);
				}
			}
	return;
}
inline void work()
{
	reg int m[2],k,x;
	read(k);
	int t[5];mem(t,0);
	for(int i=1;i<=8;++i)
		read(x),++t[x];
	m[0]=idx[t[0]][t[1]][t[2]][t[3]];
	mem(t,0);
	for(int i=1;i<=8;++i)
		read(x),++t[x];
	m[1]=idx[t[0]][t[1]][t[2]][t[3]];
	puts(vis[m[0]][m[1]][k]?((win[m[0]][m[1]][k]^k)?"Alice":"Bob"):"Deal");
	return;
}
signed main(void)
{
	for(int i=0;i<=8;++i)
		for(int j=0;i+j<=8;++j)
			for(int k=0;i+j+k<=8;++k)
				for(int l=0;i+j+k+l<=8;++l)
					idx[i][j][k][l]=++idxcnt,
					rev[idxcnt][0]=i,rev[idxcnt][1]=j,rev[idxcnt][2]=k,
					rev[idxcnt][3]=l,rev[idxcnt][4]=8-i-j-k-l,
					Sum[idxcnt]=(!!j)+(!!k)+(!!l)+(!!rev[idxcnt][4]);
	for(int i=1;i<idxcnt;++i)
	{
		vis[idxcnt][i][0]=vis[i][idxcnt][0]=
		vis[idxcnt][i][1]=vis[i][idxcnt][1]=true;
		win[idxcnt][i][0]=win[i][idxcnt][1]=true;
		int m[2];
		m[0]=idxcnt,m[1]=i,dfs(m,0),dfs(m,1);
		m[0]=i,m[1]=idxcnt,dfs(m,0),dfs(m,1);
	}
	int t;read(t);
	while(t--)
		work();
	return 0;
}

CF919F A Game With Numbers

原文：https://www.cnblogs.com/chinesepikaync/p/13692829.html