[C++知识库]蓝桥杯基础题集训练二

1、阶乘计算

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, f[N];
signed main() {
    f[0] = 1;
    scanf("%d", &n);
    for(int i = 2; i <= n; i++) {
        int add = 0;
        for(int j = 0; j <= 100000; j++) {
            int s = f[j] * i + add;
            f[j] = s % 10;
            add = s / 10;
        }
    }
    for(int i = 100000; i >= 0; i--) {
        if(f[i] != 0) {
            for(; i >= 0; i--) printf("%d", f[i]);
        }
    }
    return 0;
}

2、高精度加法

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
int n, f[N];
vector<int> add(vector<int>& a, vector<int>& b) {
    vector<int> c;
    int t = 0;
    for(int i = 0; i < a.size() || i < b.size(); i++) {
        if(i < a.size()) t += a[i];
        if(i < b.size()) t += b[i];
        c.push_back(t % 10);
        t /= 10;
    }
    if(t) c.push_back(1);
    return c;
}
signed main() {
    vector<int> A, B;
    string a, b;

    cin >> a >> b;

    for(int i = a.size() - 1; i >= 0; i--) A.push_back(a[i] - '0');
    for(int i = b.size() - 1; i >= 0; i--) B.push_back(b[i] - '0');

    //蓝桥杯c++不能用auto 编译器版本有点老
    vector<int> ok = add(A, B);
    for(int i = ok.size() - 1; i >= 0; i--) {
        printf("%d", ok[i]);
    }
    return 0;
}

3、Huffuman树

优先队列是个好东西

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e3 + 9;
int n;
priority_queue<int, vector<int>, greater<int> > a;
signed main() {
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++) {
        int x;
        scanf("%lld", &x);
        a.push(x);
    }

    if(n == 1) {
        printf("%lld", a.top());
        return 0;
    }
    int ok = 0;
    while(a.size() != 1) {
        int tmp = 0;
        tmp += a.top();
        a.pop();
        tmp += a.top();
        a.pop();
        //cout<<tmp<<" ";
        ok += tmp;
        a.push(tmp);
    }
    //ok+=a.top();
    // cout<<endl;
    printf("%lld",ok);
    return 0;
}