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^
对于 60% 的评测用例，1 ≤ N ≤ 10^
对于 100% 的评测用例，1 ≤ N ≤ 10^4，1 ≤ B ≤ A ≤ 10^
思维题
直接上代码
#include
using namespace std;
#define ll long long
int 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));
}
couth32.飞机降落(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 class="brush:python;toolbar:false"/pre
h3样例输出/h3
blockquote
pre class="brush:python;toolbar:false"YES
NO
/pre
/blockquote
h3提示/h3
p对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。/p
p对于第二组数据，无论如何安排，都会有飞机不能及时降落。/p
p对于 30% 的数据，N ≤ /p
p对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti , Di , Li ≤ 10^/p
p解题思路/p
p一看数据范围就是搜索，10的阶乘为3628800算上10组数据刚好可以过。/p
pre class="brush:python;toolbar:false"#includebits/stdc++.h
using namespace std;
#define ll long long
int 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&&headThe End