如果了解 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;
- }
- View Code
来源: http://www.bubuko.com/infodetail-3475294.html