蓝桥杯 第十届 决赛 选讲题解 C++ 下半部分（编程题）
2021/5/30 1:20:49
本文主要是介绍蓝桥杯 第十届 决赛 选讲题解 C++ 下半部分（编程题），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
试题：最优包含
题目描述：
我们称一个字符串 S 包含字符串 T 是指 T 是 S 的一个子序列，即可以从字符串 S 中抽出若干个字符，它们按原来的顺序组合成一个新的字符串与 T 完全一样。
给定两个字符串 S 和 T，请问最少修改 S 中的多少个字符，能使 S 包含 T ？
其中， 1 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 1000 ， 1 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 10001 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 1000 ， 1 ≤ ∣ T ∣ ≤ ∣ S ∣ ≤ 1000 1 \leq |T| \leq |S| \leq 1000，1≤∣T∣≤∣S∣≤10001≤∣T∣≤∣S∣≤1000，1≤∣T∣≤∣S∣≤1000 1≤∣T∣≤∣S∣≤1000，1≤∣T∣≤∣S∣≤10001≤∣T∣≤∣S∣≤1000，1≤∣T∣≤∣S∣≤1000。
解析：
这道题目，首先，我们先不看正确的答案，然后我们自己写一个dfs看看。毕竟dfs是万能的（笑）。
我们设dfs（N，M）的意思是：对S的字符串的0->N-1和T字符串的0->M-1。安装题目的要求，存入修改多少个S中的字符满足题意的那个数字（或者说是return这个数字）。
现在字符串的下标不是从0开始，而是从1开始。我的习惯就是如此。
那题目的答案就是求出dfs（S.length，T.length）
dfs的思想是，本层和下一层（或上一层）。我们现在本层是（9，5）：可以理解为：一个指针指在S[9]一个指针指在T[5]。那么我们上一层（因为我觉得说上一层更符合思想）就是指针分别往前移动。请往下看，来理解。
比如我们看题目中的样例，那么最终答案就是dfs(9,5)
那我们怎么求dfs(9,5)呢？
如果S[9]==T[5]。这种状态跟dfs(8,4)是一模一样的，因为我们根本就不需要做S的修改。所以dfs(9,5)==dfs(8,4)
但是しかし，非常的遗憾通知您，S[9]！=T[5]那我们怎么办呢？
（1）[修改S字符串方法] ：我们可以修改S[9]为为“Z”，那么现在dfs(9,5)==dfs(8,4)+1。（别忘记我们规定的dfs的含义。现在我S[9]和T[5]我都不选择，然后改变一个S[9]为“Z”在次转移到dfs(9,5)现在就包含了S[9]和T[5]）。
（2）[不修改S字符串的方法] ：我们可以试探一下dfs(8,5)也就是看看：
紫色圈圈圈出的这部分，能不能得到答案。如果dfs(8,4)返回一个巨大无比的数字，我们就认为是之前不能搞出一个解的。也就是如果不修改字符串S就是行不通的。
最后：dfs(9,5)=min(dfs(8,4)+1,dfs(8,5));
考虑边界：
（1）|S|<|T|：无论S怎么修改都不可能配出T字符串，因为S长度太短了。
（2）|T|==0：T字符串是一个空串，不需要修改字符串S了。
正解dfs代码：
#include <cstring>
#include <iostream>
using namespace std;
string S, T;
int S_len, T_len;
int dfs(int s_p, int t_p) {
if (t_p > s_p) {
return 9999999999;
}
if ((s_p == 0 && t_p == 0) || t_p == 0) {
return 0;
}
if (S[s_p] == T[t_p]) {
return dfs(s_p - 1, t_p - 1);
} else {
return min(dfs(s_p - 1, t_p - 1) + 1, dfs(s_p - 1, t_p));
}
}
int main() {
cin >> S >> T;
S.insert(S.begin(), ' '); //手动将S和T的下标从1开始。
T.insert(T.begin(), ' ');
S_len = S.length() - 1; //记录一下S和T字符串的长度，不要忘记前面的''
T_len = T.length() - 1;
cout << dfs(S_len, T_len);
return 0;
}
解析2：
说到这里，你一定会发现，其实dfs运算是很浪费的，因为会对同一个点（s_p，t_p）进行访问多次。所以我们想到了状态缓存，也叫动态规划。（淦，为什么叫动态规划其实我也不明白为什么）
然后其实我们当时推出dfs的递归公式的时候，也就把dp的公式给推到出来了，简直就是一模一样，我们稍微改写：
正解代码（动态规划）：
#include <cstring>
#include <iostream>
using namespace std;
string S, T;
int S_len, T_len;
int dfs[1001][1001];
int main() {
cin >> S >> T;
S.insert(S.begin(), ' '); //手动将S和T的下标从1开始。
T.insert(T.begin(), ' ');
S_len = S.length() - 1; //记录一下S和T字符串的长度，不要忘记前面的''
T_len = T.length() - 1;
dfs[0][0] = 0; //边界嘛。
for (int i = 1; i <= S_len; i++) { // S_p
dfs[i][0] = 0; //和dfs是一样的。因为T为0，那么S根本就不用修改
for (int j = 1; j <= T_len; j++) { // T_p
if (j > i) {
dfs[i][j] = 999999999; //这里赋值这么大，是因为为了下一层有可能访问到TA，所以搞大一点。
continue;
}
if (S[i] == T[j]) {
dfs[i][j] = dfs[i - 1][j - 1];
} else {
dfs[i][j] = min(dfs[i - 1][j], dfs[i - 1][j - 1] + 1);
}
}
}
cout << dfs[S_len][T_len];
return 0;
}
吐槽一句：我这里建议蓝桥杯直接改名字好啦，改成动态规划杯，嘻嘻嘻（我可是一只调皮的熊哦~）
试题：排列数
题目描述：
题意
在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。
对于一个 1 ∼ n 的排列，如果可以将这个排列中包含 t 个折点，则它称为一个 t + 1 单调序列。 例如，排列 (1,4,2,3)(1,4,2,3)(1,4,2,3) 是一个 3 单调序列，其中 4 和 2 都是折点。 给定 n 和 k，请问 1 ∼ n 的所有排列中有多少个 k 单调队列？
输入输出描述
输 入 一 行 包 含 两 个 整 数 n , k ( 1 ≤ k ≤ n ≤ 500 ) n , k ( 1 ≤ k ≤ n ≤ 500 ) 。 输入一行包含两个整数 n,k (1≤k≤n≤500)n,k(1≤k≤n≤500)。 输入一行包含两个整数n,k(1≤k≤n≤500)n,k(1≤k≤n≤500)。
输出一个整数，表示答案。答案可能很大，你可需要输出满足条件的排列数量除以 123456 的余数即可。
输入输出样例
输入：4 2
输出：12
分析：
高中数学回顾：
本题目是排列组合问题，依旧是一个动态规划的问题。
首先排列组合本身就是一个动态规划。
比如我们有3个数，1，2，3。总共可以组合6种不同位置的数字。
比如：123 132 312 213 231 321
我们高中学过一个公示，如果有n个数子，那么它的排列数（全排列）是 n ！ n！ n！。比如上面的3个数字的全排列就是 1 ∗ 2 ∗ 3 1*2*3 1∗2∗3。
为什么是这个样子呢，比如我们看数字“3”是怎么排列的。
（1）我们可以先排列前两个数字1 2总共两种可能：1 2 2 1
（2）然后我们插入3到空隙中。(空隙)1(空隙)2(空隙)然后变成3 1 2 1 3 2 1 2 3而(空隙)2(空隙)1(空隙)也是一模一样的样子。所以最后是6种。
也就是，前2个数字有2种方法，而前2个数字每种方法有3个空隙，所以直接 2 ∗ 3 2*3 2∗3。（数字1只有一种位置可以放，所以最终 1 ∗ 2 ∗ 3 1*2*3 1∗2∗3）
题目解析：
现在，我们来看看这道题目吧！
假设我们现在有一个序列，它是拥有3个折点。
不过在继续下一步之前，我想先定义一些东西：
然后我们现在思考：
（1）三个折点可以全部是突折点或者凹折点吗？
这是不可能的，这是因为两个凸折点链接在一起，一定会产生一个凹折点。同理的，两个凹折点链接在一起会产生一个凸折点。
所以：当折点的个数是偶数的时候，凸折点和凹折点的个数应该是一样的。而当折点的个数是奇数的时候。要么有折点总数 整除 2个凸折点或者凹折点，剩下的就是凹折点或者凸折点。
（2）折点个数为3的序列大体看上去是什么样子的？
现在我们有5个数字，1，2，3，4，5。如下图，下图有三个折点。
（作图软件：Ms PowerPoint）
当然，下面的这张图片也有3个折点：
那么总体来说：从远处看，我们可以看到的就是这两种情况：
（作图软件：画图）
但是如果现在不仅仅有6个数字，而有很多个位置呢？
其中实心黑色的地方就是数字存在的位置。
（3）动态规划该怎么转移呢？
增加0个凸点：
比如现在，我们在往后面加上一个数字，这个数字比前面的所有数字都要大。
现在我们设置状态数组d
p
[
N
]
[
M
]
p[N][M]
p[N][M]表示：前N个数字（这些数字从小到大排列）然后M表示折点的个数。
（参照上面用Ms PowerPoint画出的图片）
首先需要理解
d
p
[
5
]
[
3
]
dp[5][3]
dp[5][3]是包含了全部的M和W这样形状的全部组合的个数。如果我们递推是正确的话，您完全不用担忧
d
p
[
5
]
[
3
]
dp[5][3]
dp[5][3]存放的是错误的答案。所以就请相信，里面存放了所有的W和M形状的组合的个数吧！
现在看看第六个数字插入的位置。
插入在No.X位置上的数字六不会对折点的个数有一点点的影响。
插入No.2和No.3位置上的数字六也不会对折点产生影响。
（总共4个位置，这种情况有一个凸点）
而M形状的也是同样的情况：
还是4个点。（这时候有两个凸点，一个凸点就会产生两个这样拆入却不增加折点的空隙，上上图中虽然只有一个凸点，但是它左右两边是上升的，所以还是不会增加凸点。）
偶数凸点也是一样哦，请自己在纸上画一画。
所以我们最终找到的规律是：增加0个折点的方法是：
M
/
2
∗
2
+
1
M/2*2+1
M/2∗2+1
(M是上面定义的dp数组的折点的个数）
增加1个凸点：
偶数折点也是同样的，请读者自行验证。
增加3个折点：
那么就是前面所有的空隙排除“增加0个折点和增加1个折点”的空隙剩下的位置。
可能说的比较乱上面的话，我的意思就是，找出所有能增加两个折点的空隙。
（N设实心点的个数，M是折点的个数，还记得我们定义的dp公式吗？）
那么就是N个实心点，有N-1个空隙。
然后N个节点，只考虑在n个节点直接的空隙，在n节点之外的空隙，比如最前和最末尾不在考虑范围之内。
总共
N
−
1
N-1
N−1减去红色的点（折点+0）
M
/
2
∗
2
M/2*2
M/2∗2在减去橙色的点（折点+1）有一个。
最终化简为 N − M − 2 N-M-2 N−M−2。
其他位置还请读者自行思考。（笑）
（图片来源：蓝桥杯官方教材“决赛训练营”https://www.lanqiao.cn/courses/3981/learning/?id=134743）
现在我们有了终极递推式：
d
p
[
i
+
1
]
[
j
]
+
=
d
p
[
i
]
[
j
]
∗
(
j
+
1
)
;
dp[i+1][j] += dp[i][j] *(j+1);
dp[i+1][j]+=dp[i][j]∗(j+1);
d
p
[
i
+
1
]
[
j
+
1
]
+
=
d
p
[
i
]
[
j
]
∗
2
;
dp[i+1][j+1] += dp[i][j]*2;
dp[i+1][j+1]+=dp[i][j]∗2;
d
p
[
i
+
1
]
[
j
+
2
]
+
=
(
d
p
[
i
]
[
j
]
∗
(
i
−
j
−
2
)
)
;
dp[i+1][j+2] += (dp[i][j]*(i-j-2));
dp[i+1][j+2]+=(dp[i][j]∗(i−j−2));
正解代码：
#include<cstdio>
#include<iostream>
using namespace std;
const int mod = 123456;
int n, k, dp[1009][1009];
int main() {
cin >> n >> k;
dp[1][0] = 1;//一个数字，折点为0个，这样的方案有一种
for (int i = 2; i <= n; i++) {
dp[i][0] = 2;//没有这点，要么n个数字单调递增，要不然单调递减，总共两种。
for (int j = 0; j <= i - 2; j++) {
//从dp[i][j]往后面的状态推。
dp[i + 1][j] = (dp[i + 1][j] + (dp[i][j] * (j + 1)) % mod) % mod; //增加0个折点
dp[i + 1][j + 1] = (dp[i + 1][j + 1] + (dp[i][j] * 2) % mod) % mod; //1个折点
dp[i + 1][j + 2] = (dp[i + 1][j + 2] + (dp[i][j] * (i - j - 2)) % mod) % mod; //2个折点。
}
}
cout << dp[n][k - 1] % mod << endl;
return 0;
}
蓝桥杯，动态规划杯！蓝桥杯，动态规划杯！蓝桥杯，动态规划杯！
感受就是，如果想要考蓝桥杯国赛要拿一个国二，动态规划一定要好好学哦~
试题：解密游戏
题目描述：
题意：
小明正在玩一款解谜游戏。谜题由 24 根塑料棒组成，其中黄色塑料棒 4 根，红色 8 根，绿色 12 根 (后面用 Y 表示黄色、R 表示红色、G 表示绿色)。初始时这些塑料棒排成三圈，如上图所示，外圈 12 根，中圈 8 根，内圈 4 根。
小明可以进行三种操作：
-
将三圈塑料棒都顺时针旋转一个单位。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么顺时针旋转一次之后，外圈、中圈、内圈依次变为：GYRYGRYGRGGG、 YRGRGGRR 和 RGGG。
-
将三圈塑料棒都逆时针旋转一个单位。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么逆时针旋转一次之后，外圈、中圈、内圈依次变为：RYGRYGRGGGGY、 GRGGRRYR 和 GGRG。
-
将三圈 0 点位置的塑料棒做一个轮换。具体来说：外圈 0 点塑料棒移动到内圈 0 点，内圈 0 点移动到中圈 0 点，中圈 0 点移动到外圈 0 点。例如当前外圈从 0 点位置开始顺时针依次是 YRYGRYGRGGGG，中圈是 RGRGGRRY，内圈是 GGGR。那么轮换一次之后，外圈、中圈、内圈依次变为：RRYGRYGRGGGG、GGRGGRRY 和 YGGR。
小明的目标是把所有绿色移动到外圈、所有红色移动中圈、所有黄色移动到内圈。给定初始状态，请你判断小明是否可以达成目标？
输入描述：
第一行包含一个整数 T ( 1 ≤ T ≤ 100 ) T (1≤T≤100) T(1≤T≤100)，代表询问的组数。
每组询问包含 3 行：
- 第一行包含 12 个大写字母，代表外圈从 0 点位置开始顺时针每个塑料棒的颜色。
- 第二行包含 8 个大写字母，代表中圈从 0 点位置开始顺时针每个塑料棒的颜色。
- 第三行包含 4 个大写字母，代表内圈从 0 点位置开始顺时针每个塑料棒的颜色。
输出描述：
对于每组询问，输出一行 YES 或者 NO，代表小明是否可以达成目标。
解析：
想法：
这道题目是一道只要求输出“YES”或者“NO”的那一类题型。
这里我参考了一位大佬的方案，想看他的解析请移步：https://blog.csdn.net/m0_45210226/article/details/109634102
那么，我们怎么去思考他呢，我一开始思考的是写一个dfs，不停转动，然后改变次序呗，但是这样复杂度就炸天了。
然后我又想会不会是动态规划，但是没有想出来。后来看了上面大佬的博客，思路一下子就打开了。
首先：您必须明白，到底为什么，游戏会失败，也就是，为什么，配凑不出来。
这是因为，比如内圈的0号位置，它永远只能和中圈的0号位置和4号位置相互交换。不行的话，现在请你拿出两根手指，然后一根指在内圈0号位置，一根指在外圈的0号位置，顺时针转动4下，然后再转动4下。之后，你就明白我说的意思了。
好的，现在我们知道：
(1)如果现在他们颜色全部为黄色（或其他同一种颜色），那么永远不可能交换出正确的颜色。游戏无效。
(2)如果现在有两个黄色，也是不正确的，因为实在不能将所有的黄色都排在一个内圈的位置上，总有一个黄色会留在外圈。游戏无效。
(3)所以，最好的情况是，只有一个黄色，然后可以放进“内圈0号位置”。
但是不要忘记：我们还有一个外圈没有考虑，但是实际情况是一样的。
（图片引用自：https://blog.csdn.net/m0_45210226/article/details/109634102）
外圈对应3个位置。请看图片。然后按照这样子划分区域的话，总共能画出4大类。
上面的蓝色是一类。
上图就是对应的四大类。
每种类型必须要求有且只有“1个黄色”“2个红色”“3个绿色”。要不然就是怎么操作都满足不了游戏的要求。
正确性验证：
现在我们定义N_M当N=1，2，3的时候分别代表 内圈 中圈 外圈。而M则是位置。
比如1_1代表中圈第一个位置。
现在我们有：
那么（1_0,2_0,3_0)这样的位置都有机会对应一次吗？
如果你朝着一个方向循环6次，那么上面所有的位置都会被对应一次。
手动证明完毕，嘿嘿。
正解代码：
#include<bits/stdc++.h>
using namespace std;
int t;
string s1,s2,s3;
int main(){
//freopen("a.txt","r",stdin);
cin>>t;
while(t--){
int flag = 0;
cin>>s3>>s2>>s1;
for(int i = 0;i<4;i++){ //分成了四大类
map<char ,int>mp;
//内圈
mp[ s1[i] ] += 1;
//中圈
mp[ s2[i] ] += 1;
mp[ s2[ i+ 4]] += 1;
//外圈
mp[ s3[i] ] += 1;
mp[ s3[ i+4]] += 1;
mp[ s3[i+8]] += 1;
if(mp['Y'] != 1 || mp['R'] != 2 || mp['G'] != 3){
flag = 1;
break;
}
}
if(flag == 0)
cout<<"YES"<<endl;
else{
cout<<"NO"<<endl;
}
}
return 0;
}
这篇关于蓝桥杯 第十届 决赛 选讲题解 C++ 下半部分（编程题）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-26MATLAB 中 A(7)=[];什么意思？-icode9专业技术文章分享
- 2024-11-26UniApp 中如何实现使用输入法时保持页面列表不动的效果？-icode9专业技术文章分享
- 2024-11-26在 UniApp 中怎么实现输入法弹出时禁止页面向上滚动？-icode9专业技术文章分享
- 2024-11-26WebSocket是什么，怎么使用？-icode9专业技术文章分享
- 2024-11-26页面有多个ref 要动态传入怎么实现？-icode9专业技术文章分享
- 2024-11-26在 UniApp 中实现一个底部输入框的常见方法有哪些？-icode9专业技术文章分享
- 2024-11-26RocketMQ入门指南：搭建与使用全流程详解
- 2024-11-26RocketMQ入门教程：轻松搭建与使用指南
- 2024-11-26手写RocketMQ：从入门到实践的简单教程
- 2024-11-25【机器学习(二)】分类和回归任务-决策树(Decision Tree,DT)算法-Sentosa_DSML社区版
