原题链接：蓝桥杯历届试题-约数倍数选卡片
解题思路:
基本的博弈都可以用递归来求解，这道题由于想不到有效解法，则用 递归+优化
1. 尝试所有走法，把局面交给对手，如果对手的局面是必输，则当前局面必胜；
2. 尝试所有走法后，还是赢不了那 当前局面比输
递归思路：
dfs(局面s){
尝试走一步s变成s1，把s1交给对手
如果存在一个s1局面必输：返回赢了;
返回必输;
}
不优化 只有50%成绩
优化思路：1.优先当前可选的数字大的卡片（数字越大，则约倍数在100内越少，所以递归的层数就越少）
2.常数优化，递归之前预处理每张卡片的下一次可选卡片集合
注意事项:
这个C语言网不知为什么代码AC不了一直超时17%，我去蓝桥杯官网提交了两次都600msAC了
参考代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#define _for(i,a,b) for(int i=a;i<b;i++)
#define _unfor(i,a,b) for(int i=a;i>=b;i--)
#define mset(a,val,n) for(int i=0;i<n;i++)a[i]=val;
#define FO freopen("out.txt","w",stdout)
#define RI(a) scanf("%d",&a)
using namespace std;
typedef long long LL;
int a[111],b[111],c='A';
vector<int> G[111];
int ri(){
int x=0;
while(!isdigit(c))if((c=getchar())=='\n')return 0;
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x;
}
int dp(int i){
if(!a[i])return 0;
a[i]--;
int len=G[i].size();
_for(k,0,len){
int j=G[i][k];
if((!(i%j)||!(j%i))&&a[j])
if(!dp(j)){a[i]++;return 1;}
}
a[i]++;
return 0;
}
int main(){
int x;
while(x=ri()){
a[x]++;
if(c=='\n')break;
}
//预处理
_for(i,1,101)
_unfor(j,100,1)if((!(i%j)||!(j%i))&&a[j])
G[i].push_back(j);
//
while(x=ri()){
b[x]++;
if(c=='\n')break;
}
_for(i,1,101)if(b[i])
if(!dp(i)){printf("%d\n",i);return 0;}
printf("%d\n",-1);
return 0;
}0.0分
5 人评分
C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：
一点编程也不会写的：零基础C语言学练课程
解决困扰你多年的C语言疑难杂症特性的C语言进阶课程
从零到写出一个爬虫的Python编程课程
只会语法写不出代码？手把手带你写100个编程真题的编程百练课程
信息学奥赛或C++选手的 必学C++课程
蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程
手把手讲解近五年真题的蓝桥杯辅导课程
发表评论 取消回复