zoj - 1039 Number Game

本文主要是介绍zoj - 1039 Number Game，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int  M = 1<<19;
int dp[M+5];
int a[20];
int getk(int st,int x){//去除x的倍数及不在集合中组成的和在集合中for(int i = x;i <= 20;i+=x)st &= ~(1<<(i-2));//去除x的倍数；for(int i = 2;i <= 20;i++){if(st&(1<<(i-2))){for(int j = x;i-j-2 >= 0;j+=x){if(!(st&(1<<(i-j-2)))){st &= ~(1<<(i-2));break;}}}}return st;
}
int dfs(int st){if(dp[st] != -1) return dp[st];for(int i = 2;i <= 20;i++){if(st&(1<<(i-2))){int k = getk(st,i);if(!dfs(k)) return dp[st] = 1;}}return dp[st] = 0;
}
int main(){memset(dp,-1,sizeof(dp));dp[0] = 0;int n,t,S = 1;cin >> t;while(t --){int st = 0;cin >> n;for(int i = 0;i < n;i++){cin >> a[i];st |= (1<<(a[i]-2));//总的状态}printf("Scenario #%d:\n",S++);if(dfs(st) == 0) cout << "There is no winning move." << endl;else {cout << "The winning moves are:" ;for(int i = 0;i < n;i++){int k = getk(st,a[i]);if(!dfs(k)) cout<< " " << a[i];}cout << "." <<endl;}cout << endl;}
}

题意：给你n个数  n个数 在2~19范围内，两个人每个人取一个数，去除其倍数以及不在集合中两个数的和，谁先取完，谁就获胜，求第一个人获胜取得第一个数是什么（可以是多个）

题解：记忆化搜索 + 状态压缩  

  

这篇关于zoj - 1039 Number Game的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---