做HH的网站,的网站建设,3d网页游戏排行,佛山 网站建设培训班取石子游戏
jzoj 1211
题目大意#xff1a;
有n个石子#xff0c;每次可取1~k个石子#xff08;必须取#xff09;#xff0c;问先取者是否有必胜方法
输入样例
2
2 3
3 2输出样例
No
Yes数据范围
20%的数据 K≤10 N≤30,000,000 50%的数据 K≤100 N≤2^31-1 100%的…取石子游戏
jzoj 1211
题目大意
有n个石子每次可取1~k个石子必须取问先取者是否有必胜方法
输入样例
2
2 3
3 2输出样例
No
Yes数据范围
20%的数据 K≤10 N≤30,000,000 50%的数据 K≤100 N≤2^31-1 100%的数据 K≤1000 N≤10^1000
解题思路
我们用DP思想,设f[i]f[i]f[i]为剩i颗石子时的胜败情况然后可以发现前i个是1然后是一个0因为接下来n个可以选1~n使对方是0所以又是n个1如此循环就变成了一个高精乘 如果除n1除得尽那就是0否则是1
代码
#includecstdio
#includestring
#includecstring
#includeiostream
using namespace std;
int n,l,t,T,a[1500];
string str;
int main()
{scanf(%d,T);for (int k1;kT;k){memset(a,0,sizeof(a));t0;scanf(%d,n);n;//加1cinstr;lstr.size();for (int i1;il;i)a[i]str[l-i]-48;for (int il;i0;--i)//高精除{a[i]t*10;ta[i]%n;a[i]/n;}if (t) printf(Yes\n);//输出else printf(No\n);}return 0;
}
