2023 蓝桥杯题解 （弱鸡版本）_蓝桥杯飞机降落

队长51假期留给我们的作业，大家就看个乐呵就行。

D.飞机降落

【问题描述】

N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻 到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早 可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li 个单位时间。 一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不 能在前一架飞机完成降落前开始降落。 请你判断 N 架飞机是否可以全部安全降落。

题解 ： 数据太小了 ， 本来一眼贪心 ， 一看数据范围100 ， 直接bf是就能过

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1001;
int T, n;
int t[N], d[N], l[N];
bool st[N];
bool flag = false;
 
void dfs(int k , int time)
{
    if (k == n - 1) // 最后一个飞机 ，可以直接降落
    {
        flag = true;
        return;
    }
 
    for (int i = 0; i < n; i++)
    {
        if ( !st[i] )
        {
            if ( t[i] + d[i] >= time ) // 当飞机可以降落时
            {
                st[i] = true; // st 是当前飞机i=用没用
                dfs( k + 1, max(time + l[i], t[i] + l[i]) );
                st[i] = false; // 找完了放回去，为其他案例做预备
            }
        }
    }
 
}
void solve()
{
    flag = false;
    cin >> n;
 
    memset(st,0,sizeof st); // 多组数据 ， 需要初始化 
 
    for (int i = 0; i < n; i++)
        cin >> t[i] >> d[i] >> l[i];
 
    for (int i = 0; i < n; i++) // 每个飞机 都需要 bfs一遍
    {
        if (!st[i])
        {
            st[i] = true;
            dfs(0, t[i] + l[i]); 
            st[i] = false;
        }
    }
 
    if (flag)
        cout << "YES" << endl;
    else
        cout << "NO" << endl;
}
 
int main()
{
    cin >> T;
    while (T--)
        solve();
 
    return 0;
}
 
/*
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
*/

E. 接龙数列

【问题描述】

对于一个长度为 K 的整数数列：A1, A2, . . . , AK，我们称之为接龙数列当且 仅当 Ai 的首位数字恰好等于 Ai−1 的末位数字 (2 ≤ i ≤ K)。 例如 12, 23, 35, 56, 61, 11 是接龙数列；12, 23, 34, 56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。所有长度为 1 的整数数列都是接龙数列。 现在给定一个长度为 N 的数列 A1, A2, . . . , AN，请你计算最少从中删除多少 个数，可以使剩下的序列是接龙序列？

// 简单的动态规划的题 , 用数组 f 存储从1 到 n 最长的接龙数列的长度，最后用 n 减去 f[n]就是答案

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 10;
 
int f[N];
int a[N], last[N], st[N];
int n;
 
int get_the_first_number(int n) //两个辅助函数 ， 辅助 check 函数 
{
    while (n)
    {
        int t = n % 10;
        n /= 10;
        if (n == 0)
            return t;
    }
    return 0;
}
 
int get_the_last_number(int n)
{
    return n % 10;
}
 
bool check(int a, int b) // 比较两个 数字是否可以 形成接龙数列
{
    int a_last = get_the_last_number(a);
    int b_first = get_the_first_number(b);
 
    if(a_last==b_first)
        return true;
    return false;
}
 
int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
 
    for (int i = 1; i <= n; i++)
    {
        f[i] = f[i - 1];
        st[i] = st[i - 1];
        if (i == 1 || check(st[i], a[i])) // 动态规划 ， 存贮的都是当前最大的接龙数列
        {
            f[i]++;
            st[i] = a[i];
        }
    }
 
    cout<<n-f[n]<<endl; // 总的减去最大的就是答案
 
    return 0;
}

A.字符串统计

【问题描述】

小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的 范围之内。数组中的元素从左至右如下所示： 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 现在他想要从这个数组中寻找一些满足以下条件的子序列： 1. 子序列的长度为 8； 2. 这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且 要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。 yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只 有一位时需要一个前导零补充。 请你帮小蓝计算下按上述条件一共能找到多少个不同 的 2023 年的日期。 对于相同的日期你只需要统计一次即可。

// 暴力bfs ， 详情看注释 ， 答案 235

#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e2 + 1;
int a[N];
 
set<int> s;
 
bool check(int date) // 检查日期是否合法
{
    int mm = date / 100 % 100;
    int dd = date % 100;
    if (mm < 1 || mm > 12)
        return false;
    if (mm == 1 || mm == 3 || mm == 5 || mm == 7 || mm == 8 || mm == 10 || mm == 12)
    {
        if (dd >= 1 && dd <= 31)
            return true;
    }
    else if (mm == 2)
    {
        if (dd >= 1 && dd <= 28)
            return true;
    }
    else if (dd >= 1 && dd <= 30)
        return true;
 
    return false;
}
// cnt 记录当前 有几个 数字 
void dfs(int x, int cnt, int date)
{
    if (x == 100)
        return;
        // 一百个就停了 从 0 开始的
 
    if (cnt == 8) // 八个一chek
    {
        if (check(date))
            s.insert(date);
        return;
    }
 
    if (cnt == 0)//初始化init
        date = 0;
// 判断每个位置的合法与否
    if ((cnt == 0 && a[x] == 2) || (cnt == 1 && a[x] == 0) || (cnt == 2 && a[x] == 2) || (cnt == 3 && a[x] == 3) || (cnt == 4 && a[x] >= 0 && a[x] <= 1) || (cnt == 5 && a[x] >= 0 && a[x] <= 9) || (cnt == 6 && a[x] >= 0 && a[x] <= 3) || (cnt == 7 & a[x] >= 0 && a[x] <= 9))
        dfs(x + 1, cnt + 1, date * 10 + a[x]); // 合法可以选
 
    dfs(x + 1, cnt, date); // 不选
}
 
int main()
{
    for (int i = 0; i < 100; i++)
        cin >> a[i];
    dfs(0, 0, 0);
    cout << s.size() << endl;
 
    return 0;
}

B . 串的熵

【问题描述】

对于一个长度为 n 的 01 串 S = x1 x2 x3...xn，香农信息熵的定义为 H(S ) = −Σ n 1 p(xi)log2 (p(xi))，其中 p(0), p(1) 表示在这个 01 串中 0 和 1 出现的占比。 比如，对于 S = 100 来说，信息熵 H(S ) = − 1 3 log2 ( 1 3 ) − 2 3 log2( 2 3 ) − 2 3 log2 ( 2 3 ) = 1.3083。对于一个长度为 23333333 的 01 串，如果其信息熵为 11625907.5798， 且 0 出现次数比 1 少，那么这个 01 串中 0 出现了多少次？

直接暴力就能做 ， 直接看代码

#include <bits/stdc++.h>
using namespace std;
 
const int N = 23333333,M = N/2;
long double eps = 11625907.5798; // 题目里给定  
 
int lmr(int i)
{
    long double p;
    long double n0 = i;  // 0 的数 
    long double n1 = N-i;// 1 的 
    
    p = -( (n0*n0/N)*log2l(n0/N)+(n1*n1/N)*log2l(n1/N) );
    
    //cout<<p<<endl;
    if(abs(p-eps)<0.0001) // 判断精确度 
        cout<<i<<endl;
}
 
int main()
{
    //cout<<cal(114514)<<endl;
    for(int i = 1;i<=N/2;i++)
        lmr(i);
 
    return 0;
}

C.冶炼金属

【问题描述】

小蓝有一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个 炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金 属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法 继续冶炼。 现在给出了 N 条冶炼记录，每条记录中包含两个整数 A 和 B，这表示本次 投入了 A 个普通金属 O，最终冶炼出了 B 个特殊金属 X。每条记录都是独立 的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。 根据这 N 条冶炼记录，请你推测出转换率 V 的最小值和最大值分别可能是 多少，题目保证评测数据不存在无解的情况。

最大换最小 ， 最小换最大 。

#include <bits/stdc++.h>
 
using namespace std;
 
const int INF = 1e9 + 10;
int n;
 
int main()
{
	cin >> n;
	int maxn = INF, minx = -INF;
	for(int i = 0;i < n;i++)
	{
		int a, b;
		cin >> a >> b;
		minx = max(minx, a / (b + 1));
		maxn = min(maxn, a / b);
	}
	cout << minx + 1 << ' ' << maxn;
	
	return 0;
}