十四届蓝桥杯省赛真题解析中E,F,G题讲解
目录
十四届蓝桥杯省赛真题解析（中）————E,F,G题讲解
题目E：接龙数列 在这里插入图片描述
思路分析：
这道题的本质是线性DP，我们观察发现下一个数的第一位和上一个数的最后一位是相同的，所以我们可以取出当前数的第一位X和最后一位Y，然后我们规定DP[i]就是以i为数字最后一位的最长接龙数列长度，那么只会存在DP[0]到DP[9],而我们如果选择当前数字接入队列，那么由于上一个数字的结尾也为X，状态转移方程就可以写为DP[x]+1即长度加1，如果不选当前数字，那么就还是以Y结尾状态就还是DP[i]，所以状态转移方程就为
dp[y]=max(dp[x]+1,dp[y])
作者题解：
#include<iostream>
#include<vector>
using namespace std;
int N, dp[10];
const int MAX_N = 1e5 + 5;
int main()
{
ios::sync_with_stdio, cin.tie(0), cout.tie(0);
cin >> N;
for (int i = 1; i <= N; i++)
{
int A;
cin >> A;
vector<int> d;
while (A)
{
d.push_back(A % 10);
A /= 10;
}
int y = *d.begin(), x = d.back();
dp[y] = max(dp[y], dp[x] + 1);
}
int len = 0;
for (int i = 0; i < 10; i++)len = max(len, dp[i]);
cout << N - len << endl;
return 0;
}运行结果：
题目F：岛屿个数
思路分析：
本题是小编认为本届蓝桥杯最难的一道题目，综合性比较强，有两个关键：
关键1：利用BFS找出存在的环，下图的黑色实线即为环状岛屿
关键2:看内部岛屿能否逃出外围岛屿，我们采用向8个方向搜素，只要到达地图边界，说明不是内部岛屿
如上图，蓝色岛屿可以从黄色缺口方向逃出
作者题解：
#include<iostream>
#include<queue>
using namespace std;
const int MAX_N = 51;
int M, N;
string mp[MAX_N];//读入地图
bool vis[MAX_N][MAX_N];//标记是否访问
bool used[MAX_N][MAX_N];
int dx[] = { 0,0,1,-1,1,-1,1,-1 };
int dy[] = { 1,-1,0,0,1,1,-1,-1 };//定义搜索的八个方向，前四个为上下左右，后四个为对角线
void bfs_col(int x, int y)//bfs染色模板，先找出一个环
{
queue<int>qx, qy;
qx.push(x); qy.push(y); vis[x][y] = 1;//标记为已走过
while (!qx.empty())
{
x = qx.front(); qx.pop();
y = qy.front(); qy.pop();
for (int i = 0; i < 4; ++i)//这里是4个方向，因为题目中说按上下左右四个方向成环没有说对角线
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || M <= nx || ny < 0 || N <= ny || vis[nx][ny] || mp[nx][ny] == '0')continue;//如果超出边界或者已访问过或者是海洋我们就不再搜索直接跳过，进行剪枝
qx.push(nx);
qy.push(ny);
vis[nx][ny] = 1;//否则加入队列，标记已经走过
}
}
}
bool bfs_out(int x, int y)
{
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
used[i][j] = 0;//这里的used同vis的作用一样
queue<int>qx, qy;
qx.push(x); qy.push(y); used[x][y] = 1;//标记为已走过
while (!qx.empty())
{
x = qx.front(); qx.pop();
y = qy.front(); qy.pop();
if (x == 0 || x == M - 1 || y == 0 || y == N - 1)return true;//递归出口如果我们逃到了边界就不是内部岛屿
for (int i = 0; i < 8; ++i)//这里是8个方向，因为我们求的是内部岛屿的逃跑线路
{
int nx = x + dx[i];
int ny = y + dy[i];
if (nx < 0 || M <= nx || ny < 0 || N <= ny || used[nx][ny] || mp[nx][ny] == '1')continue;//这里有一点不同就是我们要找的是海洋，即判断内部岛屿能否逃出环与外界海洋连通
qx.push(nx);
qy.push(ny);
used[nx][ny] = 1;//否则加入队列，标记已经走过
}
}
return false;
}
void solve()
{
cin >> M >> N;//读入M行N列的地图
for (int i = 0; i < M; ++i)
{
cin >> mp[i];
for (int j = 0; j < N; ++j)
vis[i][j] = 0;//初始化都为未访问过
}
int ans = 0;
for (int i = 0; i < M; ++i)
for (int j = 0; j < N; ++j)
if (!vis[i][j] && mp[i][j] == '1')
{
bfs_col(i, j);//染色圈出一个环
if (bfs_out(i, j))++ans;//判断是否存在子岛屿即是否能形成闭环
}
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio, cin.tie(0), cout.tie(0);
int t; cin >> t;
while (t--)solve();
return 0;
}运行结果：
题目G：子串简写
思路分析：
我们采用前缀和加上双指针来解决，我们先找出C1的位置有多少个，然后再以C2为右端点，反过来统计有多少个c1符合条件
作者题解：
#include<iostream>
using namespace std;
using ll = long long;
int K;
string S;
char c1, c2;
int main()
{
cin >> K >> S >> c1 >> c2;
int numberc1 = 0;
int n = S.size();
ll ans = 0;
for (int i = K - 1, j = 0; i < n; ++i, ++j)
{//我们让i,j始终保持k个间隔就满足了题目的条件
if (S[j] == c1)++numberc1;//先统计c1的位置有多少个
if (S[i] == c2)ans += numberc1;//再反过来统计符合条件的c1有多少个
}
cout << ans;
return 0;
}运行结果：
下期预告：H，I，J题讲解