D - Stone Division HackerRank - stone-division (博弈+搜索)

时间:2022-04-05 07:52:24

题目链接:https://cn.vjudge.net/problem/HackerRank-stone-division

题目大意:给你n,m,然后是m个数。每一次你可以选择一个a[i],如果能被n整除,然后n就被分成了a[i]堆,每一堆有n/a[i]个。问你谁先无法分。

具体思路:对于当前的a[i],如果是偶数的话,那么只要第二个人怎么做,第一个人模仿就行了,这个时候是必胜态。

如果是奇数的话,判断当前单独一堆里面有多少个,然后判断一下这个n是不是必胜的,如果不是,那么先手赢,否则后手赢。

谢谢lxw的讲解

AC代码:

 #include<bits/stdc++.h>
using namespace std;
# define ll long long
const int maxn = 2e5+;
ll n,m;
map<ll,bool>sg;
ll a[maxn];
bool dfs(ll t)
{
if(sg.count(t))
return sg[t];
for(ll i=; i<=m; i++)
{
if(t%a[i])
continue;
if((a[i])%==)
{
sg[t]=;
return ;
}
else
{
if(!dfs(t/a[i]))
{
sg[t]=;
return ;
}
}
}
sg[t]=;
return ;
}
int main()
{
scanf("%lld %lld",&n,&m);
for(ll i=; i<=m; i++)
{
scanf("%lld",&a[i]);
}
if(dfs(n))
printf("First\n");
else
printf("Second\n");
return ;
}