问题分析

有 $n$ 个朋友，每个朋友有 $m$ 种特征； 小 $C$ 知道 $Miku$ 想的是哪个朋友，但需要通过提问来唯一确定； 每次提问是关于某个特征是否为特定值； 目标是找到最少提问次数，使得这些提问的答案能唯一确定朋友身份； 如果有完全相同的朋友（所有特征都一样），则无法确定，输出 $- 1$；

代码解析：

代码的核心流程是：

1.读入数据 → 2. 处理每个朋友 → 3. 排除特殊情况（$n=1$ 或有相同朋友） → 4. 从少到多尝试特征数量 → 5. 生成所有可能的特征组合并检查 → 6. 输出最少需要的特征数量（即提问次数）。

代码整体思路是：

对于每个朋友 $i$，尝试找到最小的提问次数 $k$，使得通过这 $k$ 个特征的提问，能够将朋友 $i$ 与其他所有朋友区分开来。

详细解释见代码；

主要函数说明：

$d(e, f, g, h[], i)$：

检查对于朋友 $e$，使用 $h$ 数组中指定的 $i$ 个特征，是否能与其他所有朋友区分开； 参数 $e$ 是当前考虑的朋友索引； 参数 $f$ 是朋友总数； 参数 $g$ 是特征总数； 参数 $h []$ 是选择的特征索引数组； 参数 $i$ 是选择的特征数量； 功能：遍历其他所有朋友，检查是否有朋友在这 $i$ 个特征上与朋友 $e$ 完全相同

$n(o, p, q, r)$：

检查对于朋友 $o$ 是否存在 $r$ 个特征可以将其与其他朋友区分开； 参数 $o$ 是当前考虑的朋友索引； 参数 $p$ 是朋友总数； 参数 $q$ 是特征总数； 参数 $r$是要检查的特征数量； 功能：通过生成所有可能的 $r$ 个特征组合，调用 $d$ 函数检查是否有有效的区分特征组合；

$main()：$主函数

读取输入数据 对每个朋友进行处理： 特殊情况：如果只有 $1$ 个朋友，不需要提问，输出 $0$ 检查是否有完全相同的朋友，若有则输出 $- 1；$ 否则从 1 到 $m$ 依次尝试，找到最小的有效提问次数；

算法流程

对于每个朋友 $i$： 检查是否存在与 $i$ 完全相同的朋友，若有则输出 $- 1$ 否则从最少提问次数 $1$ 开始尝试： 检查是否存在 $1$ 个特征可以区分朋友 $i$ 与其他所有朋友； 若存在则记录 $1$，否则检查是否存在 $2$ 个特征的组合可以区分； 以此类推，直到找到最小的有效提问次数；

这种方法通过组合枚举的方式寻找最小特征集合，确保能唯一确定朋友身份，符合题目的要求。时间复杂度较高（时间复杂度为 $O(n² × m × 2^m))$,但是实际代码会小于此复杂度，所以不知道为什么就过了

代码：

#include<bits/stdc++.h>
using namespace std;

const int a=20,b=20;
long long c[a][b];
// a代表最大朋友数,b代表最大特征数,用二维数组c存储所有朋友的特征值
// e：目标朋友的编号（要区分的朋友）
// f：总朋友数n
// g：总特征数m
// h[]：存储选中的k个特征的编号（比如h=[0,2]表示选中特征0和2）
// i：选中的特征数量k
bool d(int e,int f,int g,int h[],int i){
    // 枚举所有其他朋友的特征，检查是否都能被辨别开
    for(int j=0;j<f;j++){
        if(j==e)continue;//跳过目标朋友自己
        bool k=0;// 记录是否能辨别开当前朋友j和目标朋友e
        // 检查选中的每个特征
        for(int l=0;l<i;l++){
            int m=h[l];
            // 当前特征的编号（比如m=0表示第0个特征）
            // 如果目标朋友e和朋友j在这个特征上的值不同，说明能辨别开
            if(c[e][m]!=c[j][m]){
                k=1;// 标记为可以辨别开
                break;// 不用检查其他特征了
            }
        }
        // 如果有一个朋友j无法区分，这个s数组无效
        if(!k)return 0;
    }
    // 所有朋友都能区分，这个s数组有效
    return 1;
}
// o：目标朋友的编号（同d函数的e）
// p：总朋友数n（同d函数的f）
// q：总特征数m（同d函数的g）
// r：要尝试的特征数量k（同d函数的i）
bool n(int o,int p,int q,int r){
    if(r==0)return 1;// 特殊情况：选0个特征（仅朋友数为1时）
    int s[r];// 记下当前选中的k个特征的编号
    // 初始化：选前k个特征编号（比如k=2时，s=[0,1]）
    for(int t=0;t<r;t++)s[t]=t;
    while(1){// 循环生成所有可能的s数组
        if(d(o,p,q,s,r))return 1;// 有效则返回true
        // 生成下一个s数组
        int u=r-1;// 从最后一个特征开始找可以递增特征编号的位置
        // 找到能递增特征编号的位置（避免超出特征范围），判断能不能递增的方法：见代码下
        while(u>=0&&s[u]==q-(r-u))u--;
        if(u<0)return 0;// 所有可能的s数组都试完了，没有有效的s数组
        s[u]++;// 递增当前位置的特征编号
        // 重置后面的特征为连续编号（保证组合不重复）
        for(int t=u+1;t<r;t++)s[t]=s[t-1]+1;
    }
}

int main(){
    int v,w;cin>>v>>w;
    for(int x=0;x<v;x++)
        for(int y=0;y<w;y++)
            cin>>c[x][y];
    // 对每个朋友计算最少提问次数
    for(int x=0;x<v;x++){
        // 特殊情况1：只有1个朋友，无需提问
        if(v==1){
            cout<<"0 ";continue;
        }
        // 检查是否存在和当前朋友x完全相同的朋友（无法区分）
        bool z=0;
        for(int aa=0;aa<v;aa++){
            if(aa==x)continue;// 跳过自己
            bool ab=1;//记录是否所有特征都相同
            for(int ac=0;ac<w;ac++)
                if(c[x][ac]!=c[aa][ac]){// 有一个特征不同就不是相同朋友
                    ab=0;
                    break;
                }
            if(ab){
                z=1;
                break;// 找到相同朋友，标记后跳出
            }
        }
        if(z){
            cout<<"-1 ";// 有相同朋友，输出-1
            continue;
        }
        // 寻找最少提问次数（从1个特征开始试）
        int s=-1;//结果
        for(int ad=1;ad<=w;ad++)// ad是尝试的特征数量（1到m）
            if(n(x,v,w,ad)){// 调用n函数检查ad个特征是否足够
                s=ad;// 找到最小数量，记录结果
                break;
            }
        cout<<s<<" ";
    }
    return 0;
}
    

判断能不能递增的方法：

先举例子理解如何递增：

假设总共有 4 个特征$（$编号 $0、1、2、3）$，现在要生成 “选 2 个特征” 的所有s数组。正确的顺序应该是： $[0,1] → [0,2] → [0,3] → [1,2] → [1,3] → [2,3]$

重要公式：$s[u]==q-(r-u)$

其中： $s[u]$是当前s数组中第u个位置的特征编号$（比如[0,1]中u=1时，s[u]=1）。$ $q$是总特征数。 $r - u$是当前位置$u$后面还剩的特征数量$（比如u=0，r=2时，r-u=2）。$ 然后，这个公式用来判断 “当前位置u的特征编号是否已经是最大值，不能再递增了”。

以$q=4$（总特征 0~3），$r=2$（选 2 个特征）为例：

对于 $u=1$（s数组中第 2 个位置）： $r - u = 2 - 1 = 1$，所以$q - (r - u) = 4 - 1 = 3。$ 即当s[1] == 3时，这个位置不能再递增了（因为最大特征是 3）。 对于$u=0$（s数组中第 1 个位置）： $r - u = 2 - 0 =2$，所以$q - (r - u) = 4 - 2 = 2$。 即当 $s[0]== 2$ 时，这个位置不能再递增了（因为后面还要留 1 个特征的位置，最大只能是 2，后面才能放 3）。

总结：

找到递增的位置” 本质是：

从组合的最后一个特征开始往前找，找到第一个 “还能增大” 的位置（即该位置的特征编号没达到最大值）。 增大这个位置的编号后，后面的位置依次设为 “当前位置 $+ 1$”，确保组合严格递增且不重复。

这种方式能高效生成所有可能的特征组合，就像按字典序排列组合一样，既不重复也不遗漏。