7.8 #E 小W挖宝藏-深搜

总结

0 分，赛时用了广搜的思路，时间复杂度太高，所以做搜索题时，经过尽量多的格子的题用 深搜 ，经过尽量少的格子的题用 广搜 。

题解

循环枚举每个格子，深搜计算从该格子出发所能得到的最多宝藏数量，与之前的最多比较，统计整个矩阵中从那个格子出发能得到最多宝藏。

搜索过程中，按下、右、上、左的顺序递归，直到无法再继续走为止，统计拿到的宝藏数量，回溯到上一层，继续计算其他可能。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
int n,m,mp[N][N];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; //方向计算数组

int dfs(int x,int y){
	int maxx=0;
	for(int i=0;i<4;i++){
		int nx=x+d[i][0],ny=y+d[i][1];
		if(nx<1 or nx>n or ny<1 or ny>m) continue; //是否越界
		if(mp[nx][ny]>=mp[x][y]) continue; //是否能走
		maxx=max(maxx,dfs(nx,ny)); //走到下一层
	}
	return maxx+1; 
}
signed main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}
	int res=-1,x,y;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int df=dfs(i,j);
			if(df>res){
				res=df;
				x=i,y=j;
			}
		}
	}
	cout<<x<<" "<<y<<'\n'<<res;
	return 0;
}

这样直接提交肯定会 TLE 的，搜索过程中每次移动都需要很多次递归调用计算，而有些计算是重复了很多次的，导致无用的计算太多，时间复杂度太高。

在此基础上，我们可以加入一个 cnt 数组优化，这个数组记录每个格子继续走下去所能得到的宝藏的最大值，以后在走到这个格子时可以直接调用 cnt 中的数据。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=105;
int n,m,mp[N][N],cnt[N][N];
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};

int dfs(int x,int y){
	int maxx=0;
	if(cnt[x][y]) return cnt[x][y];
	for(int i=0;i<4;i++){
		int nx=x+d[i][0],ny=y+d[i][1];
		if(nx<1 or nx>n or ny<1 or ny>m) continue;
		if(mp[nx][ny]>=mp[x][y]) continue;
		maxx=max(maxx,dfs(nx,ny));
	}
	cnt[x][y]=maxx+1;
	return maxx+1; 
}
int main(){
	freopen("treasure.in","r",stdin);
	freopen("treasure.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>mp[i][j];
		}
	}
	int res=-1,x,y;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int df=dfs(i,j);
			if(df>res){
				res=df;
				x=i,y=j;
			}
		}
	}
	cout<<x<<" "<<y<<'\n'<<res;
	return 0;
}

7.9 #D 蓬莱山仙峰台 - 邻接表

没有提交

题解

$N$ 和 $M$ 都是 $10^5$ ，稀疏图，使用邻接表。 两种逻辑相反的解法：

#1：

对于 $i$ 号观景台：遍历与之相连的所有观景台 $j$，如果有 $H_i\le H_j$ ，则终止遍历，如果遍历正常结束或没有任何一个观景台与 $i$ 号观景台相连，则 $i$ 号观景台是一个仙峰台，cnt++ 。

最终输出 cnt 。

#2：

首先把 cnt 设为 $n$ ，即假设每个观景台都是仙峰台。

对于 $i$ 号观景台：如果有任何一个与之相连的观景台 $j$ 的高度 $H_j$ 不小于 $H_i$ ，则 cnt-- 。

最终输出 cnt 。

//#1
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,x,y,cnt,high[N];
int h[N],e[N],ne[N],idx;

void add(int a,int b){
	idx++;
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx;
}

int main(){
	freopen("penglai.in","r",stdin);
	freopen("penglai.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>high[i];
	while(m--){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		bool flag=true;
		for(int j=h[i];j!=0;j=ne[j]){
			if(high[i]<=high[e[j]]){
				flag=false;
				break;
			}
		}
		if(flag) cnt++;
	}
	cout<<cnt;
	return 0;
}

---

//#2
#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m,x,y,cnt,high[N];
int h[N],e[N],ne[N],idx;

void add(int a,int b){
	idx++;
	e[idx]=b;
	ne[idx]=h[a];
	h[a]=idx;
}

int main(){
	freopen("penglai.in","r",stdin);
	freopen("penglai.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	cnt=n;
	for(int i=1;i<=n;i++) cin>>high[i];
	while(m--){
		cin>>x>>y;
		add(x,y);
		add(y,x);
	}
	for(int i=1;i<=n;i++){
		for(int j=h[i];j!=0;j=ne[j]){
			if(high[i]<=high[e[j]]){
				cnt--;
				break;
			}
		}
	}
	cout<<cnt;
	return 0;
}

7.10 #E 小W运水 - 最短路

比赛未参加

题解

本题可以使用任意最短路算法，但是 $n=2000$ 的数据范围使得 $O(n^3)$ 的 $Floyd$ 超时。

$n$ 和 $m$ 大小相近，稀疏图，使用邻接表存储和遍历。

首先用邻接表存图并使用任意的最短路算法计算从 $x$ 到 $y$ 的最小损耗，再记录这条路径上每一段的损耗，从 $100$ 逆推到出发时的水量。

未完，补题去！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！