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，所以以后准备蓝桥杯一定要刷难度稍微大一点的题，因为趋势是就是难度逐年递增。

最后祝各位大佬都省一。