竞赛讨论区 > 本人考场做法
头像
527107307
发布于 2018-07-31 17:41
+ 关注

本人考场做法

这题我在考场上的想法是这样的:
题目要求出所有的Dist[i][j],这可能是一个比较重要的性质。
看起来可以把所有Dist[i][j]放在一起转移?
然后我想到两个转移:
Dist[i][j']=Dist[i][j]+1, a[j]<=j'<=j
Dist[i'][j]=Dist[i][j]+1, a[i]<=i'<=i
这样比较舒服的是转移都是某一维的一段连续区间了。
没错,我考场上并没有想清楚。。。并没有想到先往左走再往右走的情况会漏转移。
不过我写完以后一遍过了对拍!
为什么呢?因为这题的性质决定了:最短路一定是先往右走一段再往左走一段,否则,如果路径中存在片段i->j->k,其中a[i]<=j<i,b[k]<=j<k,那么当k<=i时,有k>=a[i],当k>i时,有i>=b[k],于是可以直接走i->k。
于是我们可以将所有的(i,i)点作为源,用上述两种转移BFS。
因为BFS的转移是一段区间,所以可以开两个n^2的并查集来代替visit数组,就可以做到O(n^2*α(n))了。
然而这样会被卡常数。。。我当时卡了一波常数还是要跑4s。。。
接着就想:能不能换一个做法?于是我用暴力打了个表,发现一个性质:
Dist[i][j-1]>=Dist[i][j], 1<j<=i
Dist[i-1][j]>=Dist[i][j], 1<i<=j
没错,我当时依旧并没有想清楚这个性质为啥是对的。。。然后在原来的程序上瞎写了一个优化,又过了对拍,并且交上去AC了。。。
其实冷静分析一下就知道为啥了。
以 Dist[i][j']=Dist[i][j]+1, a[j]<=j'<=j 为例(另一个转移同理),如果j<=i,那么这个性质就很好解释了。
而如果j>i,其实我们只需要转移 a[j]<=j'<=i 的 j',i<j'<=j 这一部分的转移是没用的,同样也很好解释了。
这是因为,考虑i到j的最短路:先往右走 i->x[1]->x[2]->...->x[u],令 y[v]=x[u],再往左走 y[v]->y[v-1]->y[v-2]->...->y[1]->j。
BFS的转移相当于是,从(x[u],y[v])出发,每次把x[u]移到x[u-1]或者把y[v]移到y[v-1],直到移到(i,j)为止。
我们完全可以每次选择x[u-1]和y[v-1]中较大的一个来移,这样每次移动都会减小min(x[u],y[v])。
这也就证明了对于j>i的状态(i,j),只要转移到j'<i的(i,j')就行了。
因此最后加的优化就是,去掉并查集,对每个i维护left[i]为满足j<=i且(i,j)被访问过的最大的j,以及up[i]为满足j<=i且(j,i)被访问过的最大的j,当(i,j)加入队列时把满足j<j'<left[i]的(i,j')或者i<i'<up[j]的(i',j)都加入队列,并更新left[j]和up[i]。
这样就可以做到O(n^2)了。

全部评论

(0) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐