【第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;
}
H. 整数删除
【题目】整数删除
【分析】
- 考察优先队列和双向链表。
【AC_Code】
I. 景区导游
【题目】 景区导游
【分析】
【AC_Code】
J. 砍树
【题目】砍树
【分析】
【AC_Code】
结语
感谢您的阅读!期待您的一键三连!欢迎指正!