题意分析

本题是一个关于博弈游戏的问题，游戏中玩家轮流选择大于1的整数，有禁选规则（已选数字及其倍数、已选数字倍数之和不能选），先手为Christine，后手为Matt，若玩家无合法可选数字则输。要求根据给定的可选数字集合，判断其中的“必赢选项”。

解题思路

1. 状态表示：
   • 用一个整数pos表示当前已选数字的状态，每一位对应一个数字，若该位为1表示对应的数字已被选，初始时pos为所有数字都未选的状态，即(1 << 21) - 3（因为1不参与游戏，所以去掉前两位）。
   • 对于每个测试用例，根据输入的可选数字集合，更新pos，将已选数字对应的位设为0。
   • 用dp[posb]表示状态posb（剩余可选数字的状态）下是否必赢，-1表示未计算，0表示必输，1表示必赢。
2. 深度优先搜索（DFS）：
   • 定义DFS(int posa, int posb)函数，posa表示当前已选数字的状态，posb表示剩余可选数字的状态。
   • 若posb == 0，表示没有可选数字了，当前玩家必输，返回0。
   • 若dp[posb] != -1，表示该状态已经计算过，直接返回dp[posb]。
   • 遍历所有可选数字，对于每个可选数字a[i]：
     • 先复制当前状态ita = posa，itb = posb。
     • 如果itb中该数字对应的位为1（即该数字可选），则根据规则更新ita（将已选数字加上a[i]对应的位）和itb（去掉已选数字的倍数和已选数字倍数之和对应的位）。
     • 递归调用DFS(ita, itb)，若返回0（即对手必输），则当前玩家必赢，将dp[posb]设为1并返回1。
   • 如果遍历完所有可选数字都没有找到必赢的情况，则当前玩家必输，将dp[posb]设为0并返回0。
3. 寻找必赢选项：
   • 在main函数中，对于每个测试用例，先初始化dp数组为-1，然后对输入的可选数字进行排序。
   • 遍历所有可选数字，对于每个数字a[i]，根据规则更新ita和itb，然后调用DFS(ita, itb)。
   • 如果DFS(ita, itb)返回0（即对手必输），则将该数字加入必赢选项数组ans中。
4. 输出结果：
   • 按照输出格式要求，输出测试用例编号、必赢选项或提示没有必赢选项的信息。

复杂度分析

1. 时间复杂度：
   • 对于每个测试用例，遍历所有可选数字，对于每个数字又要进行一些状态更新和递归调用。假设可选数字个数为n，状态更新和递归调用的时间复杂度与数字的范围和状态表示有关，这里粗略估计为指数级，所以整体时间复杂度为指数级，具体为$O(2^n \times n)$（因为每个数字都可能有选或不选两种情况，且对于每个状态需要遍历所有数字进行状态更新）。
2. 空间复杂度：
   • 主要空间消耗是dp数组，其大小为$2^{20}$（因为状态最多有$2^{20}$种），以及存储必赢选项的数组ans，其大小最多为n，所以空间复杂度为$O(2^{20} + n)$。

代码实现

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn = 21;
int n, pos, a[maxn], ans[maxn], cnt;
int dp[2097158];

// 深度优先搜索函数，判断状态(posa, posb)下是否必赢
bool DFS(int posa, int posb)
{
    if (posb == 0)
        return 0;
    if (dp[posb] != -1)
        return dp[posb];
    int ita, itb;
    for (int i = 0; i < n; i++)
    {
        ita = posa;
        itb = posb;
        if (itb & (1 << i))
        {
            // 更新ita，将已选数字加上a[i]对应的位
            for (int j = 0; j + a[i] < 21; j++)
                if (ita & (1 << j))
                    ita |= 1 << (j + a[i]);
            // 更新itb，去掉已选数字的倍数和已选数字倍数之和对应的位
            for (int j = 0; j < n; j++)
                if (itb & (1 << j) && (ita & (1 << a[j])))
                    itb ^= 1 << j;
            if (!DFS(ita, itb))
                return dp[posb] = 1;
        }
    }
    return dp[posb] = 0;
}

int main()
{
    int cas = 1;
    while (scanf("%d", &n) && n)
    {
        memset(dp, -1, sizeof(dp));
        cnt = 0;
        pos = (1 << 21) - 3;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            pos ^= 1 << a[i];
        }
        sort(a, a + n);
        for (int i = 0; i < n; i++)
        {
            int ita = pos;
            int itb = (1 << n) - 1;
            // 更新ita，将已选数字加上a[i]对应的位
            for (int j = 0; j + a[i] < 21; j++)
                if (ita & (1 << j))
                    ita |= 1 << (j + a[i]);
            // 更新itb，去掉已选数字的倍数和已选数字倍数之和对应的位
            for (int j = 0; j < n; j++)
                if (ita & (1 << a[j]))
                    itb ^= 1 << j;
            if (!DFS(ita, itb))
            {
                dp[ita] = 1;
                ans[cnt++] = a[i];
            }
        }
        printf("Test Case #%d\n", cas++);
        if (!cnt)
        {
            printf("There's no winning move.\n\n");
            continue;
        }
        printf("The winning moves are:");
        for (int i = 0; i < cnt; i++)
            printf(" %d", ans[i]);
        printf("\n\n");
    }
    return 0;
}

🧠 题解（Solution）

🔍 本质：

这是一道典型的 博弈论搜索题（Impartial Game, Game Theory），可用记忆化搜索 + MinMax 判断解决。

✅ 状态定义：

状态由“当前还可以选择的数字集合”定义；

若从当前状态出发，任意选择一个合法数字后，对手必输，则当前状态是必赢态（Winning Position）；

如果无法选出使对方进入输局的数字，则当前为必输态（Losing Position）。

✅ 核心步骤：

对当前状态中每个合法数字 $x$，模拟选中它后的新状态：

移除 $x$；

移除所有 $x$ 的倍数；

移除所有可以由选中集合线性组合得到的数（如 $2x + 3y$ 等）；

递归判断新状态是否是必输状态（对方无必胜策略）；

若存在某个 $x$ 能使新状态是必输态，则 $x$ 是必赢选项。

✅ 优化：

由于数字范围最多 $20$，状态可以用位图（bitmap）表示；

所有状态总数最多为 $2^{19} = 524288$，可使用记忆化搜索避免重复判断；

所有组合可预处理（剪枝优化）。

📌 举个例子（第三组）：

当前可选集合为 ${2,3,4,5,6}$，Christine 可选择：

$2$ → 移除 $2, 4, 6, 3+2=5$ ⇒ 无剩余 ⇒ 对方输，$2$ 是必胜；

$3$ → 同理判断；

找到所有使对方陷入无可选项的数字。

代码实现：

using namespace std; 
int timemark[21];        //每次搜索时，对数字是否可选的标记 
int N;                    //输入数字的个数 
int a[21];                //储存输入的数字 
int record[524288];        //保存局面策略的数组 
int cifang(int m,int n){//求m的n次方 
    if(n==0)
        return 1;
    int s=m;
    for(int i=1;i<n;i++)
        s=s*m;
    return s;
}
int bin2dec(int c[],int n){//将数组c对应的局面2进制数转化为十进制数字 
    int s=0;
    for(int i=1;i<=n;i++){
        s=s+cifang(2,c[i]-2);
    }
    return s;
}
int pd(int a[],int n){    //a是储存当前局面数字的数组，n是数组的长度 
    int b2d=bin2dec(a,n);    //求这个局面对应的十进制索引 
    if(record[b2d]!=0){        //如果是已搜索过的局面，则直接返回结果 
        return record[b2d];
    }
    else{//否则对这个局面开始搜索 
        int winmove[21];//储存胜利策略的数组 
        int winCount=1;//储存胜利策略的数量 
        int flag=0;//标记是否为必胜局面的变量，0必输，1必胜 
        for(int i=1;i<=n;i++){//循环取出a中第i个数字 
            int count=1;//取出数字的个数 
            for(int ii=2;ii<=20;ii++){//标记若数字t在数组a中，则标记为1，否则为0，去掉第i个元素，所以timemark[i]=0 
                timemark[ii]=0;
            }
            for(int ii=1;ii<=n;ii++){
                if(ii==i)
                    continue;
                timemark[a[ii]]=1;
            }    
            for(int k=2;a[i]+k<=20;k++){//将因为第i个数字被取出而影响的数字剔除 
                if(timemark[k]==0&&timemark[a[i]+k]!=0){
                    count++;
                    timemark[a[i]+k]=0;
                }
            }
            int b[21];//储存a去掉取出的数字和受影响的数字后的数组，用来进行下一层搜索 
            for(int indb=1;indb<=n-count;){
                for(int inda=1;inda<=n;inda++){
                    if(timemark[a[inda]]==1){
                        b[indb]=a[inda];
                        indb++;
                    }
                }
            }
            int next=pd(b,n-count);//求下一层局面的胜负情况 
            if(next==-1){//如果下一层为必输局面，这一层就是必胜局面，同时当前取出的数字成为一个必胜策略 
                winmove[winCount++]=a[i];
                flag=1;
            }
            if(i==n&&flag==0){//遍历本次所有可取的数字后，记录输赢的标记flag为0，则说明无论取哪个数字，下一个局面都是一个必胜局面，从而当前局面为必输局面 
                record[bin2dec(a,n)]=-1;
                return -1;
            }
            else if(i==n&&flag==1){//遍历本次所有可取的数字后，记录输赢的标记flag为0，从而当前局面为必赢局面 
                record[bin2dec(a,n)]=bin2dec(winmove,winCount-1);//将必胜策略转化为十进制数字储存在record中 
                return 1;
            }
        }
    }
    
}
void printWin(int t){//打印必胜时的策略 
    int count = 2;
    while(t!=0){
        if(t%2==1)
            cout<<count<<' ';
        count++;
        t=t/2;
    }
    cout<<endl;
}
int main(){
    cin>>N;
    int count=1;
    record[0]=-1;
    for(int i=1;i<524288;i++){
        record[i]=0;
    }
    for(int i=2;i<=20;i++){
        int a[2];
        a[1]=i;
        record[bin2dec(a,1)]=bin2dec(a,1);
    }
    while(N){
        for(int i=1;i<=N;i++)
            cin>>a[i];
        cout<<"Test Case #"<<count++<<endl;
        if(N==1){
            cout<<"The winning moves are: "<<a[1]<<endl;
        }
        else{
            int t=pd(a,N);
            if(t==-1)
                cout<<"There's no winning move."<<endl;
            else{
                cout<<"The winning moves are: ";
                printWin(record[bin2dec(a,N)]);
            }
        }
        cout<<endl;
        cin>>N;
    }
    return 0;
}