1. 二进制位取反（bitset)
题目描述
输入10进制非负整数（小于2 30 2^{30}2
30
），利用bitset转二进制，并将每位取反输出。注意不可使用循环。
输入
测试次数
每组测试数据，一个10进制非负整数
输出
每组测试数据输出一行，32位计算结果。
样例输入
3
0
32
10
样例输出
11111111111111111111111111111111
11111111111111111111111111011111
11111111111111111111111111110101
题解
#include <iostream> #include <bitset> using namespace std; int main(){ int t,n; cin >> t; while(t--){ cin >> n; bitset<32> a(n); a.flip(); cout<<a<<endl; } return 0; }
2. 多重集合的简单操作(multiset)
题目描述
在一个给定的多重集合上，可以进行如下三种操作：
1 x表示给集合增加一个元素x；
2表示删除集合中最小的元素（如果集合为空，则什么都不做）；
3表示输出集合中最大的元素（如果集合为空，则什么都不做）。
输入
首先输入操作次数t
接下来每行输入一个操作命令
输出
对操作3，输出相应信息。
样例输入
6
1 2
1 3
3
1 3
1 4
3
样例输出
3
4
题解
#include <iostream> #include <set> using namespace std; int main(){ int t,op,n; cin >> t; multiset<int> s; while(t--){ cin >> op; if(op == 1) { cin >> n; s.insert(n); } if(op == 2){ if(s.size()){ s.erase(s.begin()); } } if(op == 3){ if(s.size()){ cout<<*(s.rbegin())<<endl; } } } }
3. 单词排序(set)
题目描述
输入一个文本，找出所有不同的单词（连续的字母序列），按字典序从小到大输出。单词不区分大小写。
smatch是类模板match_results的实例化，模板类。若cin读入多个单词，查regex_search和match_results的suffix方法。
输入
输入一段文本
输出
以从小到大的顺序输出文本中包含的所有单词（不区分大小写）
样例输入
Adventures in Disneyland
Two blondes were going to Disneyland when they came to a fork in the road. The sign read:“Disneyland Left.”
So they went home.
样例输出
a
adventures
blondes
came
disneyland
fork
going
home
in
left
read
road
sign
so
the
they
to
two
went
were
when
题解
#include <bits/stdc++.h> using namespace std; int main() { string word; set<string> s; while(cin >> word){ for(int i=0;i<word.size();i++) word[i] = tolower(word[i]); regex R("[a-z]{1,}"); smatch Mat; if(regex_search(word, Mat, R)) s.insert(Mat.str()); } for(auto i:s){ cout<<i<<endl; } return 0; }
4. 求并集(set)
题目描述
给定两个集合，求{A} + {B}.
注:同一个集合中不会有两个相同的元素。
看map课件，集合的并set_union算法和back_insert（迭代器适配器）用法。
输入
每组输入数据分为三行,第一行有两个数字n,m(0<n,m<=10000),分别表示集合A和集合B的元素个数.后两行分别表示集合A和集合B.每个元素为不超出int范围的整数,每个元素之间有一个空格隔开.
输出
针对每组数据输出一行数据,表示合并后的集合,要求从小到大输出,每个元素之间有一个空格隔开.
样例输入
1 2
1
2 3
1 2
1
1 2
样例输出
1 2 3
1 2
题解
#include <bits/stdc++.h> using namespace std; int main() { set<int> s1,s2,result; int n,m,cnt=0; while(cin>>n>>m){ int num; if(cnt++) cout<<endl; s1.clear();s2.clear();result.clear(); for(int i=0;i<n;i++){ cin>>num; s1.insert(num); } for(int i=0;i<m;i++){ cin>>num; s2.insert(num); } set_union(s1.begin(),s1.end(),s2.begin(),s2.end(),inserter(result, result.begin() )); int c=0; for(auto i:result){ if(c++) cout<<" "; cout<<i; } } }
5. 通讯录(multimap)
题目描述
Cindy的通讯录使用STL中的multimap记录所有好友的所有电话号码。通讯录支持两种查询操作：
1.输入姓名，输出该好友电话号码的个数；
2.输入姓名，输出该好友所有的电话号码。
输入
输入数据第一行为n，表示有n条姓名和对应号码记录。
接下来有n行，每行一个姓名和电话号码。
接下来一行为正整数m，表示查询次数
下面的m行中每行为操作种类（1或者2）和想查询的姓名。
输出
对于第一类操作，输出该姓名有多少个电话号码，每行一个数。
对于第二类操作，输出该姓名所有的电话号码（按输入的顺序），每行一个电话号码，如果不存在则输出None。
样例输入
3
crq 13512345678
yuyu 15988888888
crq 0576-12345678
6
1 crq
1 yuyu
1 kangkang
2 crq
2 yuyu
2 kangkang
样例输出
2
1
0
13512345678
0576-12345678
15988888888
None
题解
#include <bits/stdc++.h> using namespace std; int main() { multimap<string, string> mp; int n,m; string name,call; cin >> n; for(int i =0; i<n; i++){ cin>>name>>call; mp.insert(make_pair(name,call)); } cin >> m; int op; for(int i=0;i<m;i++){ cin>>op>>name; int cnt = mp.count(name); if(op == 1){ cout<<cnt<<endl; } if(op == 2){ if(cnt){ for(auto I = mp.lower_bound(name);I!=mp.upper_bound(name);I++){ cout<<I->second<<endl; } } else cout<<"None\n"; } } return 0; }
6. 同一集合？（bitset)
题目描述
有n个集合，每个集合有若干个元素，元素值在1-10000之间。给定i和j(0<i,j<10001)，求i,j是否属于同一集合？
思路：bitset数组，两个数组按位与，任意1即可。理清bitset数组行列对应什么？
输入
测试数据只有1组，格式如下：
第1行，集合数n(n<1000)
第2行到n+1行，每行1个集合，集合元素数m(1~10000之间）， 后跟m个元素，值范围1-10000。
第n+2行，问询次数t，后跟t行，每行两个1-10000之间的数字i j。
输出
对每个问询，输出一行，若i,j同属于1个集合以上（含一个集合），输出i,j同属于哪些集合。若i,j不同属于某一集合，输出no。
样例输入
4
3 10 20 30
4 1 10 5 7
6 12 3 4 5 7 2
2 10 15
3
5 7
10 15
1 3
样例输出
2 3
4
no
题解
#include <bits/stdc++.h> using namespace std; int main() { int n, t, m, num; cin >> n; bitset<10005> bit[n],aa,bb; for(int i = 0; i< n;i++){ cin >> m; bit[i] &= 0; for(int j=0;j<m;j++){ cin >> num; bit[i][num] = 1; } } int a,b,f; vector<int> ans; cin >> t; while(t--){ f=0; ans.clear(); aa &= 0, bb &= 0; cin >> a >> b; aa[a]= 1; bb[b]= 1; for(int i =0;i<n;i++){ if((bit[i] & aa)!=0 && (bit[i] & bb)!=0){ f = 1; ans.push_back(i+1); } } if(f==0) cout<<"no"; else{ for(int i =0; i<ans.size(); i++){ if(i!=0) cout<<" "; cout<<ans[i]; } } if(t!=0) cout<<endl; } }
