未来

用户名：tj16

访问量：3092

签　名：

等　　级
排　　名	4310
经　　验	1720
参赛次数	0
文章发表	6
年　　龄	0
在职情况	学生
学　　校	太原学院
专　　业

　　自我简介：

TA的其他文章

DNA-题解(Java代码)
浏览：214

DP和DFS+DP详解（Java代码）
浏览：1207

1451题约数倍数选卡片-题解(Java详解-博弈论）
浏览：597

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

1451题约数倍数选卡片-题解(Java详解-博弈论）

　　作者: 未来　　　　发表时间：2020-02-23 18:41:01 浏览：597　|　评论：0　

原题链接：蓝桥杯历届试题-约数倍数选卡片

解题思路：**博弈论**——对手的必败态就是我的必胜态。需要注意的是只要某个选择可以导致对手出现必败态，则这个选择就是正确的，可以直接返回；而当我所有选择走了一遍之后，发现并没有返回，即并没有对手的必败态，才可以说明这是我的必败态。

```java

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	static int numCard[] = new int[101];// 下标为代表数字，值为数字出现次数
	static ArrayList<Integer>[] listA = new ArrayList[101];// 存储每个数的约数倍数
	static ArrayList<Integer> listB = new ArrayList<Integer>();// 存储可选数

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String s1 = sc.nextLine();
		String s2 = sc.nextLine();
		sc.close();
		String s11[] = s1.split("\\s+");// 空格个数不一定是一个，直接用" "分隔会错误50%
		String s22[] = s2.split("\\s+");

for (int i = 0; i < s11.length; i++) {
			int num = Integer.parseInt(s11[i]);
			numCard[num] += 1;//记录数字出现次数
		}
		for (int i = 0; i < s22.length; i++) {
			listB.add(Integer.parseInt(s22[i]));//记录可选数字
		}
		Collections.sort(listB);//对可选数字排序，这样有多种可行必胜策略时，只会输出较小数
		for (int i = 0; i < 101; i++) {
			listA[i] = new ArrayList<Integer>();//实例化链表，用于存储数字的约数倍数
		}

for (int i = 1; i < 101; i++) {//遍历1~100
			if (numCard[i] != 0) {//如果该数存在
				numCard[i]--;//查看该数被取走后他的约数倍数是否存在
				for (int j = 1; j < 101; j++) {//如果该数的约数倍数存在
					if (numCard[j] != 0 && (j % i == 0 || i % j == 0)) {
						listA[i].add(j);//存入
					}
				}
				numCard[i]++;//回溯
			}
		}

for (int i = 0; i < listB.size(); i++) {//遍历可选数
			int num = listB.get(i);
			numCard[num]--;//取出该数
			boolean result = dfs(num);//让对方选
			numCard[num]++;//回溯
			if (!result) {//对手必败，即我必胜
				System.out.println(num);
				return;
			}
		}
		System.out.println(-1);//执行自此说明我取那一张都不行，必败无疑
	}

private static boolean dfs(int num) {
		//遍历该数的约数倍数，优先选取较大值，因为100以内大数的约数倍数更少，胜率更高，减少递归层数
		//如果从i从0开始会超时33%
		for (int i = listA[num].size() - 1; i >= 0; i--) {
			int num2 = listA[num].get(i);
			if (numCard[num2] > 0) {//如果该数存在约数倍数
				numCard[num2]--;//取出
				boolean result = dfs(num2);//轮到我选(这一步会有多层递归，双方轮流选，直到一方没得选)
				numCard[num2]++;//回溯
				if (!result ) {//自己选的时候不存在，也就是我没得选了，对方胜利
					return true;
				}
			}
		}
		return false;//该数的约数倍数不存在
	}

}

```

0.0分

4 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

未来

TA的其他文章

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言训练-角谷猜想（C语言代码）

【计算两点间的距离】（C语言代码）

1451题约数倍数选卡片-题解(Java详解-博弈论）

评论区

精彩推荐

求圆的面积（C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

WU-输入输出格式练习（C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

DNA （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C二级辅导-求偶数和（C语言代码）

用筛法求之N内的素数。（C语言代码）

字符串比较（C语言代码）

未来

TA的其他文章

你可能喜欢

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值 （C语言代码） 如果a<0，那就不是这个代码了，哈哈哈哈

2005年春浙江省计算机等级考试二级C 编程题(3) （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

C语言训练-角谷猜想 （C语言代码）

【计算两点间的距离】 （C语言代码）

1451题约数倍数选卡片-题解(Java详解-博弈论）

评论区

精彩推荐

求圆的面积 （C语言代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

WU-输入输出格式练习 （C++代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

DNA （C语言描述，蓝桥杯）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

C二级辅导-求偶数和 （C语言代码）

用筛法求之N内的素数。 （C语言代码）

字符串比较 （C语言代码）

C语言训练-求s=a+aa+aaa+aaaa+aa...a的值（C语言代码）如果a<0，那就不是这个代码了，哈哈哈哈

C语言训练-角谷猜想（C语言代码）

【计算两点间的距离】（C语言代码）

　　评论区

求圆的面积（C语言代码）

WU-输入输出格式练习（C++代码）

C二级辅导-求偶数和（C语言代码）

用筛法求之N内的素数。（C语言代码）

字符串比较（C语言代码）