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*9$($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(6
n)$,总复杂度$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;
}

 评论