CF677D Vanya and Treasure

有一个 \(n\times m\) 的矩阵 \(a(1\le a_{i,j}\le p)\)，求从起点 \((1,1)\) 出发依次遍历值为 \(1\to p\) 的矩阵单元的最短路径曼哈顿距离。保证满足 \(a_{i,j}=p\) 的 \((i,j)\) 唯一。

数据范围：\(1\le n,m\le 300\)，\(1\le p\le n\cdot m\)。

---

先记录 \(\tt vector\) 数组 \(w\)，\(w_t\) 表示 \(a_{i,j}=t\) 的位置集合。

\(w_t\) 的每个元素有三个属性：\(x,y,g\)。\(x\) 和 \(y\) 是位置坐标，\(g\) 是出发遍历矩阵值 \(1\to t\) 后到 \((x,y)\) 的最短路径长度。

---

暴力做法：从 \(w_{i-1}\) 的所有 \(g\) 值递推 \(w_i\) 的所有 \(g\) 值：

\[u.g=\min_{v\in w_{i-1}}\{v.g+{\rm abs}(u.x-v.x)+{\rm abs}(u.y-v.y)\}(u\in w_i)\]

时间复杂度 \(\Theta\left(\sum_{i\in[2,p]}|w_{i-1}|\cdot |w_i|\right)\le\Theta(n^2m^2)\)。

• 怎么卡到 \(\Theta(n^2m^2)\) 的？

比如 \(n=300,m=300,p=2\)，矩阵一半是 \(1\) 一半是 \(2\)。

---

这题的优化是真的巧，反正我比赛时没想到。

考虑以下情况：

\[\forall i\in[2,p]:|w_{i-1}|\cdot|w_i|\le n\cdot m\]

总的时间复杂度是：

\[\Theta\left(\sum_{i\in[2,p]}|w_{i-1}|\cdot |w_i|\right)\]

同时满足 \(\sum_{i=1}^p |w_i|=n\cdot m\)，根据柯西不等式：

\[\begin{split}&\left(\sum_{i=2}^p|w_{i-1}|\cdot |w_i|\right)^2\\\le&\sum_{i=1}^{p-1}|w_i|^2\sum_{i=2}^{p}|w_i|^2\\\le&\left(\sum_{i=1}^{p}|w_i|^2\right)^2\\\le&\left(\sqrt{n\cdot m}\times\left(\sqrt{n\cdot m}\right)^2\right)^2\end{split}\]

所以 \(\sum_{i=2}^p|w_{i-1}|\cdot |w_i|\le n\cdot m\times\sqrt{n\cdot m}\)。

复杂为 \(\Theta(n\cdot m\sqrt{n\cdot m})\) 可以通过。

---

但是如果 \(\exists i\in[2,p]:|w_{i-1}|\cdot|w_i|>n\cdot m\) 怎么办呢？

可以套个 \(\Theta(V)\) 的多源无向无权图最短路模板 \(\tt Bfs\)。

所以此时单次递推的时间复杂度也是 \(\Theta(n\cdot m)\)。

这样的单次递推与 \(|w_{i-1}|\cdot|w_i|=n\cdot m\) 相比：

一次递推时间复杂度相等。

由于对于这个 \(i\) 的 \(|w_{i-1}|\cdot|w_i|\) 大，所以对于其他 \(i\) 的 \(|w_{i-1}|\cdot|w_i|\) 较小。所以总时间复杂度小。

所以这样优化后总时间复杂度 \(\le \Theta(n\cdot m\sqrt{n\cdot m})\)。可以通过。

---

• 代码：

//Dataconst int N=3e2;int n,m,k,a[N+7][N+7];struct node{int x,y,g;node(int X=0,int Y=0,int G=0){x=X,y=Y,g=G;}};vector w[N*N+7];//Bfsint d[N+7][N+7];int tx[]={0,0,-1,1},ty[]={-1,1,0,0};int ok(int x,int y){return 1<=x&&x<=n&&1<=y&&y<=m;}void Bfs(vector&s){ //多源无向无权图最短路模板 Bfs。vector q;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) d[i][j]=inf;int sc=-1;q.pb(s[++sc]);for(int i=0;i

祝大家学习愉快！