Skip to main content

第十一届蓝桥杯国赛题解

PDF 下载链接：

点我下载

美丽的二​

image-20210517223017356

提示：

stl的运用，用string的find函数找一下就可以了

#include <iostream>
#include <string>

using namespace std;

int main() {
    int ans = 0;
    string year;
    for (int i = 1; i < 2021; ++i) {
        year = to_string(i);
        if (year.find('2') != year.npos) {
            ans += 1;
        }
    }
    cout << ans;
    return 0;
}
  • Ans: 563

扩散​

image-20210517223034240

提示：

其实还是stl的应用，会用标准库的话真的挺简单的。主要的思想就是用一个集合来存已经扩散后的格子，一个队列用来存储正在扩散的格子；

#include <iostream>
#include <set>
#include <queue>

using namespace std;

int loc[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};

struct ppair {
    int xx; // x坐标
    int yy; // y坐标
    int ss; // 步数
    ppair() {
        xx = 0;
        yy = 0;
        ss = 0;
    }

    ppair(int x, int y, int s) {
        xx = x;
        yy = y;
        ss = s;
    }
};


int main() {
    int ans = 4;
    set<pair<int, int>> points; // 存储已经扩散的点
    queue<ppair> que;
    // 将初始点加入队列当中
    que.push(ppair(0, 0, 0));
    que.push(ppair(2020, 11, 0));
    que.push(ppair(11, 14, 0));
    que.push(ppair(2000, 2000, 0));
    int i, j;
    int x, y;
    while (!que.empty()) {
        ppair point = que.front();
        x = point.xx;
        y = point.yy;
        if (!points.count(make_pair(x, y)) and point.ss <= 2020) {
            points.insert(make_pair(x, y));
            for (i = 0; i < 4; i++) {
                que.push(ppair(x + loc[i][0], y + loc[i][1], point.ss + 1));
            }
        }
        que.pop();
    }
    ans += points.size();
    cout << ans;
}
  • Ans: 20312092

阶乘约数​

image-20210517223047033

提示：

数论的题目，结论是每一个数都可以被分解为素数的乘积，将素数的乘积的幂次方加一后乘起来；

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

using namespace std;

bool judge(int n) {
    bool re = true;
    if (n <= 2) return re;
    for (int i = 2; i < n; ++i) {
        if (n % i == 0) {
            re = false;
            break;
        }
    }
    return re;
}

int main() {
    vector<int> p;
    // 计算100以内的所有素数
    for (int i = 2; i <= 100; ++i) {
        if (judge(i)) {
            p.push_back(i);
        }
    }
    map<int, int> count;
    for (int i : p) {
        count[i] = 1; // 在初始化的时候就+1
    }
    for (int i = 2; i <= 100; ++i) {
        int num = i;
        int j = 0;
        while (num != 1) {
            if (num % p[j] == 0) {
                num = num / p[j];
                count[p[j]]++;
            } else {
                j++;
            }
        }
    }
    long long res = 1;
    for (int i:p) {
        res *= count[i];
    }
    cout << res;
    return 0;
}
  • Ans: 39001250856960000

本质上升序列​

image-20210602214039344

提示：

动态规划：建立dp数组, dp[i]表示以num[i]为结尾的子序列个数，为什么可以这么想呢？因为我们已经确定了序列的最后一位是 num[i]

A: 假如num[j](j<i)是小于num[i]的, 那么dp[i]=dp[i]+dp[j]就是我们要求的答案。

B: 假如num[j](j<i)是等于num[i]的 dp[i]=dp[i]-dp[j], 这是因为该种情况已经被加进去了。为了去重所以是dp[i] - dp[j]

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

using namespace std;

int main() {
    string S = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";
    int dp[201];
    for (int i = 0; i < 201; ++i) {
        dp[i] = 1;
    }
    for (int i = 0; i < S.size(); ++i) {
        for (int j = 0; j < i; ++j) {
            if (S[i] > S[j]){
                dp[i] += dp[j];
            }
            if (S[i] == S[j]){
                dp[i] -= dp[j];
            }
        }
    }
    int res = 0;
    for (int i = 0; i < S.size(); ++i) {
        res += dp[i];
    }
    cout << res << endl;
    return 0;
}
  • Ans: 3616159

玩具蛇​

image-20210525224912929

提示：

使用dfs进行搜索，如果走了16步了说明是满足题述的一种情况。

#include "iostream"

using namespace std;
// 方向控制
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int a[4][4] = {0};
int n = 0;

// x,y相当于正在放置的格子的坐标
void dfs(int stay, int x, int y) {

    int tx, ty;
    // 递归终止条件
    if (stay == 16) {
        n++;
        return;
    }
    // 尝试向四个方向放置
    for (int i = 0; i < 4; i++) {
        tx = x + dx[i];
        ty = y + dy[i];
        // 该格子不可放置 或越界 跳过该方向
        if (a[tx][ty] == 1 || tx < 0 || tx > 3 || ty < 0 || ty > 3)
            continue;
        // 对已放置的格子进行标记
        a[tx][ty] = 1;
        dfs(stay + 1, tx, ty);
        // 清除标记
        a[tx][ty] = 0;
    }
}

int main() {
    int i, k;
    // 对4x4的格子 枚举玩具蛇第一个步放置的所有可能。
    for (i = 0; i < 4; i++) {
        for (k = 0; k < 4; k++) {
            // 对已放置的格子进行标记
            a[i][k] = 1;
            dfs(1, i, k);
            // 清除标记
            a[i][k] = 0;
        }
    }
    cout << n;
    return 0;
}
  • Ans：552