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

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

正文

总共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】

结语
感谢您的阅读！期待您的一键三连！欢迎指正！