题目描述在友好小学一年级每个学生需要与同班所有不认识的同学进行一分钟的相互介绍。若两个学生原本认识则无需介绍。为了节省时间老师希望将NNN名学生分配到两个班级使得两班人数相差至多111并且完成全部介绍所需的总时间尽可能短。完成全部介绍的时间定义为所有学生中需要进行的最大介绍次数因为每个学生可以依次与不认识的同学交谈而总时间由最繁忙的学生决定。给定NNN1≤N≤241 \le N \le 241≤N≤24以及学生之间的认识关系无向图求一种最优分配方案并输出该方案下每个学生需要进行的最大介绍次数以及两个班级的具体学生名单。输入格式输入包含多个测试用例。各测试用例之间由一个空行分隔。每个测试用例的第一行为一个整数NNN表示学生总数。接下来NNN行每行描述一个学生的认识关系格式为学生编号1∼N1 \sim N1∼N该学生认识的人数kkk随后kkk个整数表示该学生认识的学生编号顺序任意数据保证一致性即若AAA认识BBB则BBB也认识AAA。输出格式对于每个测试用例输出三行第一行输出一个整数表示最优分配下每个学生需要进行的最大介绍次数。第二行描述第一个班级先输出班级人数再按升序输出该班级所有学生编号各数字之间用单个空格分隔。第三行描述第二个班级格式同第二行。两个连续测试用例的输出之间用一个空行隔开。若存在多个最优分配输出任意一组即可。样例输入4 1 2 3 4 2 2 3 4 3 2 1 2 4 2 1 2 2 1 1 2 2 1 1输出0 2 1 3 2 2 4 0 1 1 1 2说明样例输出中第一组测试用例的分配结果为班级一有学生1,31,31,3班级二有学生2,42,42,4最大介绍次数为000。第二组测试用例中两名学生互相认识分配为每班一人最大介绍次数也为000。题目分析本题核心在于将学生划分为两个集合班级使得每个学生在其所在班级内不认识的人数最大值最小。由于N≤24N \le 24N≤24直接枚举所有可能的分割方案是可行的。我们用图模型表示认识关系顶点为学生边表示相互认识。对于某个分配方案每个学生iii的“介绍次数”等于他在自己班级内不认识的人数也就是补图不认识关系中与该学生同属于一个班级的邻居数量。我们需要最小化所有学生介绍次数的最大值。由于两班人数差至多111我们可以固定其中一个班级的人数为⌈N/2⌉\lceil N/2 \rceil⌈N/2⌉即较大的班另一个班级自动为补集。枚举所有大小为⌈N/2⌉\lceil N/2 \rceil⌈N/2⌉的子集即可覆盖所有合法分配。解题思路数据存储使用邻接矩阵或位掩码记录认识关系。每个学生iii维护一个整数notKnow[i]其二进制第jjj位为111表示iii与jjj不认识i≠ji \ne jij。这样对于任意班级集合mask学生iii在该班级内的不认识人数可通过popcount(notKnow[i] mask)快速得到。枚举子集令NNN为总人数target⌈N/2⌉target \lceil N/2 \rceiltarget⌈N/2⌉。使用Gospers hack算法高效枚举所有大小为targettargettarget的子集。该算法每次生成下一个包含相同数量111位的整数时间复杂度O(C(N,target))O(C(N, target))O(C(N,target))在N24N24N24时最大组合数为C(24,12)2,704,156C(24,12)2,704,156C(24,12)2,704,156完全可行。计算最优值对于每个子集mask补集comp fullMask ^ mask。遍历每个学生iii若iii属于mask则其介绍次数为popcount(notKnow[i] mask)否则为popcount(notKnow[i] comp)。记录最大值maxDeg。若maxDeg小于当前最优值则更新最优值及对应的子集。输出根据最优子集分别整理两个班级的学生编号升序按照格式输出最大介绍次数、班级人数和名单。代码实现// You Who// UVa ID: 649// Verdict: Accepted// Submission Date: 2026-07-02// UVa Run Time: 0.510s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;boolfirstCasetrue;while(cinN){// 读入认识关系vectorvectorboolknow(N,vectorbool(N,false));for(inti0;iN;i)know[i][i]true;for(inti0;iN;i){intid,k;cinidk;--id;for(intj0;jk;j){intv;cinv;--v;know[id][v]know[v][id]true;}}// 构建每个学生的不认识掩码vectorintnotKnow(N,0);intfullMask(1N)-1;for(inti0;iN;i){intmask0;for(intj0;jN;j)if(i!j!know[i][j])mask|(1j);notKnow[i]mask;}inttarget(N1)/2;// 较大班级的人数intbestMaxN1;intbestMask0;// Gospers hack: 枚举所有大小为 target 的子集intmask(1target)-1;intlimit1N;while(masklimit){intcompfullMask^mask;intmaxDeg0;for(inti0;iN;i){intd;if(mask(1i))d__builtin_popcount((unsigned)(notKnow[i]mask));elsed__builtin_popcount((unsigned)(notKnow[i]comp));if(dmaxDeg)maxDegd;}if(maxDegbestMax){bestMaxmaxDeg;bestMaskmask;}// 生成下一个组合intcmask-mask;intrmaskc;mask(((r^mask)2)/c)|r;}// 输出两个用例之间空一行if(!firstCase)cout\n;firstCasefalse;coutbestMax\n;vectorintclassA,classB;for(inti0;iN;i){if(bestMask(1i))classA.push_back(i1);elseclassB.push_back(i1);}coutclassA.size();for(intid:classA)cout id;cout\n;coutclassB.size();for(intid:classB)cout id;cout\n;}return0;}总结本题的关键在于将实际问题转化为图论中的最小化最大内部补图度数问题并利用NNN较小的特点通过枚举所有合法分割求得最优解。算法复杂度为O(C(N,⌈N/2⌉)⋅N)O(C(N, \lceil N/2 \rceil) \cdot N)O(C(N,⌈N/2⌉)⋅N)在N≤24N \le 24N≤24时运行效率足够。使用位掩码和Gospers hack提高了枚举效率同时简化了内部度数的计算。注意输入可能包含多个测试用例且输出格式要求空行分隔需要妥善处理首例空行问题。该方法属于典型的暴力枚举 位运算优化适用于小规模组合优化问题。 
长河君 · 2026/10/24 3:52:07 · 阅读 1.2k UVa 649 You Who
题目描述在友好小学一年级每个学生需要与同班所有不认识的同学进行一分钟的相互介绍。若两个学生原本认识则无需介绍。为了节省时间老师希望将NNN名学生分配到两个班级使得两班人数相差至多111并且完成全部介绍所需的总时间尽可能短。完成全部介绍的时间定义为所有学生中需要进行的最大介绍次数因为每个学生可以依次与不认识的同学交谈而总时间由最繁忙的学生决定。给定NNN1≤N≤241 \le N \le 241≤N≤24以及学生之间的认识关系无向图求一种最优分配方案并输出该方案下每个学生需要进行的最大介绍次数以及两个班级的具体学生名单。输入格式输入包含多个测试用例。各测试用例之间由一个空行分隔。每个测试用例的第一行为一个整数NNN表示学生总数。接下来NNN行每行描述一个学生的认识关系格式为学生编号1∼N1 \sim N1∼N该学生认识的人数kkk随后kkk个整数表示该学生认识的学生编号顺序任意数据保证一致性即若AAA认识BBB则BBB也认识AAA。输出格式对于每个测试用例输出三行第一行输出一个整数表示最优分配下每个学生需要进行的最大介绍次数。第二行描述第一个班级先输出班级人数再按升序输出该班级所有学生编号各数字之间用单个空格分隔。第三行描述第二个班级格式同第二行。两个连续测试用例的输出之间用一个空行隔开。若存在多个最优分配输出任意一组即可。样例输入4 1 2 3 4 2 2 3 4 3 2 1 2 4 2 1 2 2 1 1 2 2 1 1输出0 2 1 3 2 2 4 0 1 1 1 2说明样例输出中第一组测试用例的分配结果为班级一有学生1,31,31,3班级二有学生2,42,42,4最大介绍次数为000。第二组测试用例中两名学生互相认识分配为每班一人最大介绍次数也为000。题目分析本题核心在于将学生划分为两个集合班级使得每个学生在其所在班级内不认识的人数最大值最小。由于N≤24N \le 24N≤24直接枚举所有可能的分割方案是可行的。我们用图模型表示认识关系顶点为学生边表示相互认识。对于某个分配方案每个学生iii的“介绍次数”等于他在自己班级内不认识的人数也就是补图不认识关系中与该学生同属于一个班级的邻居数量。我们需要最小化所有学生介绍次数的最大值。由于两班人数差至多111我们可以固定其中一个班级的人数为⌈N/2⌉\lceil N/2 \rceil⌈N/2⌉即较大的班另一个班级自动为补集。枚举所有大小为⌈N/2⌉\lceil N/2 \rceil⌈N/2⌉的子集即可覆盖所有合法分配。解题思路数据存储使用邻接矩阵或位掩码记录认识关系。每个学生iii维护一个整数notKnow[i]其二进制第jjj位为111表示iii与jjj不认识i≠ji \ne jij。这样对于任意班级集合mask学生iii在该班级内的不认识人数可通过popcount(notKnow[i] mask)快速得到。枚举子集令NNN为总人数target⌈N/2⌉target \lceil N/2 \rceiltarget⌈N/2⌉。使用Gospers hack算法高效枚举所有大小为targettargettarget的子集。该算法每次生成下一个包含相同数量111位的整数时间复杂度O(C(N,target))O(C(N, target))O(C(N,target))在N24N24N24时最大组合数为C(24,12)2,704,156C(24,12)2,704,156C(24,12)2,704,156完全可行。计算最优值对于每个子集mask补集comp fullMask ^ mask。遍历每个学生iii若iii属于mask则其介绍次数为popcount(notKnow[i] mask)否则为popcount(notKnow[i] comp)。记录最大值maxDeg。若maxDeg小于当前最优值则更新最优值及对应的子集。输出根据最优子集分别整理两个班级的学生编号升序按照格式输出最大介绍次数、班级人数和名单。代码实现// You Who// UVa ID: 649// Verdict: Accepted// Submission Date: 2026-07-02// UVa Run Time: 0.510s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN;boolfirstCasetrue;while(cinN){// 读入认识关系vectorvectorboolknow(N,vectorbool(N,false));for(inti0;iN;i)know[i][i]true;for(inti0;iN;i){intid,k;cinidk;--id;for(intj0;jk;j){intv;cinv;--v;know[id][v]know[v][id]true;}}// 构建每个学生的不认识掩码vectorintnotKnow(N,0);intfullMask(1N)-1;for(inti0;iN;i){intmask0;for(intj0;jN;j)if(i!j!know[i][j])mask|(1j);notKnow[i]mask;}inttarget(N1)/2;// 较大班级的人数intbestMaxN1;intbestMask0;// Gospers hack: 枚举所有大小为 target 的子集intmask(1target)-1;intlimit1N;while(masklimit){intcompfullMask^mask;intmaxDeg0;for(inti0;iN;i){intd;if(mask(1i))d__builtin_popcount((unsigned)(notKnow[i]mask));elsed__builtin_popcount((unsigned)(notKnow[i]comp));if(dmaxDeg)maxDegd;}if(maxDegbestMax){bestMaxmaxDeg;bestMaskmask;}// 生成下一个组合intcmask-mask;intrmaskc;mask(((r^mask)2)/c)|r;}// 输出两个用例之间空一行if(!firstCase)cout\n;firstCasefalse;coutbestMax\n;vectorintclassA,classB;for(inti0;iN;i){if(bestMask(1i))classA.push_back(i1);elseclassB.push_back(i1);}coutclassA.size();for(intid:classA)cout id;cout\n;coutclassB.size();for(intid:classB)cout id;cout\n;}return0;}总结本题的关键在于将实际问题转化为图论中的最小化最大内部补图度数问题并利用NNN较小的特点通过枚举所有合法分割求得最优解。算法复杂度为O(C(N,⌈N/2⌉)⋅N)O(C(N, \lceil N/2 \rceil) \cdot N)O(C(N,⌈N/2⌉)⋅N)在N≤24N \le 24N≤24时运行效率足够。使用位掩码和Gospers hack提高了枚举效率同时简化了内部度数的计算。注意输入可能包含多个测试用例且输出格式要求空行分隔需要妥善处理首例空行问题。该方法属于典型的暴力枚举 位运算优化适用于小规模组合优化问题。