算法设计_综合练习_编程题（上）

2023-05-19 101

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 算法设计_综合练习_编程题

7-1 气球升起来

#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1010;
int n;
string str;
map<string, int> mp;
int main() {
    while (cin >> n) {
        for (int i = 0; i < n; i ++) {
            cin >> str;
            mp[str] ++;
        }
        string res;
        int cnt = 0;
        for (auto item : mp) {
            if (cnt < item.second) {
                res = item.first;
                cnt = item.second;
            }
        }
        cout << res << endl;
        mp.clear();
    }
    return 0;
}

7-2 集合A-B

#include <iostream>
#include <set>
#include <algorithm>
using namespace std;
int t, n, m;
set<int> arr1, arr2;
int x, i;
int main() {
    cin >> t;
    while (t --) {
        cin >> n >> m;
        int f = 0;
        for (i = 0; i < n; i ++)
            cin >> x, arr1.insert(x);
        for (i = 0; i < m; i ++)
            cin >> x, arr2.insert(x);
        set<int> res;
        for (auto it : arr1) {
            if (arr2.find(it) != arr2.end()) {
            } else {
                res.insert(it);
                if (f) cout << ' ';
                cout << it, f = 1;
            }
        }
        if (!f) cout << "NULL";
        cout << endl;
        arr1.clear();
        arr2.clear();
    }
    return 0;
}

7-3 排队

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int n, arr[N];
int x;
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> arr[i];
    }
    cin >> x;
    sort(arr, arr + n);
    int l = 0, r = 0, f = 0;
    for (int i = 0; i < n; i ++) {
        if (arr[i] == x && f == 0) l = i + 1, f = 1;
        if (arr[i] == x) r = i + 1;
    }
    cout << l << ' ' << r << endl;
    return 0;
}

7-4 办事大厅排队

#include <iostream>
using namespace std;
const int N = 100010;
string str, q[N];
int n, h, t = -1;
int main() {
    int n;
    cin >> n;
    while (n --) {
        cin >> str;
        if (str == "in") {
            cin >> str;
            q[ ++ t] = str;
        } else if (str == "out"){
            h ++;
        } else {
            if (h > t) cout << "NULL" << endl;
            else cout << q[h] << endl;
        }
    }
    return 0;
}

7-5 天梯赛的善良

#include <iostream>
using namespace std;
const int N = 20010;
int n, max_num, min_num, x;
int a = -0x3f3f3f3f, b = 0x3f3f3f3f;
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> x;
        if (x > a) a = x, max_num = 1;
        else if (x == a)max_num ++;
        if (x < b) b = x, min_num  = 1;
        else if (x == b) min_num ++;
    }
    cout << b << ' ' << min_num << endl;
    cout << a << ' ' << max_num << endl;
    return 0;
}

7-6 词典

#include <iostream>
#include <map>
using namespace std;
const int N = 1010;
int n, m;
string str1, str2;
map<string, string>mp;
int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i ++) {
        cin >> str1 >> str2;
        mp[str2] = str1;
    }
    for (int i = 0 ; i < m; i ++) {
        cin >> str1;
        if (mp.count(str1))
            cout << mp[str1] << endl;
        else cout << "eh" << endl;
    }
    return 0;
}

7-7 查找出现过的数字

#include <iostream>
#include <set>
using namespace std;
int n, m, x;
set<int> s;
int main() {
    cin >> m >> n;
    while (m --) {
        cin >> x;
        s.insert(x);
    }
    while (n --) {
        cin >> x;
        if (s.find(x) != s.end()) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

7-8 出现次数最多的数字和次数

#include <iostream>
#include <map>
using namespace std;
map<int, int>mp;
int n, x;
int x_v, x_c;
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> x;
        mp[x] ++;
    }
    for (auto i : mp) {
        if (i.second > x_c) {
            x_v = i.first;
            x_c = i.second;
        }
    }
    cout << x_v << ' ' << x_c << endl;
    return 0;
}

7-9 英雄出场王

#include <iostream>
#include <map>
using namespace std;
const int N = 100000000;
int n, x;
int x_v, x_c = -1;
map<int, int> mp;
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> x;
        mp[x] ++;
    }
    for (auto i : mp) {
        if (i.second > x_c) {
            x_v = i.first;
            x_c = i.second;
        }
    }
    cout << x_v << endl << x_c << endl;
    return 0;
}

7-10 求n个数中差的绝对值相差最小的2个数的差值

#include <iostream>
using namespace std;
const int N = 1010;
int n, x_v = 100000000;
int arr[N];
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        cin >> arr[i];
    }
    for (int i = 0; i < n; i ++) {
        for (int j = i + 1; j < n; j ++) {
            if (abs(arr[i] - arr[j]) < x_v) {
                x_v  = abs(arr[i] - arr[j]);
            }
        }
    }
    cout << x_v << endl;
    return 0;
}

7-11 数列求和-加强版

#include <iostream>
using namespace std;
int main() {
    int a, n;
    cin >> a >> n;
    int arr[1000010], cnt = 0, t = 0;
    if (!n) {
        cout << 0;
        return 0;
    }
    for (int i = 0; i < n; i ++) {
        arr[cnt ++] = (a * (n - i) + t )% 10;
        t = (a * (n - i) + t)/ 10;
    }
    if (t) arr[cnt ++] = t;
    for (int i = cnt - 1; i >= 0; i --) {
        cout << arr[i];
    }
    return 0;
}

7-12 数组循环右移（加强版）

#include <iostream>
using namespace std;
int main() {
    int n, m, i, f = 0;
    cin >> n >> m;
    m %= n;
    int a[n];
    for (i = 0; i < n; i ++)
        cin >> a[i];
    for (i = n - m; i < n; i ++) {
        if (f ++) cout << ' ';
        cout << a[i];
    }
    for (i = 0; i < n - m; i ++) {
        if (f ++) cout << ' ';
        cout << a[i];
    }
    cout << endl;
    return 0;
}

7-13 猴子选大王[加强版]

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k, s = 1;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ )
        s = (s + k) % i;
    cout << s;
    return 0;
}

7-14 最大公约数

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int a, b, res = 0;
    cin >> a >> b;
    for (int i = 2; i < max(a, b); i ++) {
        if (a % i == 0 && b % i == 0) {
            res = i;
        }
    }
    res = __gcd(a, b);
    cout << res << endl;
    return 0;
}

7-15 大菲波数

#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1010;
string f[N];
int t;
vector<int> add(vector<int> &A, vector<int> &B) {
    vector<int> C;
    for (int i = 0, t = 0; i < A.size() || i < B.size() || t; i++) {
        if (i < A.size()) t += A[i];
        if (i < B.size()) t += B[i];
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0) C.pop_back();
    return C;
}
int main() {
    f[1] = f[2] = "1";
    for (int i = 3; i < N; i ++) {
        string s1 = f[i - 1];
        string s2 = f[i - 2];
        vector<int> A, B;
        for (int i = s1.size() - 1; i >= 0; i --)
            A.push_back((s1[i] - '0'));
        for (int i = s2.size() - 1; i >= 0; i --)
            B.push_back((s2[i] - '0'));
        auto C = add(A, B);
        string s;
        for (int i = C.size() - 1; i >= 0; i --)
            s += to_string(C[i]);
        f[i] = s;
    }
    cin >> t;
    while (t --) {
        int x;
        cin >> x;
        cout << f[x] << endl;
    }
    return 0;
}

7-16 大数的乘法

#include <iostream>
#include <vector>
using namespace std;
typedef long long LL;
vector<LL> mul(vector<LL> &A, int b) {
    vector<LL> C;
    for (LL i = 0, t = 0; i <A.size() || t; i ++) {
        if (i < A.size()) t += A[i] * b;
        C.push_back(t % 10);
        t /= 10;
    }
    while (C.size() > 1 && C.back() == 0)
        C.pop_back();
    return C;
}
int main() {
    string s;
    int b;
    while(cin >> s >> b) {
        vector<LL> A;
        for (int i = s.size() - 1; i >= 0; i --)
            A.push_back(s[i] - '0');
        auto C = mul(A, b);
        for (int i = C.size() - 1; i >= 0; i --)
            cout << C[i];
        cout << endl;
    }
    return 0;
}