题目大意
给一个长度为$n$的$01$序列$S$和$m$个描述,每个描述告诉S[l~r]中$1$的个数的奇偶性,求从哪个描述开始与前面的描述有矛盾,从第$k$个描述开始矛盾,则输出$k-1$,所有描述都没有矛盾,则输出$m$
解题思路
带权并查集做法
$s[i]$表示前$i$个数中$1$的个数,那么有:
S[l~r]有奇数个1 <==> s[r]和s[l-1]奇偶性不同(不同类)
S[l~r]有偶数个1 <==> s[r]和s[l-1]奇偶数相同(同类)
(注意写题过程中并不关心s数组具体是什么,只是关注$r$和$l-1$的关系)
那么有三种传递关系:
1.若$x、y$奇偶性相同,$y、z$奇偶性相同,则$x、z$奇偶性相同
2.若$x、y$奇偶性相同,$y、z$奇偶性不同,则$x、z$奇偶性不同
3.若$x、y$奇偶性不同,$y、z$奇偶性不同,则$x、z$奇偶性相同
带权并查集处理传递关系即可。本题$d[x]%2==0$说明$x$与根节点同类,否则说明不同类。
每给出一个$x$和$y$的描述:
1.若当前$px!=py$,说明这是第一次描述$x$和$y$的关系,则要把它们合并,不妨让$p[px]=py$,更新$d[px]$
2.若当前$px=py$,我们可以通过$(d[x]+d[y])%2$知道$x$和$y$的关系,从而判断是否和当前描述有矛盾
扩展域并查集做法
带权并查集更像是存了一个个相对关系,扩展域更像是直接存下了条件。这里有奇偶两种类型,因此扩展域并查集的大小是$2N$。这样理解此题最好懂:一个集合中若有$x$,则说明这个集合中$x$是奇数,一个集合中若有$x+N$,说明这个集合中$x$是偶数。一个集合中若存在互斥的条件,那么就说明有矛盾
具体代码
带权并查集做法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 10010;
int n, m, p[N], d[N];
unordered_map<int, int> S;
int get(int x) //应该是非保序离散化的最简单写法
{
if (S.count(x) == 0)
S[x] = ++n;
return S[x];
}
int find(int x)
{
if (p[x] != x) //模板
{
int t = find(p[x]);
d[x] += d[p[x]];
// d[x]%=2 这里可以加上这一句防止可能的溢出
p[x] = t;
}
return p[x];
}
int main()
{
cin >> n >> m;
n = 0;
for (int i = 0; i < N; i++)
p[i] = i;
int res = m; //没有矛盾就输出m
for (int i = 1; i <= m; i++)
{
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b); // 此题数据需要离散化
int mod = type == "odd" ? 1 : 0;
int pa = find(a), pb = find(b);
if (pa == pb)
{
if (((d[a] + d[b]) % 2 + 2) % 2 != mod)
{
res = i - 1;
break;
}
}
else
{
p[pa] = pb;
d[pa] = ((d[a] + d[b] + mod) % 2 + 2) % 2; //在草稿纸上分类讨论可以总结出这个式子
}
}
cout << res << endl;
return 0;
}
扩展域并查集做法
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 2e4 + 10;
int n, m, p[N * 2];
unordered_map<int, int> S;
int get(int x) //应该是非保序离散化的最简单写法
{
if (S.count(x) == 0)
S[x] = ++n;
return S[x];
}
int find(int x)
{
if (p[x] != x)
p[x] = find(p[x]);
return p[x];
}
int main()
{
cin >> n >> m;
n = 0;
for (int i = 0; i < N * 2; i++)
p[i] = i;
int res = m; //没有矛盾就输出m
for (int i = 1; i <= m; i++)
{
int a, b;
string type;
cin >> a >> b >> type;
a = get(a - 1), b = get(b); // 此题数据需要离散化
if (type == "even") //说明x和y应该同类
{
if (find(a + N) == find(b)) //不同类却在一个集合里,矛盾
{
res = i - 1;
break;
}
p[find(a)] = find(b);
p[find(a + N)] = find(b + N);
}
else
{
if (find(a) == find(b)) //同理
{
res = i - 1;
break;
}
p[find(a)] = find(b + N);
p[find(a + N)] = find(b);
}
}
cout << res << endl;
return 0;
}