这周有亿点点忙（……）

C. 冶炼金属

二分，公式

被分配到讲解这道题了，写ppt的时候发现自己原来的写法是错误的（痛啊——）含泪测试数据，希望蓝桥杯的数据别太严

简单摘录下我讲解的分析好了，虽然我讲得依托答辩但是感觉当时想的还是蛮详细的（……）

+ 找出几个区间的交集
+ 对于相同的普通金属数量，在一段连续的整数（转换率）中，一定分成连续的几段，每一段内的数所对应的转换出的特殊金属数量相同
+ 总的左端点为每个左端点的最大值，总的右端点为每个右端点的最小值。
+ 区间是连续的，上一个区间的终点是下一个区间的起点

二分

二分找出每对数的左右端点，进而求出所有的左右端点。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=1e4+10;
int n,num[N][3];
 
int find_l(int x,int y){
	int l=0,r=1e9+1;
	while(l+1<r){
		int mid=l+r>>1;
		if(x/mid>y) l=mid;
		else r=mid;
	}
	return r;
}

int find_r(int x,int y){
	int l=0,r=1e9+1;
	while(l+1<r){
		int mid=l+r>>1;
		if(x/mid>=y) l=mid;
		else r=mid;
	}
	return l;
}

int main(){
	cin>>n;
	int l=0,r=0x3f3f3f3f;
	while(n--){
		int x,y;
		cin>>x>>y;
		//左端点找最大值 
		l=max(l,find_l(x,y));
		//右端点找最小值 
		r=min(r,find_r(x,y));
	}
	cout<<l<<" "<<r;
	return 0;
}

公式

当前区间左端点是上个区间右端点+1，区间右端点为普通金属数量/区间对应产出特殊金属的数量。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
const int N=1e4+10;
int n,num[N][3];

int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>num[i][1]>>num[i][2];
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		//求左端点找最大值 
		ans=max(ans,num[i][1]/(num[i][2]+1)+1);
	}
	cout<<ans<<" ";
	ans=0x3f3f3f3f3f;
	for(int i=1;i<=n;i++){
		//求右端点找最小值 
		ans=min(ans,num[i][1]/num[i][2]);
	} 
	cout<<ans;
	return 0;
}

D. 飞机降落

DFS/next_premutation

观察一下题目的数据范围，发现其实挺小的N和T都在10以内，故考虑直接暴力。

赛场上非常有信心地写了排序然后贪心，追悔莫及啊啊啊啊啊啊啊

暴力有两种方法，比较熟悉的是DFS，也可以用next_permutation来一个个判断。

其实没啥难的直接看代码吧

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
#define endl "\n"
const int N=20;
int n;
bool vis[N];

struct type{//存储飞机信息
	int val,t,d;
}pl[N];

int read() {
	int i=0,j=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') j=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		i=i*10+ch-'0';
		ch=getchar();
	}
	return i*j;
}

bool dfs(int cnt,int ti){
	if(cnt==n) return true;
	for(int i=1;i<=n;i++){
		if(!vis[i]&&ti<=pl[i].t+pl[i].d){//寻找可行的下一架飞机
			vis[i]=true;
			bool flag=dfs(cnt+1,max(ti,pl[i].t)+pl[i].val);
			vis[i]=false;
			if(flag) return true;
		}
	}
	return false;
}

int main(){
	int _=read();
	while(_--){
		n=read();
		for(int i=1;i<=n;i++){
			pl[i].t=read();
			pl[i].d=read();
			pl[i].val=read();
		} 
		if(dfs(0,0)) printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
#define endl "\n"
const int N=20;
int n,a[N];
bool vis[N];

struct type{//存储飞机信息
	int val,t,d;
}pl[N];

int read() {
	int i=0,j=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') j=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		i=i*10+ch-'0';
		ch=getchar();
	}
	return i*j;
}

bool check(){
	int t=0;
	for(int i=1;i<=n;i++){
		if(t>pl[a[i]].t+pl[a[i]].d) return false;
		t=max(t,pl[a[i]].t)+pl[a[i]].val;
	}
	return true;
} 

int main(){
	int _=read();
	while(_--){
		n=read();
		for(int i=1;i<=n;i++){
			pl[i].t=read();
			pl[i].d=read();
			pl[i].val=read();
			a[i]=i;
		} 
		bool flag=false;
		do{
			if(check()){
				flag=true;
				break;
			}
		}while(next_permutation(a+1,a+1+n));
        //好像在一些场合下还挺好用的，记一记
		if(flag) cout<<"YES\n";
		else cout<<"NO\n";
	}
	return 0;
}

关于这题，学长给出的最终解法是状压dp，但我太菜了，等我以后研究（）

E. 接龙数列

dp，最长上升子序列

可以发现，每次加入一个新的数字，它的长度取决于上一个以当前开头数字结尾的最长子序列、而它会影响的也只有当前结尾数字所在的子序列长度。

所以，我们可以记录从0-9结尾的子序列长度的最大值，对于新加入的数字a___b（中间一段为任意数字，我们在乎的只有开头和结尾），在它之前包含它的最长子序列长度等于len[a]+1，len[b]=max(len[b]，len[a]+1)，如此将数字一个个加入，最后找到最长的len输出即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
#define endl "\n"
const int N=20;
int n,len[11]; 

int read() {
	int i=0,j=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') j=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		i=i*10+ch-'0';
		ch=getchar();
	}
	return i*j;
}

int main(){
	n=read();
	for(int i=1;i<=n;i++){
		int x=read();
		int y=x%10;
		while(x>=10) x/=10;
		len[y]=max(len[y],len[x]+1);
	}
	int ans=0;
	for(int i=1;i<=n;i++) ans=max(ans,len[i]);
	cout<<n-ans;
	return 0;
}

F. 岛屿个数

如果直接看岛屿是否成环，虽然可以很轻易地通过深搜确定一个岛屿是否成环，但却很难确定一个成环的岛屿内有多少个被包含在内的子岛屿。（岛屿是不规则的）

让我们换个角度想，既然看岛屿不可以，那能不能看海水呢？

为了后续方便，我们先把前面读进来的岛屿分布外面加上一圈海水，如下图

有了这圈海水，我们会发现，假如我们从最外层开始dfs，将八方向（陆地是四方向相连那么海水就是八方向相连，两者是互补的）可到达的海水全部设定成2，那么能成环的岛屿外部会被2包围的同时，内部一定没有2，不能成环的岛屿则会整个被2包围（我们假定单个岛屿也算环），像是下图这样。

那么最巧妙的地方就来了，当我们给最外圈的海水染完颜色后，我们从头开始遍历，找到一个不等于2的格子后就用dfs把和这个格子四方向相连且不等于2（注意是不等于2而不是等于1，为了保证被包围的范围内的岛屿能被遍历要把包围内的海水也染色），将它全部染成2，答案+1，继续遍历重复上述步骤知道最后一格。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int,int> pii;
#define endl "\n"
const int N=60;
int n,m,mp[N][N],dx[]={0,0,0,1,-1,1,1,-1,-1},dy[]={0,1,-1,0,0,1,-1,1,-1};

int read() {
	int i=0,j=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') j=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		i=i*10+ch-'0';
		ch=getchar();
	}
	return i*j;
}

void dfs1(int x,int y){
	mp[x][y]=2;
	for(int i=1;i<=8;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>=0&&xx<=n&&yy>=0&&yy<=m&&!mp[xx][yy]){
			dfs1(xx,yy);
		} 
	}
}

void dfs(int x,int y){
	mp[x][y]=2;
	for(int i=1;i<=4;i++){
		int xx=x+dx[i],yy=y+dy[i];
		if(xx>=0&&xx<=n&&yy>=0&&yy<=m&&mp[xx][yy]!=2){
			dfs(xx,yy);
		}
	}
}

int main(){
	int _=read();
	while(_--){
		memset(mp,0,sizeof(mp));
		n=read(),m=read();
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%1d",&mp[i][j]);
			}
		}
		n++,m++;
		dfs1(0,0);
		int ans=0;
		for(int i=1;i<n;i++){
			for(int j=1;j<m;j++){
				if(mp[i][j]!=2){
					//cout<<i<<' '<<j<<endl;
					ans++;
					dfs(i,j);
				} 
			} 
		}
		printf("%d\n",ans); 
	}
	return 0;
}

H. 整数删除

对STL很巧妙地运用

每次选择数列中最小的数，我们很轻易地可以想到小根堆（priority_queue），用pair来，first存值，second存序号。但是问题就出在我们会对数列中的值进行删除和修改。

修改其实也可以想到，就是每次修改完将新修改的值和编号加入小根堆，后续每次拿出前先检查当前序号的值与拿出的值是否相等，相等才继续修改。但问题又出现了，当涉及数组的删减时我们第一个想到的肯定是vector，但自己模拟下就会发现，用vector每次删去数之后每个数的序号都会发生改变，我们很难通过上面的方法来检验当前拿出的值是否合理。

那么我们当前的问题就是，怎么样让每个数对应的序号不变，以方便我们对它的值进行检验？从我们学到的STL基础可知，vector的能实现对于数组中数据的快速删减，其底层原理其实是链表。那么我们能不能自己动手实现这个链表以达到不改变数据位置的目的呢？答案是可以的。

具体看代码。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<ll,ll> pii;
#define endl "\n"
const int N=5e5+10;
priority_queue<pii,vector<pii>,greater<pii>> q;
//优先队列，小根堆的固定形式
ll front[N],back[N],n,m,vis[N],num[N];
//模拟双向链表，记录前一个元素的位置和后一个元素的位置，删除的时候只需要改变
//对应的前后元素的前后记录即可，其自身编号不会改变。
//需要vis数组来检验当前元素是否已被取出，防止被重复取出

ll read() {
	ll i=0,j=1;
	char ch=getchar();
	while(!isdigit(ch)) {
		if(ch=='-') j=-1;
		ch=getchar();
	}
	while(isdigit(ch)) {
		i=i*10+ch-'0';
		ch=getchar();
	}
	return i*j;
}

int main(){
	n=read(),m=read();
	for(int i=1;i<=n;i++){
        //记录值，初始化堆，记录前后元素位置
		num[i]=read();
		q.push({num[i],i});
		front[i]=i-1;
		back[i]=i+1; 
	} 
	while(!q.empty()&&m){
		ll val,id;
		tie(val,id)=q.top();
		q.pop();
		if(vis[id]||num[id]!=val) continue;
		vis[id]=1;
        //当前位置的前后通过front和back查找（删除某个元素后不一定连续）
		num[front[id]]+=val;
		num[back[id]]+=val;
        //删除操作 与链表类似
		back[front[id]]=back[id];
		front[back[id]]=front[id];
		if(front[id]>0) q.push({num[front[id]],front[id]});
		if(back[id]<=n) q.push({num[back[id]],back[id]});
		m--;
	} 
	int k=1;
    //要先找到队头元素，能成功输出
    //队头元素就是第一个没有被vis的元素
	while(vis[k]) k++;
	while(k<=n){
		cout<<num[k]<<" ";
		k=back[k];
	}
	return 0;
}