UVa 496 Simply Subsets

题目描述题目要求判断两个整数集合AAA和BBB之间的关系。可能的输出为A equals BABA BABA is a proper subset of BA⊂BA \subset BA⊂BB is a proper subset of AB⊂AB \subset AB⊂AA and B are disjointA∩B∅A \cap B \emptysetA∩B∅Im confused!其他情况即部分相交但不包含输入格式输入包含偶数行每对相邻行表示两个集合。每行包含若干个不同的整数整数之间由空格分隔。输入以文件结束符EOF\texttt{EOF}EOF终止。输出格式对于每对集合输出一行对应的关系描述。样例输入55 27 55 27 9 24 1995 9 24 1 2 3 1 2 3 4 1 2 3 4 5 6 1 2 2 3输出A equals B B is a proper subset of A A is a proper subset of B A and B are disjoint Im confused!题目分析本题的核心是计算两个集合的交集大小并根据交集与原集合大小的关系判断集合关系。算法步骤读取集合AAA和BBB存入setint。计算交集大小shared∣A∩B∣\textit{shared} |A \cap B|shared∣A∩B∣。比较若shared∣A∣∣B∣\textit{shared} |A| |B|shared∣A∣∣B∣则ABA BAB。若shared0\textit{shared} 0shared0则两集合不相交。若shared∣A∣\textit{shared} |A|shared∣A∣且∣A∣∣B∣|A| |B|∣A∣∣B∣则A⊂BA \subset BA⊂B。若shared∣B∣\textit{shared} |B|shared∣B∣且∣B∣∣A∣|B| |A|∣B∣∣A∣则B⊂AB \subset AB⊂A。否则输出Im confused!。复杂度分析使用set的查找操作时间复杂度O(∣A∣log⁡∣B∣)O(|A| \log |B|)O(∣A∣log∣B∣)可接受。代码实现// Simply Subsets// UVa ID: 496// Verdict: Accepted// Submission Date: 2016-07-16// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string line;while(getline(cin,line)){setintA,B;intnumber;istringstreamiss(line);while(issnumber)A.insert(number);getline(cin,line);iss.clear();iss.str(line);while(issnumber)B.insert(number);setintshared;for(autoa:A){if(B.find(a)!B.end())shared.insert(a);}if(shared.size()A.size()shared.size()B.size()){coutA equals B\n;}elseif(shared.size()0){coutA and B are disjoint\n;}elseif(shared.size()A.size()){coutA is a proper subset of B\n;}elseif(shared.size()B.size()){coutB is a proper subset of A\n;}elsecoutIm confused!\n;}return0;}