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

· · 题解

思路：

用 a_{i} 表示有几个数字 i 可以选择，当 a_{i} 等于时表示已经不能选择数字 i 了。用数组 b_{i} 存储 lenb 个输入第二行的 可选的数字 。vec_{i} 存储数字 i 在当前卡片中的所有倍数和约数。

对可选的数字从小到大依次进行一次深度搜索，如果返回 true 表示此数字可以选择，输出该数字并结束程序。深度搜索函数带有参数 num 和 t。其中，num 表示当前最新已选择的数，t 表示当前已选择数 num 的是自己还是对手，1 表示是自己，此时轮到了对手选择了。0 表示是对手，此时轮到了自己选择了。如果当前是自己，那么就是 1 。自己赢的条件是 num 的所有约数倍数都不可选，返回 true。如果当前是对手，就是 0，则自己只要有一个选择是可以赢的那么自己就是赢了。

如果还有不理解的地方，可以参考代码及注释。

关于这道题的难度，大概是绿题左右吧。

代码：

#include <bits/stdc++.h>
using namespace std;
int a[110],b[110];
int lena,lenb,maxx;
vector<int> vec[110];
bool dfs(int num,int t)
{
    int k,i;
    a[num]--;
    for(i=vec[num].size()-1;i>=0;i--) //这里是要从大到小搜索，可以尝试一下从小到大搜索体会体会差距 
    {
        if(a[vec[num][i]]>0)
        {
            if(t==1 && !dfs(vec[num][i],1-t)) //当前是自己选，对手任何选择都是输自己才是赢 ，对手有一个选择是赢的自己就输 
            {
                a[num]++;
                return false;
            }
            else if(t==0 && dfs(vec[num][i],1-t))// 当前是对手，自己只要有一个选择是可以赢的就是赢 
            {
                a[num]++;
                return true;
            }
        }
    }
    a[num]++;   
    if(t==1)
    {
        return true;
    }
    else
    {
        return false;
    }   
}
int main()
{
    int i,j,temp=0;
    string first,second;
    getline(cin,first);
    getline(cin,second);
    for(i=0;i<first.size();i++) //将输入第一行的字符串中的数一个个提取出，并保存为int型 
    {
        if(first[i]<='9' && first[i]>='0')
        {
            temp=temp*10+first[i]-'0';
            if(first[i+1]>'9' || first[i+1]<'0') //这是这个数的个位，下一个字符是分隔两个数的 
            {
                lena++; 
                a[temp]++; 
                temp=0;
            }
        }
    } 
    for(i=0;i<second.size();i++) //将输入第一行的字符串中的数一个个提取出，并保存为int型 
    {
        if(second[i]<='9' && second[i]>='0')
        {
            b[lenb]=b[lenb]*10+second[i]-'0';
            if(second[i+1]>'9' || second[i+1]<'0')//这是这个数的个位，下一个字符是分隔两个数的 
            {
                lenb++; 
            }
        }
    }
    sort(b,b+lenb);//从小到大排列 
    //将每个数的约数和倍数先存入
    for(i=1;i<=100;i++)
    {
        if(a[i]>0)
        {
            for(j=1;j<=100;j++)
            {
                if(a[j]>0 && (j%i==0 || i%j==0))
                {
                    vec[i].push_back(j);
                }
            } 
        }
    }
    for(i=0;i<lenb;i++)
    {
        if(dfs(b[i],1))//参数1表示自己，0表示对手，如果返回值为true，表示找到方法 
        {
            cout<<b[i]<<endl;
            return 0; 
        } 
    } 
    cout<<-1<<endl;
    return 0;
}