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; }
|