Just a Blog

杂谈

第一次在外面参加这么长时间的集训… 被各路大佬摧残…

7.25 并查集相关

CF468b TWOSETS

题目传送门

题目大意

给出 $n$ 个各不相同的数字，将它们分别放入 $A$ 和 $B$ 两个集合中，使它们满足：

若数字 $x$ 在集合 $A$ 中，那么数字 $a-x$ 也在集合 $A$ 中；

若数字 $x$ 在集合 $B$ 中，那么数字 $b-x$ 也在集合 $B$ 中。

大体思路

分为以下几种情况

1.$a-x$与$b-x$有一个存在

$a-x$与$b-x$都不存在

$a-x$与$b-x$都存在

很显然，$a-(a-x)=x$,因此如果$a-x(b-x)$不在给定的集合中，则$x$就只能在$B(A)$中（注意顺序）。而如果$a-x$与$b-x$都不存在，便会无解。

重点在于情况三，如果$a-x$与$b-x$都存在，那么$x$在哪个集合都可以，这时候决定$x$在哪里的并不是$x$本身，而是与$a-x$与$b-x$有关的数。

综合以上情况，考虑用并查集维护。

代码

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
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
#include <map>
using namespace std;
#define gc ch = getchar()
int read(){
	int ret = 0, f = 1;char gc;
	while(!isdigit(ch) && (ch ^ '-'))gc;
	if(ch == '-')f = -1,gc;
	while(isdigit(ch)){ret = (ret << 3) + (ret << 1) + (ch ^ '0'), gc;}
	return ret * f;
}
#undef gc
const int maxn = 100010;
map<int, int>mp;
int n, a, b;
int x, y;
int pos[maxn];
int fa[maxn];
int findx(int x){return fa[x] == x ? x : fa[x] = findx(fa[x]);}
void merge(int x, int y){
	int fi = findx(x), fj = findx(y);
	if(fi != fj)
		fa[fi] = fj;
}
int main(){
	n = read(), a = read(), b = read();
	for(int i = 1; i <= n; ++i){
		pos[i] = read();
		mp[pos[i]] = i;
		fa[i] = i;
	}
	x = n + 1, y = n + 2;
	fa[x] = x, fa[y] = y;
	for(int i = 1; i <= n; ++i){
		// cout<<pos[i]<<"  "<<a-pos[i]<< " "<<b-pos[i]<<endl;
		// cout<<"!!"<<mp[a - pos[i]]<< " "<<mp[b - pos[i]]<<endl;
		if(!mp[a - pos[i]]){
			merge(i, y);
			// merge(mp[])
		}
		else { 
			merge(mp[a - pos[i]], i);
		}
		if(!mp[b - pos[i]]){
			merge(i, x);
		}
		else {
			merge(mp[b - pos[i]], i);
		}
		// cout<<findx(i)<<endl;
	}
	int x1 = findx(x), x2 = findx(y);
	if(x1 == x2){cout<<"NO"<<endl;return 0;}
	cout<<"YES"<<endl;
	for(int i = 1; i <= n; ++i){
		// cout<<findx(i)<<endl;
		if(findx(i) == x1)cout<<"0"<< " ";
		else cout<<"1"<<" ";
	}
}

luogu P3295 [SCOI2016]萌萌哒

题目传送门

题目大意

给定一个序列$S$的长度为$n$以及$m$对区间$(l_1,r_1,l_2,r_2)$知每一对区间中的每个数都相同，求最终序列的方案数。

大体思路

有$m$对区间，每对区间中的每个数都相同。因为最终要求的是方案数，不用考虑单独的一种方案，考虑使用并查集维护，将每一对区间中的每一对数塞到一个并查集内部，最终答案就是$10^x＊９$($ｘ$为并查集的总数)。

此时合并的复杂度最差为$O(n^2)$，但是查询的复杂度仅为$O(n)$，无法接受。

然后通过细（看）致（了）思（题）考（解），发现可以使用类似ST表的倍增进行解决。设$id[j][i]$表示以$i$为左端点，长度为$2^j$的区间的编号，在合并时，直接合并代表两段区间的$(logn)$个区间即可。查询时，因为查询的是原始的$n$个节点，所以需要针对一段区间，将其合并下放。（实现方式与st表类似）。此时合并$O(logn)$，查询$O(logn)$，可以通过。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
typedef long long ll;
const int maxn = 100010;
const ll mod = 1e9 + 7;
int n, m;
int tot, l1, r1, l2, r2;
int id[30][maxn], num[maxn * 30];
int fa[maxn * 30], h[maxn * 30];
int bin[30];
int findx(int x){return fa[x] == x ? x : fa[x] = findx(fa[x]);}
void merge(int x, int y){
	int fi = findx(x), fj = findx(y);
	if(h[fi] > h[fj]){
		swap(fi, fj);
	}
	if(h[fi] == h[fj])h[fj] ++;
	fa[fi] = fj;
}
ll ksm(ll now, ll a){
	ll res = 1, base = now;
	while(a){
		if(a & 1)
			res = (1ll * res * base) % mod;
		base = (1ll * base * base) % mod;
		a >>= 1;
	}
	return res;
}
int main(){
	#ifndef ONLINE_JUDGE
	freopen("test.in", "r", stdin);
	#endif
	scanf("%d%d", &n, &m);
	bin[0] = 1;
	for(int p = 1; p <= 20; ++p){
		bin[p] = (bin[p - 1] << 1) % mod;
	}
	for(int j = 0; j <= 20; ++j){
		for(int i = 1; i <= n; ++i){
			id[j][i] = ++tot, num[tot] = i;
			fa[tot] = tot, h[tot] = 1;
		}
	}
	for(int i = 1; i <= m; ++i){
		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
		for(int j = 20; j >= 0; --j){
			if(l1 + bin[j] - 1 <= r1){
				merge(id[j][l1], id[j][l2]);
				l1 += bin[j], l2 += bin[j];
			}
		}
	}
	// cout<<1<<endl;
	for(int j = 20; j; --j){
		// cout<<j<< " ";
		for(int i = 1; i + bin[j] - 1 <= n; ++i){
			int x = findx(id[j][i]), a = num[x];
			merge(id[j - 1][a], id[j - 1][i]);
			merge(id[j - 1][a + bin[j - 1]], id[j - 1][i + bin[j - 1]]);
			// cout<<"j"<<j<< " "<<i<<endl;
		}
	}
	// cout<<1<<endl;
	ll cnt = 0;
	for(int i = 1; i <= n; ++i){
		if(findx(id[0][i]) == id[0][i])cnt++;
	}
	// cout<<cnt<<endl;
	cout<<(9ll * ksm(10, cnt - 1)) % mod;
	return 0;
}

7.25 分治相关

luogu P1429 平面最近点对（加强版）

题目传送门

题目大意

平面上有$n$个点$(2≤n≤200000)$，求距离最近的点对

主要思路

考虑直接枚举$n$个点，$O(n^2)$显然不可做。。。。

考虑分治，将平面沿$x$坐标的中位数裁开，这样要求的解被分成三类。

1.在左侧的解

2.在右侧的解

3.横跨分割线的解

解1与解2分开递归计算即可，重点考虑解3如何处理。

然后发现了一种优美的性质。对于一个点来说，其要想和横跨分治边界的另一个点更新最优解，最多只有$6$个点符合要求。

设左侧的递归答案为$d1$，右侧的递归答案为$d2$，则当前最优解为$\delta=min(d1,d2)$,如果要想使$dis(x,y) < \delta$，很明显另一个点的取值只能是一个$[\delta,2\delta]$的矩形，又因为$\delta=min(d1,d2)$，则右侧每两个点之间的距离$dis\le\delta$，也就是说，最多只能有$6$个点被选择。

先按$x$轴第一关键字，$y$轴第二关键字排序,
每一层分治的复杂度为$O(6n)$，总复杂度$O(logn)$。

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
using namespace std;
const int maxn = 200010;
const int inf = 2 << 20;
int n;
struct node {
	double x, y;
}a[maxn];
int tmp[maxn];
bool cmp1(node &a, node &b){
	return a.x == b.x ? a.y < b.y : a.x < b.x;
}
bool cmp2(int &i, int &j){
	return a[i].y < a[j].y;
}
double dist(int i, int j){
	return sqrt((a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y));
}
double merge(int l, int r){
	double d = inf;
	if(l == r)return d;
	if(l + 1 == r)return dist(l, r);
	int mid = (l + r) >> 1;
	double d1 = merge(l, mid);
	double d2 = merge(mid + 1, r);
	d = min(d1, d2);
	int cnt = 0;
	for(int i = l; i <= r; ++i){
		if(fabs(a[mid].x - a[i].x) < d){
			tmp[++cnt] = i;
		}
	}
	sort(tmp + 1, tmp + cnt + 1, cmp2);
	double d3;
	for(int i = 1; i <= cnt; ++i){
		for(int j = i + 1; j <= cnt && fabs(a[tmp[j]].y - a[tmp[i]].y) < d; j++){
			d3 = dist(tmp[i], tmp[j]);
			if(d > d3)d = d3;
		}
	}
	return d;
}
int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i)scanf("%lf%lf", &a[i].x, &a[i].y);
	sort(a + 1, a + n + 1, cmp1);
	printf("%.4lf", merge(1, n));
	return 0;
}
 上一页

题解 DP

 评论