Bzoj1514 [POI2006]ZAB-Frogs

, , ,

Description

https://www.luogu.com.cn/problem/P3438

Solution

这题的关键在于求出每个点到最近坏点的距离。求出来以后二分即可。

先讲一下我之前的一个很 naive 的错解。

考虑多源最短路，对每个点维护到最近坏点的距离和是哪个坏点，来更新其周围的四个点。最短路过程可以类似于 01bfs 开个桶，复杂度 $O(nm)$。

后来被一组数据卡了，发现是这个点可能与周围四个点的最近坏点都不同，也就是可能最优转移没转移到。

1
2
3
4
5
6
4 4
1 1 1 1
3
1 4
4 1
3 3

如果算周围八个点，能有 96 分，但是应该和还是错的只是数据卡的比较少而已。

回到正解。考虑**对某一列进行计算，也就是固定 $j$**。记 $c_{i,j}$ 表示 $(i,j)$ 到同一行的最近的坏点的距离，$O(nm)$ 很好预处理。有 $f_{i,j}=\min (i-k)^2+c_{k,j}$。斜率优化维护一个下凸壳就好了。正反做两遍，这样显然是不重不露的。

复杂度 $O(nm\log nm)$，瓶颈在于二分答案。

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define maxn 1005
#define put() putchar('\n')
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
using namespace std;
Tp void read(T &x){
    int f=1;x=0;char c=getchar();
    while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
    while (c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();}
    x*=f;
}
namespace Debug{
	Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
	Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
	#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
#define fi first
#define se second
#define mk make_pair
const int mod=1e9+7;
int power(int x,int y=mod-2) {
	int sum=1;
	while (y) {
		if (y&1) sum=sum*x%mod;
		x=x*x%mod;y>>=1;
	}
	return sum;
}
int n,m,t;
int tp,sx,sy,tx,ty;
int fx[8]={0,0,1,-1,1,-1,1,-1};
int fy[8]={1,-1,0,0,1,-1,-1,1};
int calc(int x,int y) {return x*x+y*y;}
int vis[maxn][maxn],f[maxn][maxn];
bool check(int val) {
	queue<pair<int,int> >q;
	int i,j,x,y,xx,yy;
	if (f[sx][sy]<val) return 0; 
	for (i=1;i<=n;i++) for (j=1;j<=m;j++) vis[i][j]=0;
	q.push(mk(sx,sy));vis[sx][sy]=1;
	while (!q.empty()) {
		x=q.front().fi,y=q.front().se,q.pop();
		for (i=0;i<4;i++) {
			xx=fx[i]+x,yy=fy[i]+y;
			if (xx>0&&xx<=n&&yy>0&&yy<=m&&f[xx][yy]>=val&&!vis[xx][yy]) {
				vis[xx][yy]=1;
				q.push(mk(xx,yy));
			}
		}
	}
	return vis[tx][ty];
}
int b[maxn][maxn],c[maxn][maxn];
int q[maxn],head,tail,id;
double slope(int i,int j) {return 1.0*(calc(i,c[i][id])-calc(j,c[j][id]))/(2.0*i-2.0*j);}
signed main(void){
	freopen("1.in","r",stdin);
	int i,j,k,xx,yy,x,y;
	read(n);read(m);int N=n*n+m*m;
	read(sx),read(sy),read(tx),read(ty);
	read(t);
	for (i=1;i<=t;i++) {
		read(x),read(y);
		b[x][y]=1;
	}
	for (i=1;i<=n;i++) {
		int las=-1e9;
		for (j=1;j<=m;j++) {
			if (b[i][j]) las=j;
			c[i][j]=j-las;
		} 
		las=1e9;
		for (j=m;j>=1;j--) {
			if (b[i][j]) las=j;
			c[i][j]=min(c[i][j],las-j);
		}
	}
	for (j=1;j<=m;j++) {
		id=j;
		head=1;tail=0;
		for (i=1;i<=n;i++) {
			while (head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i)) tail--;
			q[++tail]=i;
			while (head<tail&&slope(q[head],q[head+1])<i) head++;
			k=q[head];
			f[i][id]=calc(i-k,c[k][id]);
		}
		for (i=1;i<=n/2;i++) swap(c[i][id],c[n-i+1][id]),swap(f[i][id],f[n-i+1][id]); 
		head=1;tail=0;
		for (i=1;i<=n;i++) {
			while (head<tail&&slope(q[tail-1],q[tail])>=slope(q[tail],i)) tail--;
			q[++tail]=i;
			while (head<tail&&slope(q[head],q[head+1])<i) head++;
			k=q[head];
			f[i][id]=min(f[i][id],calc(i-k,c[k][id]));
		}
		for (i=1;i<=n/2;i++) swap(c[i][id],c[n-i+1][id]),swap(f[i][id],f[n-i+1][id]); 
	}
	// for (i=1;i<=n;i++) for (j=1;j<=m;j++) gdb(i,j,f[i][j]);
	int l=0,r=N,mid;
	while (l+1<r) {
		mid=l+r>>1;
		if (check(mid)) l=mid;
		else r=mid;
	} 
	printf("%lld\n",l);
	return 0;
}
//i=begin && g++ $i.cpp -o $i -std=c++14 -O2 && ./$i