当前位置：首页 > news >正文

蓝桥杯小白打卡第七天（第十四届真题）

news 来源：原创 2025/8/23 15:55:54

小蓝的金属冶炼转换率问题

小蓝有一个神奇的炉子用于将普通金属 (O) 冶炼成为一种特殊金属 (X) 。

这个炉子有一个称作转换率的属性 (V) ，(V) 是一个正整数，这意味着消耗 (V) 个普通金属 (O) 恰好可以冶炼出一个特殊金属 (X) ，当普通金属 (O) 的数目不足 (V) 时，无法继续冶炼。

现在给出了 (N) 条冶炼记录，每条记录中包含两个整数 (A) 和 (B) ，这表示本次投入了 (A) 个普通金属 (O) ，最终冶炼出了 (B) 个特殊金属 (X) 。

每条记录都是独立的，这意味着上一次没消耗完的普通金属 (O) 不会累加到下一次的冶炼当中。

根据这 (N) 条冶炼记录，请你推测出转换率 (V) 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。

输入格式

第一行一个整数 (N) ，表示冶炼记录的数目。

接下来输入 (N) 行，每行两个整数 (A、B) ，含义如题目所述。

输出格式

输出两个整数，分别表示 (V) 可能的最小值和最大值，中间用空格分开。

数据范围

对于 30% 的评测用例，(1 \leq N \leq 10^2) 。
对于 60% 的评测用例，(1 \leq N \leq 10^3) 。
对于 100% 的评测用例，(1 \leq N \leq 10^4) ，(1 \leq B \leq A \leq 10^9) 。

输入样例

输出样例

20 25

样例解释

当 (V = 20) 时，有：(\lfloor\frac{75}{20}\rfloor = 3) ，(\lfloor\frac{53}{20}\rfloor = 2) ，(\lfloor\frac{59}{20}\rfloor = 2) ，可以看到符合所有冶炼记录。

当 (V = 25) 时，有：(\lfloor\frac{75}{25}\rfloor = 3) ，(\lfloor\frac{53}{25}\rfloor = 2) ，(\lfloor\frac{59}{25}\rfloor = 2) ，可以看到符合所有冶炼记录。

且再也找不到比 (20) 更小或者比 (25) 更大的符合条件的 (V) 值了。

代码

//消耗V个普通金属，可以冶炼一个特殊金属，当普通金属数目不到V时，无法继续
//输入N行熔炼记录，接下来N行，A代表使用普通金属数量，B代表练出了多少金属#include <iostream>
#include <cstdio>
using namespace std;
int ll=-1,rr=1e9;//下限和上限int main(){//求下限：我们假定可以练出b+1个，我们在计算出的数字的基础之上加1，就可以求出下限，随后我们针对所有计算出的下限取一个最大值//求上限：A/B，为我们可以练出的上限，对所有的上限取一个最小值int n;cin>>n;while(n--){int a,b;scanf("%d %d",&a,&b);ll=max(ll,a/(b+1)+1);rr=min(rr,a/b);}cout<<ll<<" "<<rr<<endl;return 0;
}

飞机降落问题

有 (N) 架飞机准备降落到某个只有一条跑道的机场。

其中第 (i) 架飞机在 (T_i) 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 (D_i) 个单位时间，即它最早可以于 (T_i) 时刻开始降落，最晚可以于 (T_i + D_i) 时刻开始降落。

降落过程需要 (L_i) 个单位时间。

一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。

请你判断 (N) 架飞机是否可以全部安全降落。

输入格式

输入包含多组数据。

第一行包含一个整数 (T) ，代表测试数据的组数。

对于每组数据，第一行包含一个整数 (N) 。

以下 (N) 行，每行包含三个整数：(T_i) ，(D_i) 和 (L_i) 。

输出格式

对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。

数据范围

对于 30% 的数据，(N \leq 2) 。
对于 100% 的数据，(1 \leq T \leq 10) ，(1 \leq N \leq 10) ，(0 \leq T_i,D_i,L_i \leq 10^5) 。

输入样例

输出样例

YES
NO

样例解释

对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。

对于第二组数据，无论如何安排，都会有飞机不能及时降落。

代码

//n架飞机
//第i个飞机t到达机场，还可以盘旋d个时间，降落需要l时间  ，最早可以t开始降落，最晚t+d
//一个飞机降落完，另一个飞机才可以降落
//第一行是t，代表t组数据
//n架飞机 ，t时刻到达，d时刻的盘旋，l降落时间
//因为必须等到前一个飞机降落完毕，后一个飞机才可以降落，所以我们设置一个变量为last保存下前一个飞机降落完成的时间
//if last位于t之前或者是t+d之间那么便可以完成降落
//更新last为 last+l，t+l中的最大值
//if 不满足last的条件直接返回false
//我们在这里创建一个结构体来保证数据的易读性，原有思想是对飞机进行一次排序，但是完全没有必要，因为这不具有参考的价值//这里为什么使用dfs是因为这里飞机最多有10架，dfs可以完成任务，不超时
//DFS的分类：指数型枚举（每一个方案有多个选择，就比如一个物品拿还是不拿），组合型枚举（不一定要所有的都枚举出来）
//，排列型枚举（从小到大的排序）如果我们这里一定要进行归类的话，那么这里应该是可以是排列行枚举#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef struct plane{int t,d,l;
}plane;//创建一个plane类型的数组，用来保存飞机的具体参数
plane p[12];
int n;//飞机的数量我们在这里设置为全局变量
bool st[12];//同时创建一个bool数组来确定飞机是否有完成降落bool dfs(int u,int last){if(u>n) return true;//递归首先要确定递归的出口，当u大于飞机的数量时，证明此时飞机已经完全被便利过了，没有任何问题for(int i=1;i<=n;i++){int t=p[i].t,d=p[i].d,l=p[i].l;if(!st[i]&&t+d>=last){st[i]=1;if(dfs(u+1,max(last,t)+l)) return true;st[i]=0;}}return false;
}int main(){int T;scanf("%d",&T);//输入数据组数的数量while(T--){memset(st,0,sizeof st);scanf("%d",&n);//输入飞机的数量for(int i=1;i<=n;i++){int a,b,c;scanf("%d %d %d",&a,&b,&c);p[i]={a,b,c};}if(dfs(1,0)) cout<<"YES"<<endl;//分别代表第一架飞机和上一家飞机的完成降落时间为0else cout<<"NO"<<endl;}return 0;
}

接龙数列问题

对于一个长度为 (K) 的整数数列：(A_1,A_2,\ldots,A_K) ，我们称之为接龙数列当且仅当 (A_i) 的首位数字恰好等于 (A_{i - 1}) 的末位数字 ((2\leq i\leq K))。

例如 (12,23,35,56,61,11) 是接龙数列；(12,23,34,56) 不是接龙数列，因为 (56) 的首位数字不等于 (34) 的末位数字。

所有长度为 (1) 的整数数列都是接龙数列。

现在给定一个长度为 (N) 的数列 (A_1,A_2,\ldots,A_N) ，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 (N) 。

第二行包含 (N) 个整数 (A_1,A_2,\ldots,A_N) 。

输出格式

一个整数代表答案。

数据范围

对于 20% 的数据，(1 \leq N \leq 20) 。
对于 50% 的数据，(1 \leq N \leq 10000) 。
对于 100% 的数据，(1 \leq N \leq 10^5) ，(1 \leq A_i \leq 10^9) 。所有 (A_i) 保证不包含前导 (0) 。

输入样例

5
11 121 22 12 2023

输出样例

样例解释

删除 (22) ，剩余 (11,121,12,2023) 是接龙数列。

代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N=1e5+5;
//长度为k的整数数列，当ai的首位恰好等于ai-1的末尾时可以被叫做接龙数列
//长度为1的整数数列都是接龙序列
//给定一个长度为n的整数数列，计算最少从中删除多少个数，可以使剩下的序列使接龙序列
//也就是要求原整数数列的最大接龙子序列
//和最长上升子序列很相似
//在这里我们没有必要存上去整个数字，我们仅仅需要存上数字的首和尾，所以我们这里仅仅需要创建两个
//数组来进行存储
int dp[10],l[N],r[N];//dp[i]存储的是以i为了结尾的最长接龙序列的长度
//为了方便存储我们这里采用string字符串,到时候直接读取首s[0]和尾部s[s.size()-1]就行
string str;
//我们要求最长的接龙序列的数量，每一步和上一部有关系，所以我们这里采用dp动态规划的方法
//由于我们这里的数据范围是1e5，所以双重循环情况下一定会超时
//优化方法：我们没有必要对每一个i去便利所有的j去判断是不是相等，我们只需要用dp[r[i]]=max(dp[r[i]],dp[l[i]]+1)int main(){int n;scanf("%d",&n);for(int i=0;i<n;i++){cin>>str;l[i]=str[0]-'0';r[i]=str[str.size()-1]-'0';}//完成数组的赋值int res=-1;for(int i=0;i<n;i++){//i代表的是右边的部分// dp[i]=1;//他自己就是一个接龙序列// for(int j=0;j<i;j++){//j代表的是左边的部分//     if(r[j]==l[i]) dp[i]=max(dp[i],dp[j]+1);// }// res=max(res,dp[i]);dp[r[i]]=max(dp[r[i]],dp[l[i]]+1);res=max(dp[r[i]],res);}res=n-res;cout<<res;return 0;
}

字符串的新简写方法计数问题

程序猿圈子里正在流行一种很新的简写方法：

对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。

例如 internationalization 简写成 i18n，Kubernetes 简写成 K8s，Lanqiao 简写成 L5o 等。

在本题中，我们规定长度大于等于 (K) 的字符串都可以采用这种简写方法（长度小于 (K) 的字符串不配使用这种简写）。

给定一个字符串 (S) 和两个字符 (c_1) 和 (c_2) ，请你计算 (S) 有多少个以 (c_1) 开头 (c_2) 结尾的子串可以采用这种简写？

输入格式

第一行包含一个整数 (K) 。

第二行包含一个字符串 (S) 和两个字符 (c_1) 和 (c_2) 。

输出格式

一个整数代表答案。

数据范围

对于 20% 的数据，(2 \leq K \leq |S| \leq 10000) 。
对于 100% 的数据，(2 \leq K \leq |S| \leq 5 \times 10^5) 。(S) 只包含小写字母。(c_1) 和 (c_2) 都是小写字母。
(|S|) 代表字符串 (S) 的长度。

输入样例

4
abababdb a b

输出样例

样例解释

符合条件的子串如下所示，中括号内是该子串

[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]

代码

//两个判断条件：串的长度大于k；串以a开头，以b结尾
//暴力：双重循环，1e11必超时//我们这里采用一种类似的方法和之前的统计日期很相似，就是记录2 0 2 3遇到的分别数字的数量，遇到第一次2，进行++，如果遇到0，就加上第一次
//遇到2的数目....//我们这里采用后缀和的方式，我们从最后面开始进行遍历//相对于更加耗时的双重循环，我们可以使用动态数组来进行维护#include <iostream>
#include <cstdio>using namespace std;int k;//代表长度
string str;//代表字符串
char a,b;//代表字符
long long cnt,res;int main(){cin>>k>>str>>a>>b;int len=str.size();for(int i=len-k,j=len-1;i>=0;i--,j--){if(str[j]==b) cnt++;if(str[i]==a) res+=cnt;}cout<<res;return 0;
}

小蓝的金属冶炼转换率问题

输入格式

输出格式

数据范围

输入样例

输出样例

样例解释

代码

飞机降落问题

输入格式

输出格式

数据范围

输入样例

输出样例

样例解释

代码

接龙数列问题

输入格式

输出格式

数据范围

输入样例

输出样例

样例解释

代码

字符串的新简写方法计数问题

输入格式

输出格式

数据范围

输入样例

输出样例

样例解释

代码

相关文章：