Liveddd's Blog

愛にできることはまだあるかい

CF677D Vanya and Treasure

发表于 更新于 分类于
本文字数： 3.4k 阅读时长 ≈ 8 分钟

巧妙的根号分治。

考虑暴力做法，我们将所有点按照值分层，每层节点个数设为 $w_i$，层之间暴力转移。但是我们有两种不同的转移方式：

  1. 暴力枚举两层之间所有点进行转移，单次时间复杂度 $\mathcal O(w_i\cdot w_{i+1})$。
  2. 直接在网格图上进行多源多汇 BFS，单次时间复杂度 $\mathcal O(nm)$。

直接用两种做法之一很容易被卡成 $\mathcal O(n^2m^2)$。我们考虑将两种做法结合，对于每一层，若 $w_i\cdot w_{i+1}\le nm$，则采用做法一，否则采用做法二。接下来我们证明这样做的时间复杂度是对的。

考虑 $w_i\cdot w_{i+1}\le nm$ 的情况。我们们有 $\sum_i w_i=nm$，利用均值不等式得到 $\sum_i \sqrt{w_i\cdot w_{i+1}}\le nm$。那么 $\sum_i {w_i\cdot w_{i+1}}=\sum_i(\sqrt{w_i\cdot w_{i+1}})^2\le \sqrt{nm}\sum_i \sqrt{w_i\cdot w_{i+1}}\le nm\sqrt{nm}$。这样时间复杂度上限是 $\mathcal O(nm\sqrt{nm})$。

考虑 $w_i\cdot w_{i+1}>nm$。那么有 $\max(w_i,w_{i+1})>\sqrt{nm}$，这样的点最多有 $\mathcal O(\sqrt{nm})$ 个，时间复杂度也是 $\mathcal O(nm\sqrt{nm})$。至此我们得到这个时间复杂度正确的算法。

Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int N=300+10;
const int INF=1e9;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};
template<class T>
inline void read(T &x)
{
    x=0;bool f=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    if(f)x=~x+1;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1)
{
    read(x),read(x1...);
}
int n,m,p;
int a[N][N],f[N][N];
int dis[N][N];
struct Point{int x,y;};
vector<Point>w[N*N];
queue<Point>q;
inline void ckmin(int &x,int y){x=x<y?x:y;}
inline int dist(const Point &u,const Point &v){return abs(u.x-v.x)+abs(u.y-v.y);}
inline bool cmp(const Point &u,const Point &v){return f[u.x][u.y]<f[v.x][v.y];}
inline void BFS(int key)
{
    memset(dis,0x3f,sizeof(dis));
    sort(w[key].begin(),w[key].end(),cmp);
    q.push(w[key][0]);
    dis[w[key][0].x][w[key][0].y]=f[w[key][0].x][w[key][0].y];
    auto it=w[key].begin();
    it++;
    while(!q.empty())
    {
        Point now=q.front();
        q.pop();
        for(;it!=w[key].end()&&f[(*it).x][(*it).y]<=dis[now.x][now.y]+1;it++)
            dis[(*it).x][(*it).y]=f[(*it).x][(*it).y],q.push(*it);
        for(int i=0;i<4;i++)
        {
            Point ne=now;
            ne.x+=dx[i],ne.y+=dy[i];
            if(ne.x<0||ne.x>n||ne.y<0||ne.y>m)continue;
            if(dis[now.x][now.y]+1<dis[ne.x][ne.y])
            {
                dis[ne.x][ne.y]=dis[now.x][now.y]+1;
                q.push(ne);
            }
        }
    }
    for(auto u:w[key+1])f[u.x][u.y]=dis[u.x][u.y];
}
int main()
{
    memset(f,0x3f,sizeof(f));
    read(n,m,p);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            read(a[i][j]);
            w[a[i][j]].push_back({i,j});
            if(a[i][j]==1)f[i][j]=i+j-2;
        }
    for(int i=1;i<p;i++)
    {
        if(w[i].size()*w[i+1].size()<=n*m)
            for(auto u:w[i])
                for(auto v:w[i+1])
                    ckmin(f[v.x][v.y],f[u.x][u.y]+dist(u,v));
        else BFS(i);
    }
    int ans=INF;
    for(auto u:w[p])ckmin(ans,f[u.x][u.y]);
    printf("%d\n",ans);
    return 0;
}