【第14届蓝桥杯】软件赛CB组省赛

在这里插入图片描述

个人主页：Guiat
归属专栏：算法竞赛真题题解

在这里插入图片描述

文章目录

A. 日期统计
B. 01串的熵
C. 冶炼金属
D. 飞机降落
E. 接龙数列
F. 岛屿个数
G. 子串简写
H. 整数删除
I. 景区导游
J. 砍树

正文

总共10道题。

A. 日期统计

【题目】日期统计

【分析】

【答案】235

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;int a[100] = 
{5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7,5, 9, 5, 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9,2, 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 3,8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5, 6, 5, 6,1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5, 0, 2, 5, 3, 3
}, month[13] = { 0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 }, ans;void solve()
{for (int m = 1; m <= 12; m ++) for (int d = 1; d <= month[m]; d ++){int data[8] = { 2, 0, 2, 3, m / 10, m % 10, d / 10, d % 10 }, k = 0;for (int i = 0; i < 100; i ++){if (a[i] == data[k]) { k ++; if (k == 8) { ans ++; break; } }}}cout << ans << '\n';
}int main()
{IOS; int _ = 1; // cin >> _;while (_ --) solve();return 0;
}

B. 01串的熵

【题目】01串的熵

【分析】

【答案】11027421

【AC_Code】

#include <iostream>
#include <cmath>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;double n = 23333333, sum;void solve()
{for (int i = 0; i <= n / 2; i ++){sum = 0; sum -= i * (i / n) * log2(i / n) + (n - i) * ((n - i) / n) * log2((n - i) / n);if (sum > 11625907.5 && sum < 11625907.6) { cout << i << '\n'; break; }}
}int main()
{IOS; int _ = 1; // cin >> _;while (_ --) solve();return 0;
}

C. 冶炼金属

【题目】冶炼金属

【分析】

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;int n, a, b, m, M = 2e9;void solve()
{cin >> n;for (int i = 1; i <= n; i ++){cin >> a >> b;int l = a / (b + 1) + 1, r = a / b;m = max(m, l); M = min(M, r);}cout << m << ' ' << M << '\n';
}int main()
{IOS; int _ = 1; // cin >> _;while (_ --) solve();return 0;
}

D. 飞机降落

【题目】飞机降落

【分析】
数据n的范围比较小，考虑暴力搜索。

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 15;
int t, n, T[N], D[N], L[N]; bool vis[N];bool dfs(int deep, int time)
{if (deep > n) return true;for (int i = 1; i <= n; i ++){if (vis[i] || T[i] + D[i] < time) continue;vis[i] = true;if (dfs(deep + 1, max(time, T[i]) + L[i])) { vis[i] = false; return true; }vis[i] = false;}return false;
}void solve()
{cin >> t;while (t --){cin >> n; for (int i = 1; i <= n; i ++) cin >> T[i] >> D[i] >> L[i];if (dfs(1, 0)) cout << "YES\n";else cout << "NO\n";}
}int main()
{IOS; int _ = 1; // cin >> _;while (_ --) solve();return 0;
}

E. 接龙数列

【题目】接龙数列

【分析】

【AC_Code】

#include <iostream>
#include <algorithm>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;const int N = 10;
int n, dp[N], maxn; string a;void solve()
{cin >> n;for (int i = 1; i <= n; i ++){cin >> a; int len = a.length();dp[a[len - 1] - '0'] = max(dp[a[len - 1] - '0'], dp[a[0] - '0'] + 1);}for (int i = 0; i < 10; i ++) maxn = max(maxn, dp[i]);cout << n - maxn << '\n';
}int main()
{IOS; int _ = 1; // cin >> _;while (_ --) solve();return 0;
}

F. 岛屿个数

【题目】岛屿个数

【分析】

【AC_Code】

#include <iostream>
#include <cstdio>
#define IOS ios :: sync_with_stdio(0); cin.tie(0);using namespace std;const int maxn = 55;
int T, M, N, a[maxn][maxn];void dfs_sea(int x, int y)
{int dx[] = { 0, 0, 1, 1, 1, -1, -1, -1 },dy[] =  { 1, -1, 0, 1, -1, 0, 1, -1 };if (x < 0 || x > M + 1 || y < 0 || y > N + 1) return;if (a[x][y] != 0) return;a[x][y] = 2;for (int i = 0; i < 8; ++i) dfs_sea(x + dx[i], y + dy[i]);
}void dfs_island(int x, int y)
{int dx[] = { 1, -1, 0, 0 },dy[] = { 0, 0, 1, -1 };if (x < 0 || x > M + 1 || y < 0 || y > N + 1) return;if (a[x][y] != 1) return;a[x][y] = 3;for (int i = 0; i < 4; ++ i) dfs_island(x + dx[i], y + dy[i]);
}void solve()
{cin >> T;while (T --){cin >> M >> N;for (int i = 0; i < N + 2; ++ i) { a[0][i] = 0, a[M + 1][i] = 0; }for (int i = 1; i < M + 1; ++ i) { a[i][0] = 0, a[i][N + 1] = 0; }for (int i = 1; i < M + 1; ++ i) for (int j = 1; j < N + 1; ++ j) scanf("%1d", &a[i][j]);dfs_sea(0, 0); int cnt = 0;for (int i = 0; i < M + 2; ++ i) for (int j = 0; j < N + 2; ++ j){if (a[i][j] == 1 && (i > 0 && a[i - 1][j] == 2)) dfs_island(i, j), cnt ++;}cout << cnt << '\n';
//      for (int i = 0; i < M + 2; i ++) for (int j = 0; j < N + 2; j ++)
//      {
//      	printf("%ld", a[i][j]); if (j == N + 1) cout << '\n';
//      }}
}int main()
{// IOS;int _ = 1; // cin >> _;while (_ --) solve();return 0;
}

G. 子串简写

【题目】子串简写

【分析】

两个计数变量c1_sum和cnt比较大，得开long long。
题干出现字符串的两个边界c1，c2，考虑用滑动窗口解题。
使用两个指针i，j，类似于快慢指针，i从0到S.length() - K，j从K - 1到S.length() - 1。
对于每个窗口，如S[i] == c1，则c1_sum加1;
如S[j] = c2，则将c1_sum的值累加到cnt。
最后输出总组合数cnt。

【AC_Code】

#include <iostream>
#define IOS ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);using namespace std;
using ll = long long;int K; string S; char c1, c2; ll c1_sum, cnt;void solve()
{cin >> K >> S >> c1 >> c2;for (int i = 0, j = K - 1; j < S.length(); i ++, j ++){if (S[i] == c1) c1_sum ++;if (S[j] == c2) cnt += c1_sum;}cout << cnt << '\n';
}int main()
{IOS; int _ = 1; // cin >> _;while (_ --) solve();return 0;
}