BZOJ1604 [Usaco2008 Open]Cow Neighborhoods 奶牛的邻居

在一道usaco的题上wa了三次。我也是厉害。

其实好像有简单做法的。不过我是要脑补一下曼哈顿最小生成树。

对于一个平面图上的点的曼哈顿最小生成树，一定存在一种方案，使得每个点的度数至多为8。也就是说以斜率为0,inf,1,-1的四条直线分出来的八个区域里各有一个点就行了。然后是可以保证的。

于是就是拿俩树状数组扫四遍就行了。

1	#include <cstdio>
2	#include <cstdlib>
3	#include <cstring>
4	#include <algorithm>
5	
6	using namespace std;
7	
8	const int inf = 0x3f3f3f3f;
9	
10	struct point {
11		int x, y, i;
12		point() {
13			x = -inf, y = -1;
14		}
15		point(int xo, int yo) {
16			x = xo, y = yo;
17		}
18		inline void init(int ix) {
19			scanf("%d%d", &x, &y);
20			i = ix;
21		}
22	};
23	
24	inline bool operator <(const point& a, const point& b) {
25		return (a. x < b. x) || (a. x == b. x && a. y < b. y);
26	}
27	
28	const int maxn = 100009;
29	const int maxx = 1e9;
30	
31	int n, c, r[maxn], sz[maxn], cnt, msz;
32	int v[maxn], tv, w[maxn], tw;
33	point a[maxn], ta[maxn], tb[maxn];
34	
35	int getRoot(int x) {
36		register int p, q;
37		for (p = r[x]; p ^ r[p]; p = r[p]);
38		for (; x ^ p; q = r[x], r[x] = p, x = q);
39		return x;
40	}
41	inline void join(int u, int v) {
42		r[getRoot(u)] = getRoot(v);
43	}
44	
45	point btQry(point* t, int p) {
46		point s(-inf, -1);
47		for (++ p; p; p -= (p & -p))
48			if (s < t[p])
49				s = t[p];
50		return s;
51	}
52	void btChg(point* t, int p, point v) {
53		for (++ p; p < maxn; p += (p & -p))
54			if (t[p] < v)
55				t[p] = v;
56	}
57	
58	inline bool isNeighbour(const point& a, const point& b) {
59		return abs(a. x - b. x) + abs(a. y - b. y) <= c;
60	}
61	
62	void span() {
63		sort(a, a + n);
64		tv = tw;
65		for (int i = 0; i < n; ++ i) {
66			v[i] = a[i]. y - a[i]. x;
67			w[i] = - a[i]. x - a[i]. y;
68		}
69		sort(v, v + n);
70		tv = unique(v, v + n) - v;
71		sort(w, w + n);
72		tw = unique(w, w + n) - w;
73		for (int i = 1; i <= tv || i <= tw; ++ i)
74			ta[i] = tb[i] = point();
75		for (int i = 0; i < n; ++ i) {
76			int p(lower_bound(v, v + tv, a[i]. y - a[i]. x) - v);
77			point g(btQry(ta, p));
78			if (g. y > -1 && isNeighbour(a[i], a[g. y]))
79			   join(a[i]. i, a[g. y]. i);	
80			btChg(ta, p, point(a[i]. x + a[i]. y, i));
81			p = lower_bound(w, w + tw, - a[i]. x - a[i]. y) - w;
82			g = btQry(tb, p);
83			if (g. y > -1 && isNeighbour(a[i], a[g. y]))
84			   join(a[i]. i, a[g. y]. i);	
85			btChg(tb, p, point(a[i]. x - a[i]. y, i));
86		}
87	}
88	
89	int main() {
90	#ifndef ONLINE_JUDGE
91		freopen("in.txt", "r", stdin);
92	#endif
93	
94		scanf("%d%d", &n, &c);
95		for (int i = 0; i < n; ++ i) {
96			a[i]. init(i);
97			r[i] = i;
98		}
99		span();
100		for (int i = 0; i < n; ++ i)
101			a[i]. x = maxx - a[i]. x;
102		span();
103		for (int i = 0; i < n; ++ i)
104			swap(a[i]. x, a[i]. y);
105		span();
106		for (int i = 0; i < n; ++ i)
107			a[i]. x = maxx - a[i]. x;
108		span();
109		memset(sz, 0, sizeof(sz));
110		for (int i = 0; i < n; ++ i) {
111			if (r[i] == i)
112				++ cnt;
113			++ sz[getRoot(i)];
114		}
115		for (int i = 0; i < n; ++ i)
116			if (r[i] == i && sz[i] > msz)
117				msz = sz[i];
118		printf("%d %d\n", cnt, msz);
119	}
120