求助站外题(悬棺

学术版

Always_Remember_It @ 2024-11-29 11:59:27

给出n*m的地图,每个格子一个值a[i][j],q次询问,每次给出2点,问从一个点出发走到另一个点所经历格子的所有点权值最小值的最大值

n,m是10的3次方级别的,q是10的5次方级别的

想问2个问题

1.正解是不是建边构成无向连通图之后求最大生成树,然后预处理出每两点之间的最大值?

2.但是如果考场上遇到它满分做法很难调,部分分做法怎么写(无论复杂度多少,只要正确的部分分做法就行


by xxxxxzy @ 2024-11-29 13:04:38

  1. 最大生成树后上树剖维护。
  2. 很好打,没必要打部分分。

|