题目描述当芸芸众生忙着在朋友圈中发照片的时候总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。输入格式输入第一行给出一个正整数NNN≤100\le 100≤100是已知朋友圈的个数随后NNN行每行首先给出一个正整数KKK≤1000\le 1000≤1000为朋友圈中的人数然后列出一个朋友圈内的所有人——为方便起见每人对应一个 ID 号为 5 位数字从00000到99999ID 间以空格分隔之后给出一个正整数MMM≤10000\le 10000≤10000为待查询的人数随后一行中列出MMM个待查询的 ID以空格分隔。注意没有朋友的人可以是根本没安装朋友圈也可以是只有自己一个人在朋友圈的人。虽然有个别自恋狂会自己把自己反复加进朋友圈但题目保证所有KKK超过 1 的朋友圈里都至少有 2 个不同的人。输出格式按输入的顺序输出那些帅到没朋友的人。ID 间用 1 个空格分隔行的首尾不得有多余空格。如果没有人太帅则输出No one is handsome。注意同一个人可以被查询多次但只输出一次。解题思路本题的核心在于利用哈希表unordered_set进行状态标记与高效去重。核心流程分为三步第一步标记有朋友的人题目明确指出朋友圈人数K1K1K1时该人没有朋友K≥2K \ge 2K≥2时圈内所有人都有朋友。因此我们在读取数据时若K1K1K1只需使用cin将该 ID 读走以消耗输入流但不加入集合若K≥2K \ge 2K≥2则将该朋友圈内的所有 ID 存入hasFriend集合中作为“有朋友”的标记。第二步查询并高效去重在处理MMM个查询 ID 时依次检查该 ID 是否存在于hasFriend中。若不存在说明其“帅到没朋友”将其加入结果集ans中。为了避免同一个人被重复输出我们在将其加入结果集后顺手将其插入到hasFriend集合中。这样下次再遇到相同的 ID 时find就会直接命中从而保证了每个 ID 只会被输出一次。第三步格式化输出结果循环结束后若结果集ans为空则输出No one is handsome否则按顺序输出结果集中的 ID。代码中利用for循环的索引判断仅在非首个元素前输出空格完美避开了首尾多余空格的问题。复杂度分析时间复杂度O(N⋅KM)O(N \cdot K M)O(N⋅KM)。读取朋友圈和查询操作均只遍历一次哈希表的插入和查找平均时间复杂度为O(1)O(1)O(1)。空间复杂度O(N⋅K)O(N \cdot K)O(N⋅K)。主要用于存储“有朋友”的 ID 哈希表。AC代码#includeiostream#includestring#includeunordered_set#includevectorusingnamespacestd;intmain(){intN;cinN;unordered_setstringhasFriend;// 存储有朋友的人while(N--){intK;cinK;if(K1){// 只有一个人没有朋友直接读走该ID即可不加入集合string tmp;cintmp;}else{// K 2说明朋友圈里的人都有朋友全部加入集合for(inti0;iK;i){string id;cinid;hasFriend.insert(id);}}}intM;cinM;vectorstringans;// 按顺序保存帅到没朋友的人for(inti0;iM;i){string id;cinid;if(hasFriend.find(id)hasFriend.end()){// 如果不在 hasFriend 中说明帅到没朋友ans.push_back(id);hasFriend.insert(id);}}if(ans.empty())coutNo one is handsomeendl;else{for(size_t i0;ians.size();i){if(i!0)cout ;coutans[i];}coutendl;}return0;}哈希表https://zhuanlan.zhihu.com/p/95156642留着自己看如果帮到你那最好了如果有错误请见谅 L1-020 帅到没朋友 - C++
题目描述当芸芸众生忙着在朋友圈中发照片的时候总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。输入格式输入第一行给出一个正整数NNN≤100\le 100≤100是已知朋友圈的个数随后NNN行每行首先给出一个正整数KKK≤1000\le 1000≤1000为朋友圈中的人数然后列出一个朋友圈内的所有人——为方便起见每人对应一个 ID 号为 5 位数字从00000到99999ID 间以空格分隔之后给出一个正整数MMM≤10000\le 10000≤10000为待查询的人数随后一行中列出MMM个待查询的 ID以空格分隔。注意没有朋友的人可以是根本没安装朋友圈也可以是只有自己一个人在朋友圈的人。虽然有个别自恋狂会自己把自己反复加进朋友圈但题目保证所有KKK超过 1 的朋友圈里都至少有 2 个不同的人。输出格式按输入的顺序输出那些帅到没朋友的人。ID 间用 1 个空格分隔行的首尾不得有多余空格。如果没有人太帅则输出No one is handsome。注意同一个人可以被查询多次但只输出一次。解题思路本题的核心在于利用哈希表unordered_set进行状态标记与高效去重。核心流程分为三步第一步标记有朋友的人题目明确指出朋友圈人数K1K1K1时该人没有朋友K≥2K \ge 2K≥2时圈内所有人都有朋友。因此我们在读取数据时若K1K1K1只需使用cin将该 ID 读走以消耗输入流但不加入集合若K≥2K \ge 2K≥2则将该朋友圈内的所有 ID 存入hasFriend集合中作为“有朋友”的标记。第二步查询并高效去重在处理MMM个查询 ID 时依次检查该 ID 是否存在于hasFriend中。若不存在说明其“帅到没朋友”将其加入结果集ans中。为了避免同一个人被重复输出我们在将其加入结果集后顺手将其插入到hasFriend集合中。这样下次再遇到相同的 ID 时find就会直接命中从而保证了每个 ID 只会被输出一次。第三步格式化输出结果循环结束后若结果集ans为空则输出No one is handsome否则按顺序输出结果集中的 ID。代码中利用for循环的索引判断仅在非首个元素前输出空格完美避开了首尾多余空格的问题。复杂度分析时间复杂度O(N⋅KM)O(N \cdot K M)O(N⋅KM)。读取朋友圈和查询操作均只遍历一次哈希表的插入和查找平均时间复杂度为O(1)O(1)O(1)。空间复杂度O(N⋅K)O(N \cdot K)O(N⋅K)。主要用于存储“有朋友”的 ID 哈希表。AC代码#includeiostream#includestring#includeunordered_set#includevectorusingnamespacestd;intmain(){intN;cinN;unordered_setstringhasFriend;// 存储有朋友的人while(N--){intK;cinK;if(K1){// 只有一个人没有朋友直接读走该ID即可不加入集合string tmp;cintmp;}else{// K 2说明朋友圈里的人都有朋友全部加入集合for(inti0;iK;i){string id;cinid;hasFriend.insert(id);}}}intM;cinM;vectorstringans;// 按顺序保存帅到没朋友的人for(inti0;iM;i){string id;cinid;if(hasFriend.find(id)hasFriend.end()){// 如果不在 hasFriend 中说明帅到没朋友ans.push_back(id);hasFriend.insert(id);}}if(ans.empty())coutNo one is handsomeendl;else{for(size_t i0;ians.size();i){if(i!0)cout ;coutans[i];}coutendl;}return0;}哈希表https://zhuanlan.zhihu.com/p/95156642留着自己看如果帮到你那最好了如果有错误请见谅