题解-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\) 值:
\]
时间复杂度 \(\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\)。
这题的优化是真的巧,反正我比赛时没想到。
考虑以下情况:
\]
总的时间复杂度是:
\]
同时满足 \(\sum_{i=1}^p |w_i|=n\cdot m\),根据柯西不等式:
&\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})\)。可以通过。
- 代码:
//Data
const 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<node> w[N*N+7];
//Bfs
int 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<node>&s){ //多源无向无权图最短路模板 Bfs。
vector<node> 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<sz(q);i++){
node v=q[i];
while(sc+1<sz(s)&&s[sc+1].g<=v.g) q.pb(s[++sc]);
for(int t=0;t<4;t++){
node u=node(v.x+tx[t],v.y+ty[t]);
if(ok(u.x,u.y)&&v.g+1<d[u.x][u.y]) d[u.x][u.y]=u.g=v.g+1,q.pb(u);
}
}
}
//Main
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
scanf("%d",&a[i][j]);
if(a[i][j]==1) w[a[i][j]].pb(node(i,j,i+j-2));
else w[a[i][j]].pb(node(i,j,inf));
}
for(int key=2;key<=k;key++){
if(sz(w[key-1])*sz(w[key])<=n*m){
for(node&u:w[key]) for(node v:w[key-1])
u.g=min(u.g,v.g+abs(u.x-v.x)+abs(u.y-v.y));
} else {
vector<node> s;
for(node v:w[key-1]) s.pb(v);
Bfs(s);
for(node&u:w[key]) u.g=d[u.x][u.y];
}
}
printf("%d\n",w[k][0].g);
return 0;
}
祝大家学习愉快!
最新文章
- JavaScript基本数据类型和引用数据类型
- BZOJ1951[SDOI2010]古代猪文
- [ACM训练] 数据结构----树、二叉树----c++ &;&; python
- vc编译 zlib 1.2.8
- ACM: 限时训练题解-Rock-Paper-Scissors-前缀和
- python tornado框架使用
- Vim自动补全神器:YouCompleteMe
- InstallShield:自己备份
- sqlserver高版本到低版本迁移
- [Android] 使用Webview进行OAUTH
- 项目上传svn出问题
- PHP面向对象之解释器模式
- jQuery的get()post()getJson()方法
- es6重点笔记:let,const
- Redis 设计与实现 (八)--排序、慢查询日志、监视器
- Dubbo 源码分析系列之三 —— 架构原理
- Alpha 冲刺 (7/10)
- B - SETI POJ - 2065 (高斯消元)
- 洛谷 P1474 货币系统 Money Systems(经典)【完全背包】+【恰好装满的最大方案数量】
- C# 移动及限制移动距离