如果了解sg函数,就知道如果全部相异或是0则必败,否则必胜
#include<iostream> #include<unordered_map> #include <unordered_set> #include<cstring> using namespace std; const int N=1e5+10; int n,m; int s[110]; int a[N]; int f[N]; int sg(int x){ if(f[x]!=-1) return f[x]; int i; unordered_set<int> m1; for(i=1;i<=m;i++){ if(x>=s[i]) m1.insert(sg(x-s[i])); } for(i=0;;i++){ if(!m1.count(i)){ f[x]=i; return f[x]; } } } int main(){ cin>>m; int i; for(i=1;i<=m;i++) cin>>s[i]; cin>>n; memset(f,-1,sizeof f); int res=0; for(i=1;i<=n;i++){ int x; cin>>x; res^=sg(x); } if(res==0) cout<<"No"<<endl; else cout<<"Yes"<<endl; }