网站空间便宜,推广普通话手抄报文字,盐城手机网站制作,seo 网站结构给定 n#xfffd; 堆石子以及一个由 k#xfffd; 个不同正整数构成的数字集合 S#xfffd;。
现在有两位玩家轮流操作#xff0c;每次操作可以从任意一堆石子中拿取石子#xff0c;每次拿取的石子数量必须包含于集合 S#xfffd;#xff0c;最后无法进行操作的人视…给定 n 堆石子以及一个由 k 个不同正整数构成的数字集合 S。
现在有两位玩家轮流操作每次操作可以从任意一堆石子中拿取石子每次拿取的石子数量必须包含于集合 S最后无法进行操作的人视为失败。
问如果两人都采用最优策略先手是否必胜。
输入格式
第一行包含整数 k表示数字集合 S 中数字的个数。
第二行包含 k 个整数其中第 i 个整数表示数字集合 S 中的第 i 个数 si。
第三行包含整数 n。
第四行包含 n 个整数其中第 i 个整数表示第 i 堆石子的数量 hiℎ。
输出格式
如果先手方必胜则输出 Yes。
否则输出 No。
数据范围
1≤n,k≤1001≤,≤100, 1≤si,hi≤10000
思路
对每个x求sg(x)然后然后异或得解。
代码
#define _CRT_SECURE_NO_WARNINGS #includeiostream #includecstdio #includecstdlib #includestring #includecstring #includecmath #includectime #includealgorithm #includeutility #includestack #includequeue #includevector #includeset #includemath.h #includeunordered_map #includemap using namespace std; #define LL long long #define per(i,a,b) for(int ia;ib;i) #define rep(i,a,b) for(int ia;ib;i--) const int N 1e5 100; int k, n; int f[N], s[N], ans 0;//f[x]为sg(x) int sg(int x) { if (f[x] ! -1) return f[x]; unordered_mapint, int p; per(i, 1, k)//递归求由x能到的状态sg函数值 { if (x s[i]) p[sg(x - s[i])] 1; } for (int i 0;; i)//mex函数求sg(x) if (!p[i]) { f[x] i; break; } p.clear(); return f[x]; } int main() { memset(f, -1, sizeof f); cin k; per(i, 1, k) cin s[i]; cin n; int x; per(i, 1, n) { cin x; ans ^ sg(x); } if (ans) cout Yes endl; else cout No endl; return 0; }
