2020蓝桥杯国赛

相关题目：PDF

A.美丽的2

答案：563

B.扩散

宽搜。搜的时候注意加上一个偏移量，否则数组会有负数。

答案：20312088

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

#define x first
#define y second

const int N = 10000, D = 4000; // 4000的偏移量，防止负数

int a[N][N];
int dx[4] = {0, -1, 0, 1}, dy[4] = {1, 0, -1, 0};
int res = 4;

void bfs() {
    // 初始化点
    a[0 + D][0 + D] = a[2020 + D][11 + D] = 1;
    a[11 + D][14 + D] = a[2000 + D][2000 + D] = 1;
    //
    int minutes = 0; // 第0分钟
    int times = 4; // 前一次轮回有4个点被涂黑
    queue<PII> q;
    // 加入到队列中，开始搜索
    q.push({0 + D, 0 + D});q.push({2020 + D, 11 + D});
    q.push({11 + D, 14 + D});q.push({2000 + D, 2000 + D});
    while (q.size()) {
        int now = times;
        times = 0; // 清空计数
        // 取出times个点，开始涂黑
        for (int i = 0; i < now; ++ i) {
            PII ing = q.front();
            q.pop();
            // 四个方向
            for (int j = 0; j < 4; ++ j) {
                int nex = ing.x + dx[j], ney = ing.y + dy[j];
                if (a[nex][ney] == 0) {
                    a[nex][ney] = 1;
                    times ++;
                    res ++;
                    q.push({nex, ney});
                }
            }
        }
        minutes ++;
        if (minutes == 2020) break;
    }
}

int main (){
    bfs();
    cout << res << endl;
    
    return 0;
}

C.阶乘约数

对于一个数，不同的质因数乘积就是一个因数。题目是求100的阶乘的因数，那么可以对每个数1～100求质因数，然后每一个质因数的指数+1的乘积就是答案。

答案：39001250856960000

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

map<int, int> m;
map<int, int>::iterator it;

long long res = 1;

void getP(int x) {
    for (int i = 2; i <= x / i; ++ i) {
        if (x % i == 0) {
            while (x % i == 0) {
                m[i] ++;
                x /= i;
            }
        }
    }
    if (x > 1) m[x] ++;
}

int main (){
    for (int i = 1; i <= 100; ++ i) {
        getP(i);
    }
    // 每一个质因数的指数+1 的乘积
    for (it = m.begin(); it != m.end(); ++ it) {
        res *= it->second + 1;
    }
    cout << res;
    
    return 0;
}

D.本质上升序列

现在还没弄懂

E.玩具蛇

枚举玩具蛇头的位置，然后深搜往下搜到蛇的长度是16时停止

答案：552

#include <bits/stdc++.h>

using namespace std;

const int N = 4;
int snack[N][N];
int res;

void bfs(int i, int j, int length) {
    if (length == 16) res++;
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};  // 偏移量
    for (int k = 0; k < 4; ++k) {
        int x = i + dx[k], y = j + dy[k];
        // 如果蛇能放下去
        if (snack[x][y] == 0 && x >= 0 && x < N && y >= 0 && y < N) {
            snack[x][y] = 1;
            bfs(x, y, length + 1);
            snack[x][y] = 0;
        }
    }
}

int main() {
    for (int i = 0; i < 4; ++i) {
        for (int j = 0; j < 4; ++j) {
            snack[i][j] = 1;
            bfs(i, j, 1);
            snack[i][j] = 0;
        }
    }
    cout << res;
    return 0;
}