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