P8751 [蓝桥杯 2021 省 B2] 填空问题

Loser_Syx · 2023-01-08 21:05:15 · 题解

问题 A

思路：很简单，只要用 % 取余就可以了。

code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    cout << 2021 % 20; 
    return 0;
}

答案为 1。

问题 B

思路：

按照题目所给的公式，进行计算，由于题目说输出后五位， 所以我们每次乘完取余都需要 \bmod 100000。

code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    int ans = 1;
    for(int i = 2021; i >= 1; i -= 2){
        ans *= i;
        ans %= 100000;
    }
    cout << ans;
    return 0;
}

答案是 59375。

问题 C

思路：

直接暴力枚举出所有可能，枚举成边长 2021 的正方形就行了， 因为边长为 2022 时， 1 \times 2022 > 2021， 已经不可能了，再去判断 n \times m 是否 \leq 2021,如果是，则 ans+1。

code

#include <bits/stdc++.h>
using namespace std;
int main(){
    int ans = 0;
    for(int i = 1; i <= 2021; i++){
        for(int j = 1; j <= 2021; j++){
            if(i * j <= 2021){
                ans++;
            }
        }
    }
    cout << ans;
}

答案是 15698。

问题 D

思路：

五重暴力枚举，时间复杂度飘上天，但是这是提交答案题，不用管它，算出来填上去就行了！！！ （然后我就为此废了 1 小时的时间， 吓得我以为我的代码废了）。

code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long ans = 0;//不开longlong见祖宗
    for(int a = 1; a <= 2021; a++){
        for(int b = 1; b <= 2021; b++){
            for(int c = 1; c <= 2021; c++){
                for(int d = 1; d <= 2021; d++){
                    for(int e = 1; e <= 2021; e++){
                        if(a+b+c+d+e==2021){//暴力枚举
                            ans++;
                        }
                    }
                }
            }
        }
    }
    cout << ans;
}

时间复杂度实在太高，必须得想一些优化的办法，这时就有一种新的方法：

将 2021 拆分成 2021 个 1，则两个 1 之间有 2020 种方法种放置可能。问题中将 2021 分解成五个正整数的和也就是在 2020 种可能中选取 4 种放置方式，即可用组合数表示为 C^4_{2020}。

code:

#include <bits/stdc++.h>
using namespace std;
int main(){
    long long ans = 1;
    for(int i = 2020; i >= 2017; i--){
        ans *= i;
    }
    cout << ans / (4 * 3 * 2 * 1);
}

得到得数 691677274345。

问题 E

思路就是使用最小生成树和并查集，找到答案。

由于代码长度问题，就不贴了。

答案是 4046。

最后再把输入输出的模板套上去，就能 AC 了！！！