2023年第十四届蓝桥杯大赛软件类省赛C/C++大学B组真题
一、冶炼金属
题目：
问题描述
小蓝有一个神奇的炉子用于将普通金属 OO 冶炼成为一种特殊金属 XX。这个炉子有一个称作转换率的属性 VV，VV 是一个正整数，这意味着消耗 VV 个普通金属 OO 恰好可以冶炼出一个特殊金属 XX，当普通金属 OO 的数目不足 VV 时，无法继续冶炼。
现在给出了 NN 条冶炼记录，每条记录中包含两个整数 AA 和 BB，这表示本次投入了 AA 个普通金属 OO，最终冶炼出了 BB 个特殊金属 XX。每条记录都是独立的，这意味着上一次没消耗完的普通金属 OO 不会累加到下一次的冶炼当中。
根据这 NN 条冶炼记录，请你推测出转换率 VV 的最小值和最大值分别可能是多少，题目保证评测数据不存在无解的情况。
输入格式
第一行一个整数 NN，表示冶炼记录的数目。
接下来输入 NN 行，每行两个整数 AA、BB，含义如题目所述。
输出格式
输出两个整数，分别表示 VV 可能的最小值和最大值，中间用空格分开。
样例输入
3
75 3
53 2
59 2
样例输出
20 25
样例说明
当 V=20V=20 时，有：⌊7520⌋=3⌊2075⌋=3，⌊5320⌋=2⌊2053⌋=2，⌊5920⌋=2⌊2059⌋=2，可以看到符合所有冶炼记录。
当 V=25V=25 时，有：⌊7525⌋=3⌊2575⌋=3，⌊5325⌋=2⌊2553⌋=2，⌊5925⌋=2⌊2559⌋=2，可以看到符合所有冶炼记录。
且再也找不到比 2020 更小或者比 2525 更大的符合条件的 VV 值了。
评测用例规模与约定
对于 3030% 的评测用例，1≤N≤1021≤N≤102。
对于 6060% 的评测用例，1≤N≤1031≤N≤103。
对于 100100% 的评测用例，1≤N≤1041≤N≤104，1≤B≤A≤1091≤B≤A≤109。
题解：
#include
#include
#include
int main(int argc, char *argv[])
{
int a,b,n,c,d;
int max=INT_MAX;
int min=-1;
scanf("%d",&n);
for(int i=0;i scanf("%d %d",&a,&b); c=a/b; if(c max=c; } d=a/(b+1)+1; if(d>min){ min=d; } } printf("%d %d",min,max); return 0; } 二、飞机降落 题目： 问题描述 NN 架飞机准备降落到某个只有一条跑道的机场。其中第 ii 架飞机在 TiTi 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 DiDi 个单位时间，即它最早可以于 TiTi 时刻开始降落，最晚可以于 Ti+DiTi+Di 时刻开始降落。降落过程需要 LiLi 个单位时间。 一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。 请你判断 NN 架飞机是否可以全部安全降落。 输入格式 输入包含多组数据。 第一行包含一个整数 TT，代表测试数据的组数。 对于每组数据，第一行包含一个整数 NN。 以下 NN 行，每行包含三个整数：TiTi，DiDi 和 LiLi。 输出格式 对于每组数据，输出 YESYES 或者 NONO，代表是否可以全部安全降落。 样例输入 2 3 0 100 10 10 10 10 0 2 20 3 0 10 20 10 10 20 20 10 20 样例输出 YES NO 样例说明 对于第一组数据，可以安排第 33 架飞机于 00 时刻开始降落，2020 时刻完成降落。安排第 22 架飞机于 2020 时刻开始降落，3030 时刻完成降落。安排第 11 架飞机于 3030 时刻开始降落，4040 时刻完成降落。 对于第二组数据，无论如何安排，都会有飞机不能及时降落。 评测用例规模与约定 对于 3030% 的数据，N≤2N≤2。 对于 100100% 的数据，1≤T≤101≤T≤10，1≤N≤101≤N≤10，0≤Ti,Di,Li≤1050≤Ti,Di,Li≤105。 #include using namespace std; const int N=15; int t,n; //t:测试数据次数 //n:n架飞机 bool flag,visit[N]; //第n架飞机是否在dfs中被访问 //flag: 用于判断全部飞机是否能降落 struct p { int time,delay,land; }; //p:结构体p表示飞机的信息 void dfs(int cnt,int last,vector v) { if(!cnt) { flag=true; return; } //如果访问个数已经=飞机架数,说明所有飞机可以降落，跳出循环 for(int i=1;i<=n;i++) { if(!visit[i] && v[i].time+v[i].delay >= last) //若这架飞机还没被访问,且这架飞机的最长等待时间>上一架飞机完成降落的时间 //则继续dfs { visit[i]=true; dfs(cnt-1,max(last,v[i].time)+v[i].land,v); //下一次dfs的last=max(上架飞机完成降落的时间,这架飞机到达的时间)+这架飞机完成降落的时间 visit[i]=false; //回溯 } } //若无法完成降落,flag还是false } int main() { cin >> t; while(t--) { memset(visit,false,sizeof(visit)); ///每次询问需要重置visit数组 cin >> n; vector v(N); //v数组即p数组 for(int i=1;i<=n;i++) { cin >> v[i].time >> v[i].delay >> v[i].land; } flag=false; //每次访问重置flag dfs(n,0,v); if(flag) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0; } 下面是逐行详细解释代码的含义： 下面是逐行详细解释代码的含义： #include using namespace std;：这行代码允许你使用标准库的函数和对象，而无需指定std::前缀。 const int N=15;：这行代码定义了一个常量变量N，其值为15。它表示最大飞机数量。 int t,n;：这行代码声明了两个整数变量t和n。t表示测试用例的数量，n表示飞机的数量。 bool flag,visit[N];：这行代码声明了两个布尔变量flag和visit，其中visit是一个大小 为N的数组。flag用于确定是否所有飞机都可以降落，visit用于跟踪飞机在DFS遍历中是否被访问过。 struct p { int time, delay, land; };：这行代码定义了一个结构体p，表示飞机的信息。 它有三个整数成员：time（飞机到达时间）、delay（飞机允许的最大延误时间）和land （飞机降落所需时间）。 void dfs(int cnt, int last, vector v)：这行代码定义了一个递归函数dfs， 执行深度优先搜索。它接受三个参数：cnt（尚未访问的飞机数量）、last（上一架飞机降落的时间） 和v（飞机信息的向量）。 if (!cnt) { flag = true; return; }：这行代码检查是否所有飞机都已经访问过（cnt为零）。 如果是，则将flag设置为true，并从函数中返回，表示所有飞机都可以降落。 for (int i = 1; i <= n; i++)：这行代码开始一个循环，遍历所有的飞机。 if (!visit[i] && v[i].time + v[i].delay >= last)：这行代码检查当前飞机i 是否尚未访问过（!visit[i]），并且其到达时间和最大延误时间之和是否大于等于 上一架飞机降落的时间。如果两个条件都满足，则飞机可以降落。 visit[i] = true;：这行代码将当前飞机标记为已访问。 dfs(cnt - 1, max(last, v[i].time) + v[i].land, v);：这行代码使用更新后的参数 对dfs进行递归调用。它将未访问飞机数量减少一（cnt - 1），将上一架飞机降落时间更新 为当前最大时间和当前飞机到达时间的较大值（max(last, v[i].time)），并加上当前飞机 的降落时间（v[i].land）。 visit[i] = false;：这行代码将当前飞机标记为未访问（回溯）。 int main()：这行代码开始主函数。 cin >> t;：这行代码从输入中读取测试用例的数量。 while (t--)：这行代码开始一个循环，循环t次。 memset(visit, false, sizeof(visit));：这行代码将visit数组重置为全部为 false的值。它确保在每个测试用例之前，没有飞机被标记为已访问。 cin >> n;：这行代码从输入中读取当前测试用例的飞机数量。 vector v(N);：这行代码创建了一个大小为N的向量v，用于存储飞机的信息。 for (int i = 1; i <= n; i++)：这行代码开始一个循环，读取每架飞机的信息。 cin >> v[i].time >> v[i].delay >> v[i].land;：这行代码从输入中读取当前 飞机的到达时间、最大延误时间和降落时间，并将它们存储在向量v中。 flag = false;：这行代码在每个测试用例之前将flag变量重置为false。 dfs(n, 0, v);：这行代码调用dfs函数执行深度优先搜索，初始参数为剩余n架飞机、 上一架飞机降落时间为0，以及包含飞机信息的向量v。 60-64. 这几行代码检查flag的值，并输出"YES"表示所有飞机都可以降落，或输出"NO"表示不能。 return 0;：这行代码结束主函数，并返回0以表示程序执行成功。 精彩链接
您阅读本篇文章共花了：
发表评论