约数倍数选卡片 （C++代码）递归博弈+优化 在官网已AC

解题思路:
   

    基本的博弈都可以用递归来求解，这道题由于想不到有效解法，则用 递归+优化

    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;
}