第十二届蓝桥杯省赛第二场题解

求余

提示：

​ 签到题不多说了

#include<bits/stdc++.h>
using namespace std;

int main(){
  cout << 2021%20;
  return 0;
}

• ans： 1

双阶乘

提示：

​ 输出奇数位的乘积, 需要注意一下每次的运算都取下余数，只算最后几位。 考试的时候电脑上有python环境，我直接python解决

#include <iostream>

using namespace std;

int main() {
    long long res = 1;
    for (int i = 1; i <= 2021; i += 2) {
        res = res * i % 100000;
    }
    cout << res;
    return 0;
}

• ans：59375

格点

提示：

​ 暴力一下就出来，花不了多少时间

#include <iostream>

using namespace std;

int main() {
    long long x, y;
    int ans = 0;
    for (x = 1; x <= 2021; x++) {
        for (y = 1; y <= 2021; y++) {
            if (x * y <= 2021){
                ans += 1;
            }
        }
    }
    cout << ans;
}

• ans：15698

整数分解

提示：

​ 枚举前3个数，最后两个数只有m-1种情况, 注意一下int的数据范围问题

#include <iostream>

using namespace std;

int main() {
    long long ans = 0;
    for (int i = 1; i < 2021; ++i) {
        for (int j = 1; j < 2021; ++j) {
            for (int k = 1; k < 2021; ++k) {
                int m = 2021 - i - j - k;
                if (m <= 1) break;
                ans += m - 1;
            }
        }
    }
    cout << ans;
}

• ans : 691677274345

城邦

提示：

​ 最小生成树问题： 比赛的时候忘记Prim/Kruskal算法怎么写了，脑壳疼。这里我还是选择了Kruskal算法，因为比较好写，哈哈哈！

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;

typedef struct {
    int begin;
    int end;
    int weight;
} Edge;

int calculateWeight(int a, int b) {
    int res = 0;
    string sa = to_string(a), sb = to_string(b);
    while (sa.size() < sb.size()) sa = "0" + sa;        // 因为 枚举时 a <b 所以 只可能是a要补前导0
    for (int i = 0; i < sa.size(); ++i) {
        if (sa[i] != sb[i])
            res += sa[i] - '0' + sb[i] - '0';
    }
    return res;
}


bool myCompare(Edge a, Edge b) {
    return a.weight < b.weight; // 升序排列
}

int Find(const int *parent, int f) {
    while (parent[f] > 0)
        f = parent[f];
    return f;
}

int main() {
    vector<Edge> M;
    // 构建边集数组
    for (int i = 0; i < 2021; ++i) {
        for (int j = i + 1; j < 2021; ++j) {
            Edge edge;
            edge.begin = i;
            edge.end = j;
            edge.weight = calculateWeight(i + 1, j + 1);
            M.push_back(edge);
        }
    }
    sort(M.begin(), M.end(), myCompare);
    int maxVex = M.size();
    int parent[maxVex];
    for (int i = 0; i < maxVex; ++i) {
        parent[i] = 0; // 初始化数组值为0
    }

    long long res = 0;
    for (int i = 0; i < maxVex; ++i) { // 循环每一条边
        int n = Find(parent, M[i].begin);
        int m = Find(parent, M[i].end);
        if (n != m) {
            parent[n] = m;
            res += M[i].weight;
        }
    }
    cout << res << endl;
    return 0;

}

• ans：4046

特殊年份

提示：

​ 读入之后判断一下即可；

#include <iostream>
#include <string>

using namespace std;


int main() {
    string a;
    int res = 0;
    for (int i = 0; i < 5; ++i) {
        cin >> a;
        if (a[0] == a[2] and a[3] - a[1] == 1)
            res += 1;
    }
    cout << res;
    return 0;
}

小平方

提示：

​ 直接暴力求解即可，但是需要注意进度问题，这里我乘以2取消了精度问题

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

#define ll long long
using namespace std;


int main() {
    ll n;
    cin >> n;
    ll res;
    ll k;
    for (int i = 1; i < n; ++i) {
        k = (i * i) % n;
        k *= 2; // 乘以2取消精度问题
        if (k <= n){
            res += 1;
        }
    }
    cout << res;
    return 0;
}

完全平方数

提示：

​ 用暴力的解法可以混一些分，正确的解法就比较麻烦。结合数论内容我们可以知道如果n是一个素数，那么x等于n直接输出即可。如果n 不是素数我们就做一个质因数分解，将分解得出的奇数次方的质数相乘就是我们要的结果。判断素数由于这里的数很大所以我们用欧几里得筛法。

#include <iostream>
#include <vector>
#include <map>

using namespace std;
#define ll long long


vector<ll> primes;

map<ll, int> flag;

bool isPrime(ll x) {
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}

void getPrime(ll x) {
    ll j;
    vector<bool> vis(x, true);
    vis[0] = vis[1] = false;
    for (ll i = 2; i * i < x; ++i) {
        if (isPrime(i)) {
            j = 2;
            while (j * i <= x) {
                vis[j * i] = false;
                j++;
            }
        }
    }
    for (int i = 2; i < vis.size(); ++i) {
        if (vis[i])
            primes.push_back(i);
    }
}


int main() {
    ll x;
    cin >> x;
    if (isPrime(x)) {
        cout << x;
    } else {
        getPrime(x);
        ll i = primes.size() - 1;
        while (x != 1) {
            while (i >= 0) {
                if (x % primes[(int) i] == 0) {
                    x = x / primes[i];
                    if (flag.find(primes[i]) == flag.end()) {
                        flag[primes[i]] = 1;
                    } else {
                        flag[primes[i]]++;
                    }
                    break;
                } else {
                    i--;
                }
            }
        }
        ll ans = 1;
        for (auto it:flag) {
            if (it.second % 2) ans *= it.first;
        }
        cout << ans;
    }
    return 0;
}

剩下两题一道是模拟，一道不会.... 【菜鸟的题解到这里就结束了】