1:__gcd函数

显然可以直接调用__gcd(a, b)这个函数返回a,b的最大公因数, 而最小公倍数=a * b / __gcd(a, b);

c++
1
2
int a, b; cin >> a >> b;
cout << __gcd(a, b) << ' ' << a * b / __gcd(a, b);

1-2 素数判断

显然只需要处理出1e5之内的素数,然后相邻判断是否差为2即可

c++
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语言的课上应该都讲过,注意顺序就好了

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支持头尾都插入和删除

c++
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 这个自己查一下

c++
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出现的次数即可。

c++
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去存储他点赞的人, 并同时排序(用自定义排序即可)。题目不难,难的是写法。

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
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中都有的

c++
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(),自然也可以操作了

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
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()先清空一下缓冲区在输入字符串前

c++
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);
}