[蓝桥杯 2013 国 A] 约数倍数选卡片（数论，dfs，图）

哎，牛客赛做不下去了qwq，所以决定摸鱼来记录一篇题解。

那么废话不多说，看题目：

题目大意

两个人从一堆数字中选数，选择的只能是上个人选的数的约数或倍数，如果没得选就输了。

思考

将数字关系转换为图

刚开始看这道题的时候，有些束手无策，因为想不到一个好的办法去描述这些数字的关系。总不能每次都遍历一遍寻找选什么数吧？不过我突然灵机一动，刚好最近一直在练习图相关的题目，数字这种约数倍数的关系能不能转换成图呢？答案是可以的！而且适配的非常完美：如图，可以选的数字在图上恰恰是直接连接的。那么我们就把这道题转换成了一道无向图的题。我们要在给定的起点中找到必胜的最小的起点。只要这个点走到头没法走了，那这个点的状态就是输了。

不过这道题存在可以重复选的数字，所以我们还需要一个数组 cnt 来记录可以选择的次数。

dfs求解

对于图的问题，往往需要遍历图来求解。本题也不例外。可以想到当一个节点必输的时候它的上一个节点不一定胜，当一个节点的所有下一个节点存在必胜时这个节点必输。这启发我们通过 dfs 来递归搜索每个节点的胜负情况，需要注意的是这种博弈论题的博弈思想：

• 如果当前节点的所有下一个节点中存在必胜，那么这个节点必输。
• 否则这个节点必胜，也就是当前节点所有下一个节点都必输。

就这样，我们把这道数论加博弈的题转换为了图的 dfs。

Code

读入数据

这道题的数据需要我们自己想办法按行读，有两种办法：

1. 按行读入为字符串，处理字符串。 2. 按行读入为字符串流，处理字符串流。

这里给出第二种办法：

string line;
getline(cin, line);
stringstream ss(line);
int a;
while (ss >> a) {
    arr.push_back(a);//所有数字
    cnt[a]++;
}
getline(cin, line);
stringstream ss2(line);
while (ss2 >> a) {
    can.push_back(a);//先手可选的数字
}

初始化

建图并对可选数字排序，因为我们要找出最小的答案：

for(int i=1;i<=100;++i){
		if(cnt[i]==0) continue;
		cnt[i]--;
		for(int j=1;j<=100;++j){
			if(cnt[j]>0 && (i%j==0 || j%i==0)) e[i].push_back(j);//邻接表e
		}//这里让数字可以与自己连接，因为自己也是自己的约数和倍数
		cnt[i]++;
}
sort(can.begin(), can.end());

dfs

最关键的部分：

bool dfs(int x){
	if(!e[x].empty()){
		for(int j=e[x].size()-1;j>=0;--j){
			int i=e[x][j];
			if(!cnt[i]) continue;
			cnt[i]--;
			bool pr = dfs(i);
			cnt[i]++;
			if(pr) return false;
		}
	}
	return true;
}