题目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题讲解