约数倍数选卡片
time limit per test 1 second memory limit per test 256 megabytes
闲暇时，福尔摩斯和华生玩一个游戏：
在N张卡片上写有N个整数。两人轮流拿走一张卡片。要求下一个人拿的数字一定是前一个人拿的数字的约数或倍数。例如，某次福尔摩斯拿走的卡片上写着数字“6”，则接下来华生可以拿的数字包括：
1，2，3, 6，12，18，24 ….
当轮到某一方拿卡片时，没有满足要求的卡片可选，则该方为输方。
请你利用计算机的优势计算一下，在已知所有卡片上的数字和可选哪些数字的条件下，怎样选择才能保证必胜！
当选多个数字都可以必胜时，输出其中最小的数字。如果无论如何都会输，则输出-1。
输入格式
输入数据为2行。第一行是若干空格分开的整数（每个整数介于1~100间），表示当前剩余的所有卡片。
第二行也是若干空格分开的整数，表示可以选的数字。当然，第二行的数字必须完全包含在第一行的数字中。
输出格式
程序则输出必胜的招法！！
样例输入
2 3 6
3 6
样例输出
3
样例输入
1 2 2 3 3 4 5
3 4 5
样例输出
4
题解
博弈基础题 在于必胜态和必败态
如果轮到对手有一个必胜态的话 对手肯定会选择必胜的做法 那么自己就是必败态
如果对手一个必胜态都找不到 那么自己就是必胜态
这个可以用dfs递归搜索 因为状态是轮换的
还有一个问题就是递归时时刻注意回溯的位置
不要递归return后达不到回溯的地方就尴尬了
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
| import java.io.*;
import java.util.*;
public class Main {
static ArrayList[]list3;
static int[]num;
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
PrintWriter pw=new PrintWriter (System.out);
while(sc.hasNext()){
num=new int[100000];
ArrayList<Integer>list1=new ArrayList<Integer>();
String s1=sc.nextLine();
String s2=sc.nextLine();
s1+=" ";
s2+=" ";
int num1=0;
for(int i=0;i<s1.length();i++){
if(s1.charAt(i)==' '){
list1.add(num1);
num[num1]++;
num1=0;
}else{
num1=num1*10+s1.charAt(i)-'0';
}
}
num1=0;
ArrayList<Integer>list2=new ArrayList<Integer>();
for(int i=0;i<s2.length();i++){
if(s2.charAt(i)==' '){
list2.add(num1);
num1=0;
}else{
num1=num1*10+s2.charAt(i)-'0';
}
}
Integer[]shu=new Integer[list1.size()];
for(int i=0;i<list1.size();i++){
shu[i]=list1.get(i);
}
list3=new ArrayList[101];
int n=list1.size();
for(int i=0;i<n;i++){
list3[list1.get(i)]=new ArrayList<Integer>();
}
Collections.sort(list2);
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
int a=list1.get(i);
int b=list1.get(j);
if(a%b==0||b%a==0){
if(!list3[a].contains(b))
list3[a].add(b);
}
}
}
boolean flag=false;
for(int i=0;i<list2.size();i++){
num[list2.get(i)]--;
boolean t=dfs(list3[list2.get(i)]);
if(t){
pw.println(list2.get(i));
flag=true;
break;
}
num[list2.get(i)]++;
}
if(!flag)pw.println(-1);
pw.flush();
}
}
static boolean dfs(ArrayList<Integer>list){
int n=list.size();
for(int j=n-1;j>=0;j--){
if(num[list.get(j)]>0){
num[list.get(j)]--;
boolean k=dfs(list3[list.get(j)]);
num[list.get(j)]++;
if(k==true)return false;
}
}
return true;
}
}
|
