2023第十四届蓝桥杯c++ b组省赛真题

1.冶炼金属

题目描述

小蓝���一个神奇的炉子用于将普通金属 O 冶炼成为一种特殊金属 X。这个炉子有一个称作转换率的属性 V，V 是一个正整数，这意味着消耗 V 个普通金

（）

属 O 恰好可以冶炼出一个特殊金属 X，当普通金属 O 的数目不足 V 时，无法继续冶炼。

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

（）

的，这意味着上一次没消耗完的普通金属 O 不会累加到下一次的冶炼当中。

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

输入格式

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

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

输出格式

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

样例输入

3

75 3

53 2

59 2

样例输出

20 25

提示

当 V = 20 时，有：⌊75/20⌋ = 3，⌊ 53/20 ⌋ = 2，⌊ 59/20 ⌋ = 2，可以看到符合所有冶炼记录。

当 V = 25 时，有：⌊75/25⌋ = 3，⌊ 53/25 ⌋ = 2，⌊ 59/25 ⌋ = 2，可以看到符合所有冶炼记录。

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

对于 30% 的评测用例，1 ≤ N ≤ 10^2。

对于 60% 的评测用例，1 ≤ N ≤ 10^3。

对于 100% 的评测用例，1 ≤ N ≤ 10^4，1 ≤ B ≤ A ≤ 10^9。

思维题

直接上代码

#includeusing namespace std;#define ll long longint n,a,b=1e9+10;int main(){cin>>n;while(n--){int x,y;cin>>x>>y;b=min(b,x/y);a=max(a,x/(y+1));}cout

h32.飞机降落(dfs+回溯+剪枝)/h3 h3题目描述/h3 pN 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早/p p可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li个单位时间。/p p一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。/p p请你判断 N 架飞机是否可以全部安全降落。/p h3输入格式/h3 p输入包含多组数据。/p p第一行包含一个整数 T，代表测试数据的组数。/p p对于每组数据，第一行包含一个整数 N。/p p以下 N 行，每行包含三个整数：Ti，Di 和 Li。/p h3输出格式/h3 p对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。/p h3样例输入/h3 blockquote p2/p p3/p p0 100 10/p p10 10 10/p p0 2 20/p p3/p p0 10 20/p p10 10 20/p p20 10 20/p /blockquote pre /pre h3样例输出/h3 blockquote pre YESNO/pre /blockquote h3提示/h3 p对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。/p p对于第二组数据，无论如何安排，都会有飞机不能及时降落。/p p对于 30% 的数据，N ≤ 2。/p p对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti , Di , Li ≤ 10^5。/p p解题思路/p p一看数据范围就是搜索，10的阶乘为3628800算上10组数据刚好可以过。/p pre #includebits/stdc++.husing namespace std;#define ll long longint n,T,res;struct stu{int x;int y;int z;};stu a[15];bool st[15];int t[15];bool check(){int k=a[t[1]].x+a[t[1]].z;for(int i=2;i=n;i++){if(a[t[i]].x+a[t[i]].yk) return 0;else {if(k=a[t[i]].x) k+=a[t[i]].z;else k+=(a[t[i]].x-k+a[t[i]].z);}}return 1;}void dfs(int u){if(un){if(check()) res++;return ;}if(res) return;for(int i=1;i=n;i++){if(!st[i]){t[u]=i;st[i]=1;dfs(u+1);st[i]=0;}}}int main(){cin>T;while(T--){cin>>n;res=0;memset(st,0,sizeof st);for(int i=1;i>a[i].x>>a[i].y>>a[i].z;dfs(1);if(res) coutb;n=str.size();for(int i=0;i=k) r=mid;else l=mid+1;}if(y[l]-x[i]+1>=k) res+=(n2-l);}coutk;cin>>str;cin>>a>>b;int n=str.size();for(int i=k-1;ik;l[n+1]=n;r[0]=1;priority_queue q; for(int i=1;i>v[i];l[i]=i-1;r[i]=i+1;q.push({v[i],i});}while(k--){auto t=q.top();q.pop();if(t.first!=v[t.second]) q.push({v[t.second],t.second}),k++;else del(t.second);}int head=r[0];while(head&&head