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。
思维题
直接上代码
#include<bits/stdc++.h>
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));
}
cout<<a+1<<" "<<b;
return 0;
}
2.飞机降落(dfs+回溯+剪枝)
题目描述
N 架飞机准备降落到某个只有一条跑道的机场。其中第 i 架飞机在 Ti 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 Di 个单位时间，即它最早
可以于 Ti 时刻开始降落，最晚可以于 Ti + Di 时刻开始降落。降落过程需要 Li个单位时间。
一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落，但是不能在前一架飞机完成降落前开始降落。
请你判断 N 架飞机是否可以全部安全降落。
输入格式
输入包含多组数据。
第一行包含一个整数 T，代表测试数据的组数。
对于每组数据，第一行包含一个整数 N。
以下 N 行，每行包含三个整数：Ti，Di 和 Li。
输出格式
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。
样例输入
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
样例输出
YES
NO
提示
对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。
对于第二组数据，无论如何安排，都会有飞机不能及时降落。
对于 30% 的数据，N ≤ 2。
对于 100% 的数据，1 ≤ T ≤ 10，1 ≤ N ≤ 10，0 ≤ Ti , Di , Li ≤ 10^5。
解题思路
一看数据范围就是搜索，10的阶乘为3628800算上10组数据刚好可以过。
#include<bits/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]].y<k) 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(u>n){
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<=n;i++) cin>>a[i].x>>a[i].y>>a[i].z;
dfs(1);
if(res) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
3.接龙数列（线性dp）
题目描述
对于一个长度为 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，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？
输入格式
第一行包含一个整数 N。
第二行包含 N 个整数 A1, A2, . . . , AN。
输出格式
一个整数代表答案。
样例输入
5
11 121 22 12 2023
样例输出
1
提示
删除 22，剩余 11, 121, 12, 2023 是接龙数列。
对于 20% 的数据，1 ≤ N ≤ 20。
对于 50% 的数据，1 ≤ N ≤ 10000。
对于 100% 的数据，1 ≤ N ≤ 10^5，1 ≤ Ai ≤ 10^9。所有 Ai 保证不包含前导 0。
解题思路
最长上升子序列模型，f[r]表示以r结尾的最长接龙子序列的长度，则f[r]=max(f[r],f[l]+1)
答案是n减去最长接龙子序列的长度
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,t,res;
const int N=1e5+10;
int f[N],a[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){
int t=a[i],l;
int r=t%10;
while(t){
l=t;
t/=10;
}
f[r]=max(f[r],f[l]+1);
res=max(res,f[r]);
}
cout<<n-res;
return 0;
}
4.子串简写(思维+二分)
题目描述
程序猿圈子里正在流行一种很新的简写方法：对于一个字符串，只保留首尾字符，将首尾字符之间的所有字符用这部分的长度代替。例如 internation-alization 简写成 i18n，Kubernetes （注意连字符不是字符串的一部分）简写成 K8s, Lanqiao 简写成 L5o 等。
在本题中，我们规定长度大于等于 K 的字符串都可以采用这种简写方法（长度小于 K 的字符串不配使用这种简写）。
给定一个字符串 S 和两个字符 c1 和 c2，请你计算 S 有多少个以 c1 开头c2 结尾的子串可以采用这种简写？
输入格式
第一行包含一个整数 K。
第二行包含一个字符串 S 和两个字符 c1 和 c2。
输出格式
一个整数代表答案。
样例输入
4
abababdb a b
样例输出
6
提示
符合条件的子串如下所示，中括号内是该子串：
[abab]abdb
[ababab]db
[abababdb]
ab[abab]db
ab[ababdb]
abab[abdb]
对于 20% 的数据，2 ≤ K ≤ |S | ≤ 10000。
对于 100% 的数据，2 ≤ K ≤ |S | ≤ 5 × 10^5。S 只包含小写字母。c1 和 c2 都是小写字母。
|S | 代表字符串 S 的长度。
解题思路
先把所有c1,c2的下表分别存起来，然后主要根据两个数组的单调性来优化算法（二分，思维）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll n,k,res;
string str;
char a,b;
vector<int> x;
vector<int> y;
int main(){
cin>>k;
cin>>str>>a>>b;
n=str.size();
for(int i=0;i<n;i++){
if(str[i]==a) x.push_back(i);
if(str[i]==b) y.push_back(i);
}
int n1=x.size(),n2=y.size();
for(int i=0;i<n1;i++){
int l=0,r=n2-1;
while(l<r){
int mid=l+r>>1;
if(y[mid]-x[i]+1>=k) r=mid;
else l=mid+1;
}
if(y[l]-x[i]+1>=k) res+=(n2-l);
}
cout<<res;
return 0;
}
#include<bits/stdc++.h>
#define ll long long
using namespace std;
string str;
int k;
ll res;
const int N=5e5+10;
int f[N];
char a,b;
int main(){
cin>>k;
cin>>str;
cin>>a>>b;
int n=str.size();
for(int i=k-1;i<n;i++){
if(str[i-k+1]==a) f[i]=f[i-1]+1;
else f[i]=f[i-1];
}
for(int i=k-1;i<n;i++){
if(str[i]==b) res+=f[i];
}
cout<<res;
return 0;
}
5.整数删除(优先队列+双向链表)
题目描述
给定一个长度为 N 的整数数列：A1, A2, . . . , AN。你要重复以下操作 K 次：
每次选择数列中最小的整数（如果最小值不止一个，选择最靠前的），将其删除。并把与它相邻的整数加上被删除的数值。
输出 K 次操作后的序列。
输入格式
第一行包含两个整数 N 和 K。
第二行包含 N 个整数，A1, A2, A3, . . . , AN。
输出格式
输出 N − K 个整数，中间用一个空格隔开，代表 K 次操作后的序列。
样例输入
5 3
1 4 2 8 7
样例输出
17 7
提示
数列变化如下，中括号里的数是当次操作中被选择的数：
[1] 4 2 8 7
5 [2] 8 7
[7] 10 7
17 7
对于 20% 的数据，1 ≤ K < N ≤ 10000。
对于 100% 的数据，1 ≤ K < N ≤ 5 × 10^5，0 ≤ Ai ≤ 10^8。
解题思路
首先看时间复杂度删除操作必须是O（1）很容易想到双向链表，然后每次取最小元素可以用小根堆来实现。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5e5+10;
ll l[N],r[N],v[N];
int n,k;
typedef pair<ll,int> PII;
void del(int x){
r[l[x]]=r[x];l[r[x]]=l[x];
v[l[x]]+=v[x];v[r[x]]+=v[x];
}
int main(){
cin>>n>>k;
l[n+1]=n;r[0]=1;
priority_queue<PII,vector<PII>,greater<PII>> q;
for(int i=1;i<=n;i++){
cin>>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<=n){
cout<<v[head]<<" ";
head=r[head];
}
return 0;
}
目前就会这几道，其他的学会再补更，总而言之这次蓝桥杯b组比去年都难度要大一些，写暴力拿不了太多分，题的质量很高，考察的也很精细，而且易错点也不少，在考试的紧张环境下很难把会做的都ac，所以以后准备蓝桥杯一定要刷难度稍微大一点的题，因为趋势是就是难度逐年递增。
最后祝各位大佬都省一。
