P8721 [蓝桥杯 2020 省 AB3]填空问题 题解

· · 题解

A.数青蛙

分析：

这一题一看就是一道数学题，首先，除了数字以外其他的汉字都是不用处理的，因为在每一句中都完全一样。

接着我们考虑数字的处理，根据题目的说法，我们可以知道：

令这个数字为 x。

如果 x\le10，则 x 只占一个汉字位。

如果 x\ne10 并且 x\bmod10=0，则 x 只占两个汉字位。

其余情况，x 占三个汉字位。

求解Code：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int ans = 200;
    for(int i = 1;i <= 20;i++){
        int a = i;
        int b = 2 * i;
        int c = 4 * i;
        if(a <= 10) ans++;
        else if(a < 20 || a % 10 == 0) ans += 2;
        else ans += 3;
        if(a <= 10) ans++;
        else if(a < 20 || a % 10 == 0) ans += 2;
        else ans += 3;
        if(b <= 10) ans++;
        else if(b < 20 || b % 10 == 0) ans += 2;
        else ans += 3;
        if(c <= 10) ans++;
        else if(c < 20 || c % 10 == 0) ans += 2;
        else ans += 3;
    }
    cout << ans;
}

答案：

最终运行代码，答案为 353。

B.互质

分析：

这题的数据量非常小，所以我们可以直接采取暴力枚举的办法，枚举从 1\sim2020 所有数与 1018 的最大公因数，如果为 1，就说明他们两个互质，反之就不互质。

求解Code：

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

答案：

最终运行代码，答案为 1008。

C.车牌

分析：

其实这一道题也可以采用暴力枚举的思路，枚举每一位车牌号的可能性，再判断该可能性是否成立，如果成立， 就 cnt+1，反之则继续枚举。

思路非常简单，但是就是要写六层循环呀！！！

求解Code：

#include<bits/stdc++.h>
using namespace std;
string s = "0123456789ABCDEF";
int ans;
int main(){
    for(int a = 0;a <= 15;a++){
        for(int b = 0;b <= 15;b++){
            for(int c = 0;c <= 15;c++){
                for(int d = 0;d <= 9;d++){
                    for(int e = 0;e <= 9;e++){
                        for(int f = 0;f <= 9;f++){
                            if(a==b&&a==c||b==c&&c==d||c==d&&d==e||d==e&&e==f) continue;
                            ans++;
                        }
                    }
                }
            }
        }
    }
    cout << ans;
}

答案：

最终运行代码，答案为 4002750。

D.Fibonacci 集合

分析：

这一道题可以运用广搜的思路，每一次取出队头元素，并且 将 cnt+1，如果 cnt = 2020，则输出队头元素，否则将队头元素的拓展状态插入队列。

但是要注意，为了保证取出的元素具有单调上升性，所以我们才有小根堆来解决这个问题。

求解Code：

#include<bits/stdc++.h>
//#pragma GCC opminize(2,3,"Ofast","inline")
#define endl '\n'
//#define int register int
//#define int long long
//#define double long double
const int N = 1e5 + 10,M = 1e5 + 10;
const double pi = 3.1415927;
using namespace std;
priority_queue<int,vector<int>,greater<int>> q;
bool a[N*10];
signed main(){
    ios::sync_with_stdio(false);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    //<----初始化---->
    q.push(1);
    q.push(2);
    q.push(3);
    q.push(5);
    q.push(8);
    a[1] = a[2] = a[3] = a[5] = a[8] = true;
    int ans = 0;
    while(!q.empty()){
        int x = q.top();
        q.pop();
        ans = ans + 1;
        if(ans==2020){
            cout << x;
            break;
        }
        int p = 3 * x + 2;
        int f = 5 * x + 3;
        int r = 8 * x + 5;
        if(!a[p]) q.push(p),a[p] = true;
        if(!a[f]) q.push(f),a[f] = true;
        if(!a[r]) q.push(r),a[r] = true;
    }
    return 0;
}

答案：

最终运行代码，答案为 41269。

E.上升子串

分析：

首先我们需要知道，上升子串的意思是保证序列中每一个元素都绝对大于前面所有元素。

那么再思考一下，如果我们要枚举出一个矩阵中所有的上升子串，好像有些困难。但是，如果我告诉你一个定点，让你从定点出发，枚举出其所有上升子串，这不就是 dfs 吗?

将一个矩阵分解成若干个不同的点，以每一个点出发，去跑一遍 dfs，最后输出方案总数即可。

求解Code：

因为该题没有测试数据，所以这里的代码仅作为一个验证代码。

#include<bits/stdc++.h>
//#pragma GCC opminize(2,3,"Ofast","inline")
#define endl '\n'
//#define int register int
//#define int long long
//#define double long double
const int N = 1e4 + 10,M = 1e5 + 10;
const double pi = 3.1415927;
using namespace std;
int n,m;
char a[N][N];
int ax[] = {-1,1,0,0};
int ay[] = {0,0,-1,1};
int dfs(int x,int y){
    int ans = 1;
    for(int i = 0;i <= 3;i++){
        int nx = x + ax[i];
        int ny = y + ay[i];
        if(a[nx][ny] > a[x][y]&&nx <= n && nx > 0 && ny <= m && ny > 0){
            ans = ans + dfs(nx,ny);
        }
    }
    return ans;
} 
signed main(){
    ios::sync_with_stdio(false);
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    //<----初始化---->
    cin >> n >> m;
    for(int i =1;i <= n;i++){
        for(int j =1;j <= m;j++){
            cin >> a[i][j];
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            ans = ans + dfs(i,j);
        }
    }
    cout << ans;
    return 0;
}

答案：

因为该题没有数据点，所以最终答案为 qwq。

AC CODE：

#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "353",
        "1008",
        "4002750",
        "41269",
        "qwq",
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}