Tag: 离散化+带权并查集,dsu,Kuangbin
题目链接 | Here
题意
给出$k$条信息，每条信息表示一个区间内($[l,r]$)的$1$的个数为奇数($odd$)或是偶数($even$)。问从$1$开始，连续正确的信息为几条？
tips: $1 \leq l \leq r \leq 1e9 \quad 1 \leq k \leq 5000$
输入
第一行给出$n$代表区间的总长度为$[1,n]$
第二行给出$k$代表有$k$条信息
接下来$k$行，每行给出$l,r$代表区间，后面一个字符串代表一的个数是奇数($odd$)还是偶数($even$)。
1
2
3
4
5
6
7
| 10
5
1 2 even
3 4 odd
5 6 even
1 6 even
7 10 odd
|
输出
题解
由于区间的范围很大，不能直接开这么大的数组进行对应，而询问较小，所以我们需要对输入的区间范围进行离散化，之后使用带权并查集求解即可。
这边令奇数权为$1$，偶数权为$0$即可。
AC代码
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
| #include <iostream>
#include <algorithm>
#include <map>
#include <utility>
using namespace std;
#define pir pair<int,int>
#define mkp make_pair
#define pbk push_back
#define fi first
#define se second
#define all(v) v.begin(),v.end()
const int maxn = 5e3+100;
map<int,int> idx;
pir p[maxn];
int f[maxn<<1],v[maxn<<1],k[maxn<<1],arr[maxn<<1];
void init(int n) {
for(int i=0; i<=n; i++) f[i]=i;
}
int find(int u) {
if(f[u] != u) {
int t=f[u];
f[u] = find(f[u]);
v[u] = (v[u]+v[t])%2;
}
return f[u];
}
bool merge(int a,int b,int w) {
int fa=find(a),fb=find(b);
if(fa!=fb) {
f[fa] = fb;
v[fa] = ((v[b]+w-v[a])%2+2)%2;
return 1;
}
return (((v[a]+v[fa]-v[b])%2+2)%2==w);
}
int main() {
std::ios::sync_with_stdio(false);
int n,m,a,b,cnt=0;
string str;
cin >> n >> m;
for(int i=0; i<m; i++) {
cin >> a >> b >> str;
a--;
arr[cnt++] = a; arr[cnt++] = b;
p[i].fi = a; p[i].se = b;
if(str == "even") k[i]=0;
else k[i]=1;
}
sort(arr,arr+cnt);
cnt = unique(arr,arr+cnt)-arr;
init(cnt);
for(int i=0; i<cnt; i++) idx[arr[i]] = i;
int ans=m;
for(int i=0; i<m; i++) {
if(!merge(idx[p[i].fi],idx[p[i].se],k[i])) {
ans=i;
break;
}
}
cout << ans << endl;
return 0;
}
|
