P8609 [蓝桥杯 2013 国 A] 约数倍数选卡片

题目描述

闲暇时，福尔摩斯和华生玩一个游戏：

在 $N$ 张卡片上写有 $N$ 个整数。两人轮流拿走一张卡片。要求下一个人拿的数字一定是前一个人拿的数字的约数或倍数。例如，某次福尔摩斯拿走的卡片上写着数字“ $6$ ”，则接下来华生可以拿的数字包括：

$1$，$2$，$3$，$6$，$12$，$18$，$24 \cdots $。

当轮到某一方拿卡片时，没有满足要求的卡片可选，则该方为输方。

请你利用计算机的优势计算一下，在已知所有卡片上的数字和可选哪些数字的条件下，怎样选择才能保证必胜！

当选多个数字都可以必胜时，输出其中最小的数字。如果无论如何都会输，则输出 $-1$。

输入格式

输入数据为 $2$ 行。第一行是若干空格分开的整数（每个整数介于 $1\sim 100$ 间），表示当前剩余的所有卡片。

第二行也是若干空格分开的整数，表示可以选的数字。当然，第二行的数字必须完全包含在第一行的数字中。

输出格式

程序则输出必胜的招法！！

输入输出样例 #1

输入 #1

2 3 6
3 6

输出 #1

3

输入输出样例 #2

输入 #2

1 2 2 3 3 4 5
3 4 5

输出 #2

4

说明/提示

时限 1 秒, 64M。蓝桥杯 2013 年第四届国赛

C++实现

#include<bits/stdc++.h>
using namespace std;
#define ll long long
vector<int> Split(string s){ //分割输入的整数
	s+=' ';
	string Sub="";
	vector<int> ans={};
	for(char c:s){
		if (c==' '&&Sub!=""){
			ans.push_back(stoi(Sub));
			Sub=""; //千万别忘了 
		}
		else if (c!='\n'&&c!='\r') Sub+=c;
	}
	return ans;
}
int cnt[110]; //记录还能用多少次
vector<int> g[110]; //存因数和倍数
bool dfs(int x){
	for(int i=g[x].size()-1;i>=0;i--){ //遍历因数和倍数 
		int v=g[x][i];
		if (!cnt[v]) continue;
		cnt[v]--; //使用一次
		int HouJi=dfs(v); //后继状态
		cnt[v]++; //回溯
		if (HouJi) return false;
	}
	return true;
}
int main(){
	string s1;
	getline(cin,s1);
	string s2;
	getline(cin,s2);
	vector<int> a1=Split(s1),a2=Split(s2);
	for(int x:a1) cnt[x]++;  //计数
	for(int i=1;i<=100;i++){
		if (!cnt[i]) continue; //没有这个数字，直接跳过
		cnt[i]--; //使用一次
		for(int j=1;j<=100;j++)
			if (cnt[j]/*有出现过*/&&((i%j==0)||(j%i==0)))
				g[i].push_back(j);
		cnt[i]++; //回溯
	}
	sort(a2.begin(),a2.end()); //从小到大排序
	for(int x:a2){
		cnt[x]--; //使用一次
		if (dfs(x)){
			printf("%d\n",x);
			return 0;
		}
		cnt[x]++; //回溯
	}
	return puts("-1")&0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容