题目描述给定NNN枚硬币其中恰好有一枚假币其重量与真币不同可能偏重或偏轻其余真币重量相同。使用一架天平进行KKK次称量每次左右盘放置相同数量的硬币并记录结果左盘轻、重或平衡。要求根据这些称量结果找出假币的编号若无法唯一确定则输出000。输入格式第一行为整数MMM表示数据集个数。每组数据第一行为两个整数NNN和KKK1≤N≤1001 \le N \le 1001≤N≤1001≤K≤1001 \le K \le 1001≤K≤100。接下来2K2K2K行描述KKK次称量每次称量第一行以整数PiP_iPi​开头随后PiP_iPi​个左盘硬币编号再PiP_iPi​个右盘硬币编号第二行为一个字符、或表示左盘轻、左盘重或平衡。输出格式对于每组数据输出假币编号若无法确定则输出0。每组输出之间用一个空行分隔。样例输入1 2 1 2 3 4 1 1 4 1 2 5 6 4 3 1 2 3 4 5 6 1 1 2 2 1 3 4 5 2 4 5 2 6 输出3题目分析本题的核心是枚举每种可能假币可能是111到NNN中的任意一枚且可能偏重或偏轻。对于每种假设模拟KKK次称量检查结果是否与记录一致。若只有一种假设成立则输出对应的硬币编号否则输出000。模拟称量时对于每次称量若左盘或右盘包含假币则其总重量会相应变化否则所有硬币重量相同真币。由于真币重量未知但所有真币等重我们只需比较左右盘总重量的大小关系用相对值即可。解题思路读入NNN、KKK以及每次称量的左右盘硬币集合和结果符号。枚举假币编号i111到NNN和假币重量类型w000表示偏轻222表示偏重真币重量设为111。对每种假设检查所有KKK次称量若i在左盘则左盘总重量为(左盘硬币数 - 1) * 1 w否则为左盘硬币数 * 1。右盘同理。比较左右盘总重量应与记录结果相符。若所有称量都符合则记录该假设可能有多枚硬币或同一硬币偏重/偏轻两种都成立。若唯一成立输出该硬币编号否则输出0。注意若有同一枚硬币偏重和偏轻两种假设都成立则仍算作一个硬币可能但实际重量未知不能唯一确定因此输出0代码中通过possibility计数器统计所有成立的假设数若恰好为111则唯一。复杂度分析枚举NNN枚硬币每种假设检查KKK次称量每次称量需判断硬币是否在左右盘中使用哈希集合O(1)O(1)O(1)总时间复杂度O(N⋅K)O(N \cdot K)O(N⋅K)N,K≤100N, K \le 100N,K≤100完全可接受。空间复杂度O(K⋅Pi)O(K \cdot P_i)O(K⋅Pi​)用于存储称量数据。代码实现// False coin// UVa ID: 665// Verdict: Accepted// Submission Date: 2017-05-29// UVa Run Time: 0.000s//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0),cout.tie(0),ios::sync_with_stdio(false);intM,N,K,Pi;unordered_setintleftPan[128],rightPan[128];charresult[128];cinM;for(intc1;cM;c){if(c1)cout\n;cinNK;intidentifiers;for(inti1;iK;i){leftPan[i].clear(),rightPan[i].clear();cinPi;for(intj1;jPi;j){cinidentifiers;leftPan[i].insert(identifiers);}for(intj1;jPi;j){cinidentifiers;rightPan[i].insert(identifiers);}cinresult[i];}intpossibility0,falseCoin-1;for(inti1;iN;i){for(intw0;w2;w2){boolconformedtrue;for(intj1;jK;j){intleftPanWeightleftPan[j].find(i)!leftPan[j].end()?w:1;intrightPanWeightrightPan[j].find(i)!rightPan[j].end()?w:1;if(leftPanWeightrightPanWeightresult[j])continue;if(leftPanWeightrightPanWeightresult[j])continue;if(leftPanWeightrightPanWeightresult[j])continue;conformedfalse;break;}if(conformed){possibility1,falseCoini;break;}}}if(possibility1)coutfalseCoin\n;elsecout0\n;}return0;}总结本题通过枚举所有可能的假币编号和重量类型模拟称量结果从而确定唯一可能的假币。关键点在于正确表示称量数据左右盘集合。模拟时用相对重量真币为111假币为000或222比较大小。记录所有成立的假设若唯一则输出否则输出000。该解法简洁直观适用于N≤100N \le 100N≤100的规模。注意每组输出之间有空行但第一组前无空行。