1:__gcd函数 显然可以直接调用__gcd(a, b)这个函数返回a,b的最大公因数, 而最小公倍数=a * b / __gcd(a, b);
1 2 int a, b; cin >> a >> b;cout << __gcd(a, b) << ' ' << a * b / __gcd(a, b);
1-2 素数判断 显然只需要处理出1e5之内的素数,然后相邻判断是否差为2即可
1 2 3 4 5 6 7 8 9 10 11 12 13 14 int n; cin >> n;vector <int > v;for (int i = 2 ; i <= n; i ++ ) { bool fg = true ; for (int j = 2 ; j <= sqrt (i); j ++ ) if (i % j == 0 ) fg = false ; if (fg) v.pb(i); } int cnt = 0 ;for (int i = 1 ; i < v.size (); i ++ ) if (v[i] - v[i - 1 ] == 2 ) cnt ++; cout << cnt << endl ;
1-3 数学模拟 这个没啥好说的,c语言的课上应该都讲过,注意顺序就好了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 int a[1000 ][1000 ];int b[1000 ][1000 ];int c[1000 ][1000 ];int main () { int ra, ca, rb, cb; cin >> ra >> ca; for (int i = 0 ; i < ra; i ++ ) for (int j = 0 ; j < ca; j ++ ) cin >> a[i][j]; cin >> rb >> cb; for (int i = 0 ; i < rb; i ++ ) for (int j = 0 ; j < cb; j ++ ) cin >> b[i][j]; if (ca!=rb) cout << "Error: " << ca << " != " << rb << endl ; else { cout << ra << " " << cb << endl ; for (int i = 0 ; i < ra; i ++ ){ for (int j = 0 ; j < cb; j ++ ){ c[i][j] = 0 ; for (int k = 0 ; k < ca; k ++ ) c[i][j] = c[i][j] + a[i][k] * b[k][j]; } } int i = 0 , j = 0 ; for (i = 0 ; i < ra; i ++ ) { for (j = 0 ; j < cb - 1 ; j ++ ) cout << c[i][j] << ' ' ; cout << c[i][j] << endl ; } } return 0 ; }
1-4 queue 有趣的队列 就是一个队列 支持队首出队 队尾入队的操作, 那么很明显可以用stl中的deque. deque支持头尾都插入和删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 int n, m;cin >> n >> m;deque <int > v;int cnt = 1 ;while (m -- ) { int x; cin >> x; if (x == 0 ) v.push_back(cnt ++); else { auto t = v.front(); v.pop_front(); v.push_back(t); } } while (v.size ()) { cout << v.front(); v.pop_front(); if (v.size () != 0 ) cout << ' ' ; }
1-5 map 天梯赛的善良 就是mao的用法, 实际上map<a, b> mp; (a, b)为数据类型。 这个map是从a到b的一个映射. 例如y = 2x + 1, 那么当x = 1, 有y = 3。 同理,对于给定了的一个a, 那么b则为a的映射。例如map<int, int> mp; mp[9] = 2; 那么可以说是将9映射到了2。
在本题中,我们可以用map<int, int> mp;来表示mp[x]出现的次数, mp[x] ++表示x出现了一次。(为什么不用数组, 因为数组需要开大小,会爆内存)。那么这题就很好做了, 出现一个能力值x,则mp[x] ++;后面找最大最小就是在map中寻找
遍历map的方式:1.迭代器iterator 2: for auto 这个自己查一下
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int n; cin >> n; map <int , int > mp; int mx = -1 , mxs; int mi = 1e9 , mis; while (n -- ) { int x; cin >> x; mp[x] ++; } for (auto [x, v]: mp) { if (x > mx) { mx = x; mxs = v; } if (x < mi) { mi = x; mis = v; } } cout << mi << ' ' << mis << endl ; cout << mx << ' ' << mxs << endl ;
1-6 unordered_map 完美配对1(数据增强版) 这题和上面的一样,用map<int, int> mp来表示mp[x]出现的次数
注意到ai - aj = j - i (i < j) 整理一下得到 ai + i = aj + j, i < j;
那么我们去遍历这个j从2~n, 那么是不是只需要去看前面有多少个ai + i = 当前的aj + j; 那么只需要去记录好aj + j 出现的次数即可
先把第一个数 + 1出现1次记录好 ,然后j从2~n, 去找前面对应的aj + j出现的次数即可。
1 2 3 4 5 6 7 8 9 10 11 map <int , int > mp; int n; cin >> n; int x; cin >> x; mp[x + 1 ] ++; int ans = 0 ; for (int i = 2 ; i <= n; i ++ ) { int x; cin >> x; ans += mp[x + i]; mp[x + i] ++; } cout << ans << endl ;
1-7 unordered_map标记和sort(基础) 点赞狂魔 我们用结构体来存储每个用户的点赞信息,用vector去存储他点赞的人, 并同时排序(用自定义排序即可)。题目不难,难的是写法。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 #include <bits/stdc++.h> using namespace std ;const int N = 110 ;struct person { string name; int k; vector <int > q; int cnt; }s[N]; bool cmp (person a, person b) { if (a.cnt!= b.cnt) return a.cnt > b.cnt; } int main () { int n; cin >> n; for (int i = 0 ; i < n; i ++ ) { cin >> s[i].name >> s[i].k; while (s[i].k--) { int a; cin >> a; s[i].q.push_back(a); } sort(s[i].q.begin (),s[i].q.end ()); s[i].cnt = unique(s[i].q.begin (),s[i].q.end ()) - s[i].q.begin (); } sort(s, s + n, cmp); int cn = 0 ; for (int i = 0 ; i < n; i ++) { if (cn != 2 ) cout << s[i].name << " " ; else cout << s[i].name; cn ++; if (cn == 3 ) break ; } if (cn == 1 ) cout << '-' <<' ' <<'-' ; else if (cn == 2 ) cout << '-' ; return 0 ; }
1-8 set高效查找 集合相似度 可以直接开1010个set去存储所有出现的数字,因为set这个stl会自动去重,所以每个set中已经是去重了的。那么我们计算相似度的时候只需要看一个set中的x是否在另外一个出现即可。一共不相等的个数就是a.size() + b.size() - ab中都有的
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 int n; cin >> n; for (int i = 0 ; i < n; i ++ ) { int cnt; cin >> cnt; while (cnt -- ) { int x; cin >> x; v[i].insert(x); } } int q; cin >> q; while (q -- ) { int a, b; cin >> a >> b; a --, b --; int cnt = 0 ; for (auto x: v[a]) { if (v[b].count(x)) cnt ++; } int p = v[a].size () + v[b].size () - cnt; printf ("%.2lf%%\n" , cnt * 1.0 / p * 100 ); }
1-9 数组模拟队列 特殊队列 其实本题的关键就是一半这个操作,做这题不知道大家是否会想到对顶堆那个题目。那么一半一半这种操作,用一个队列肯定是不能完成的,很明显我们要用两个,且保证有一个一定>=另外一个, 且最多只能比另外一个多一个。那我们用两个deque, q1, q2;想象q1 q2 依次是连起来的,也就是q2是在后面.
对于入队操作,我们首先把入队的x放入q2, 如果发现q1前半部分的大小 < q2后半部分, 就把q2最前面的往前转移, 也就是把q2.front -> q1.back() 这样转移。那出队操作就很简单, q1.front()出队。 对于删除中间的操作,这个位置肯定就是q1.back(),自然也可以操作了
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 deque <int > q1, q2; int m, n; cin >> m >> n; while (m -- ) { string s; cin >> s; if (s == "EnQueue" ) { int x; cin >> x; if (q1.size () + q2.size () >= n) { cout << "Full Queue" << endl ; continue ; } q2.push_back(x); if (q1.size () < q2.size ()) { q1.push_back(q2.front()); q2.pop_front(); } } else { if (q1.size () == 0 ) { cout << "Empty Queue" << endl ; continue ; } if (s == "DeQueue" ) { cout << q1.front() << endl ; q1.pop_front(); if (q1.size () < q2.size ()) { q1.push_back(q2.front()); q2.pop_front(); } } else { cout << q1.back() << endl ; q1.pop_back(); if (q1.size () < q2.size ()) { q1.push_back(q2.front()); q2.pop_front(); } } } } for (int i = 0 ; i < q1.size (); i ++ ) { if (i) cout << " " ; cout << q1[i]; } for (int i = 0 ; i < q2.size (); i ++ ) cout << " " << q2[i];
1-10 综合应用 树种统计 这个就是map<string, int> mp用来标记每一个树出现的次数,记得getchar()先清空一下缓冲区在输入字符串前
1 2 3 4 5 6 7 8 9 10 11 12 13 map <string , int > mp; int n; cin >> n; getchar(); int k = n; while (n -- ) { string s; getline(cin , s); mp[s] += 1 ; } for (auto [x, v]: mp) { cout << x << ' ' ; printf ("%.4lf%%\n" , v * 1.0 / k * 100 ); }