题解：P8690 [蓝桥杯 2019 国 B] 填空问题

JacoAquamarine · 2024-09-28 15:26:04 · 题解

试题 A 平方序列

首先，根据等差数列的定义，满足：

令 x = 2019 + k，可得：

代码如下：

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    for (int k = 1; k <= 10000; ++k) {
        int x = 2019 + k;
        int y2 = 2019 * 2019 + 4 * 2019 * k + 2 * k * k;
        int y = sqrt(y2);
        if (y * y == y2) {
            cout<<x+y<<endl;
            return 0;
        }
    }
    return 0;
}

结果为 7060。

试题 B 质数拆分

由于只需计算出答案，所以没有时间限制，因此直接判断素数并将其加入 primes 即可，最后使用背包求解。 代码如下：

#include <iostream>
#include <vector>
using namespace std;
const long long MAX_N = 2020;
long long dp[MAX_N];
vector<long long> primes;
bool isPrime(long long x) {
    if (x < 2) return false;//质数大于等于2
    for (long long i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            return false;
        }
    }
    return true;
}
int main() {
    for (long long i = 2; i < MAX_N; ++i) {
        if (isPrime(i)) {
            primes.push_back(i);
        }
    }
    dp[0] = 1;//01背包
    for (long long prime : primes) {
        for (long long j = MAX_N - 1; j >= prime; --j) {
            dp[j] += dp[j - prime];
        }
    }
    cout << dp[2019] << '\n';
    return 0;
}

结果为 55965365465060。

试题 C 拼接

深搜，以对角线上的每个点为起点。 代码如下：

#include <iostream>
#include <cstring>
using namespace std;
const int kMaxN = 7;
const int direction[4][2] = {{0, -1}, {0, 1}, {1, 0}, {-1, 0}};
int ans = 0,v[kMaxN + 1][kMaxN + 1];
void dfs(int x, int y) {
    if (x == 0 || y == 7) {
        ans++; 
        return; 
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + direction[i][0];
        int ny = y + direction[i][1];
        if (nx < 0 || nx > 7 || ny <= nx || ny > 7 || v[nx][ny]) {
            continue;
        }
        v[nx][ny] = 1;//标记
        dfs(nx, ny);
        v[nx][ny] = 0; //回溯
    }
}
int main() {
    for (int i = 0; i <= 7; i++) {//搜索以对角线上的点为起点
        memset(v, 0, sizeof(v));
        v[i][i] = 1; //标记起点
        dfs(i, i); //开始深度优先搜索
    }
    printf("%d\n", ans);
    return 0;
}

结果为 2044。

试题 D 求值

暴力即可。

代码如下：

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    for (int i = 1; ; i++) {
        int cnt = 0;
        for (int j = 1; j <= static_cast<int>(sqrt(i)); j++) {
            if (i % j == 0) {
                cnt++;
                if (j * j != i) {
                    cnt++;
                }
            }
        }
        if (cnt == 100) {
            cout << i << endl;
            return 0;
        }
    }
    return 0;
}

结果为 45360。

试题 E 路径计数

从左上角开始搜索。

代码如下：

#include <iostream>
#include <cstring>
using namespace std;
const int kMaxN = 6;
const int d[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
long long ans = 0;
bool vis[kMaxN][kMaxN];
void dfs(int x, int y, int k) {
    if (k > 12) return;
    if (k >= 4 && x == 0 && y == 0) {
        ans++;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + d[i][0];
        int ny = y + d[i][1];
        if (nx < 0 || ny < 0 || nx >= kMaxN || ny >= kMaxN || vis[nx][ny]) {
            continue;
        }
        vis[nx][ny] = true; // 标记为已访问
        dfs(nx, ny, k + 1);
        vis[nx][ny] = false; // 回溯
    }
}
int main() {
    memset(vis, 0, sizeof(vis));
    dfs(0, 0, 0);
    cout << ans << endl;
    return 0;
}

结果为 206。

AC 代码

需注意将所有结果一起输出。

#include<iostream>
using namespace std;
int main() {
    string ans [] = {
        "7020", // 双引号中替换为 A 题的答案
        "55965365465060", // 双引号中替换为 B 题的答案
        "2444", // 双引号中替换为 C 题的答案
        "45360", // 双引号中替换为 D 题的答案
        "206", // 双引号中替换为 E 题的答案
    };
    char T;
    cin >> T;
    cout << ans[T - 'A'] << endl;
    return 0;
}