2019第十届蓝桥杯大赛软件类B组C/C++国赛题解

编程入门行业动态更新时间:2024-10-21 09:42:17

2019第十届蓝桥杯大赛软件类B组C/C++国赛<a href=https://www.elefans.com/category/jswz/34/1769599.html style= 题解"/>

2019第十届蓝桥杯大赛软件类B组C/C++国赛题解

2019第十届蓝桥杯大赛软件类B组C/C++国赛目录

- - 试题 A：平方序列（结果填空）
  - 试题 B：质数拆分（结果填空）
  - 试题 C：拼接（结果填空）
  - 试题 D：求值（结果填空）
  - 试题 E：路径计数（结果填空）
  - 试题 F：最优包含（程序设计）
- 一个大佬写了下面题目的答案，点击下面链接
- - 试题 G：排列数（程序设计）
  - 试题 H：解密游戏（程序设计）
  - 试题 I：第八大奇迹（程序设计）
  - 试题 J：燃烧权杖（程序设计）

试题 A：平方序列（结果填空）

题意：

做法：双重循环暴力找一找，把N定义成了1e4（赌不会很大）。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e4+10;
int main() {LL x = 2019*2019, y, z;LL rx = N, ry = N;for(int i = 2020; i < N; ++i) {for(int j = i+1; j < N; ++j) {y = i*i; z = j*j;if(z-y == y-x && i+j < rx+ry) rx = i, ry = j;}}cout << rx << " " << ry << " " << rx + ry << endl;return 0;
}

答案：7020

试题 B：质数拆分（结果填空）

题意：

做法：有坑，我一开始以为是两个素数相加，其实可以是多个。先素数筛出2019以内的素数，然后可以转化成01背包求方案数，也可以用记忆化搜索。答案有很多种，记得开long long。

代码：
1、01背包求方案数：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e4+10;
int p[N], v[N], res, tot;
LL dp[N];
int main() {for(int i = 2; i <= 2019; ++i) {if(v[i]) continue; p[++tot] = i; for(int j = i+i; j <= 2019; j += i) {v[j] = 1;}}dp[0] = 1;for(int i = 1; i <= tot; ++i) {for(int j = 2019; j >= p[i]; --j) dp[j] += dp[j-p[i]];}cout << dp[2019] << endl;return 0;
}

2、记忆化搜索

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3000;
int p[N], v[N], res, tot;
LL dp[400][N];
LL dfs(int pos, int sum) {if(pos == tot + 2 || sum > 2019) return 0;if(dp[pos][sum] != -1) return dp[pos][sum];if(sum == 2019) return 1;LL mid = 0;mid += dfs(pos+1, sum);mid += dfs(pos+1, sum+p[pos]);return dp[pos][sum] = mid;
}
int main() {for(int i = 2; i <= 2019; ++i) {if(v[i]) continue; p[++tot] = i; for(int j = i+i; j <= 2019; j += i) v[j] = 1;}memset(dp, -1, sizeof dp);cout << dfs(1, 0);return 0;
}

答案：55965365465060

试题 C：拼接（结果填空）

题意：

做法：要满足题目，分割方式必须是沿对角线对称之前想用dfs走到对角线的方式，写炸了，后来发现一个规律。首先右上角那一个必选（除了一种沿右边界分割的情况），第一行可以选1-7的格子，第二行能选1-6…并且右端一定靠近对角线，且下一行不能多余上一行，且连续。

n=3时情况如下：

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10;
const int ne[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int n = 3, a[N];
int res;
void dfs(int step, int x) {if(step >= n || !x) {++res; for(int i = 1; i <= n; ++i) cout << a[i] << " "; cout << endl;return;}for(int i = 0; i < x && n-step >= i; ++i) {a[step+1] = i;dfs(step+1, i);a[step+1] = 0;}
}
int main() { for(int i = 1; i <= n; ++i) {memset(a, 0, sizeof a);a[1] = i; dfs(1, i);}cout << res + 1;return 0;
}

答案：128

试题 D：求值（结果填空）

题意：

做法：枚举到1e5，判断约数个数是否等于100。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5+10;
const int ne[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int cal(int x) {int sq = sqrt(x), ans = 0;for(int i = 1; i <= sq; ++i) {if(x % i == 0) {++ans;if(x / i != i) ++ans;}}return ans;
}
int main() { for(int i = 100; i < N; ++i) {if(cal(i) == 100) {cout << i << endl; break;}}return 0;
}

答案：45360

试题 E：路径计数（结果填空）

题意：

做法：看成是6*6的方格，从(1,1)开始走，格子不能相交，问回到起点的路径有多少条。搜索。最后得减去(0,0)->(0,1)->(0,0)和(0,0)->(1,0)->(0,0)两种情况。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 10;
const int ne[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int tu[N][N], ans;
void dfs(int step, int x, int y) {if(step > 13) return;if(x == 1 && y == 1 && tu[x][y]) {++ans; return; }for(int i = 0, tx, ty; i < 4; ++i) {tx = x + ne[i][0], ty = y + ne[i][1];if(tx < 1 || ty < 1 || tx > 6 || ty > 6 || tu[tx][ty]) continue;tu[tx][ty] = 1;dfs(step+1, tx, ty);tu[tx][ty] = 0;}
}
int main() { dfs(1, 1, 1);cout << ans - 2;return 0;
}

答案：206

——以下题目可以通过 AcWing 提交测试——

试题 F：最优包含（程序设计）

题意：

做法：dp转移，dp[i][j]表示s[1:i]中要包含t[1:j]最少需要改变多少字母。
d p [ i ] [ j ] = { d p [ i − 1 ] [ j − 1 ] , 当 s [ i ] = = s [ j ] m i n ( d p [ i − 1 ] [ j ] , d p [ i − 1 ] [ j − 1 ] + 1 ) , 当 s [ i ] ! = s [ j ] dp[i][j] = \begin{cases} dp[i-1][j-1], 当s[i]==s[j] \\ min(dp[i-1][j], dp[i-1][j-1]+1), 当s[i]!=s[j] \end{cases} dp[i][j]={dp[i−1][j−1],当s[i]==s[j]min(dp[i−1][j],dp[i−1][j−1]+1),当s[i]!=s[j]

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1010;
const int ne[4][2] = {1, 0, 0, 1, -1, 0, 0, -1};
int dp[N][N];
char s[N], t[N];
int main() { memset(dp, 0x3f, sizeof dp);dp[0][0] = 0;scanf("%s%s", s+1, t+1);int ls = strlen(s+1), lt = strlen(t+1);for(int i = 1; i <= ls; ++i) {dp[i][0] = 0;for(int j = 1; j <= min(i, lt); ++j) {if(s[i] == t[j]) dp[i][j] = dp[i-1][j-1];else dp[i][j] = min(dp[i-1][j], dp[i-1][j-1]+1);}}printf("%d\n", dp[ls][lt]);return 0;
}

——下面的题目因太菜做不出来，放一个题面和大佬们的思路叭——