How Many Answers Are Wrong

Posted on Edited on In

题目大意:给定一些区间的和,如果发现与前面矛盾就认为是假话.

来源:How Many Answers Are Wrong

带权并查集判错的经典例题,直到如今才学会.

这个算法实在是太经典了,所以我要十分详细的把自己掌握的写出来,方便自己和后人查阅,在此感谢这篇题解的详细指导

为什么要用并查集?

对于通常的并查集例题,都是一开始每个元素构成一个单元素集合.其后不断合并.

与这题联系起来便十分抽象,因为我们要判断真假,怎么判?肯定是比较.怎么比?跟谁比?比什么?

怎么比:假设当前输入a,b,v与之前所有输入的a,b,v相比,存在a=a,b=b,v=v,则说明没错,

但是一定能找到吗?如果找不到,说明一定是错吗?显然不是,因此不能这么比.

要想比,首先得找一个基准值,如果(a到c的距离) - (b到c的距离) == v,说明正确,解决了跟谁比,怎么比.

具体思路:

给出一个闭区间\([a,b]\),转化为:\((a-1,b]\),因为半开半闭区间有个性质:\((a,b] + (b,c] = (a,c]\)

再来考虑如何解读一条信息:a,b,v?可以解读为:a与b有关系,关系的权值是一个v

但是如何求ac,bc之间的距离,首先保证a,b的基准值都是c才可以,怎么把a,c的基准值都为c?

考虑到并查集是用来记录联通关系的.

如果当前两个点的基准值不一样,说明本条信息一定是正确的,因为无法根据其现有数据推算正假,于是认其为真.之后合并当前信息,为下一次查询做准备.

如果当前两个点的基准值一样,那么说明两个点之间的距离可以通过之前的计算出来,则比较,相等没事,不相等的话计数器加1

更清晰的话,有如下图表示:

用sum[k]表示k到k的基准点之间距离.

如果想合并a,b,最终目的是求a,b到共同基准值的距离.

首先求出a,b的祖先,然后比较x,y默认x认y为爹(a的祖先认b的祖先为爹)

所以a的祖先变成了y,x的祖先变成了y.

其中显然: \[ sum[x] = sum[b] + v - sum[a] \]

\(sum[b]+v\)是a到y的距离,减去a到x的距离\(sum[x]\)剩下的就是x到y的距离.(这里的区间都是左闭右开)

至此,代码与思路就都十分清晰了.

代码如下:

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e6 + 66;

int n, m, res;
int a[N], fa[N], sum[N];

inline int yhm_find(int x)
{
    if (x == fa[x]) return x;
    int t = yhm_find(fa[x]);
    sum[x] = sum[x] + sum[fa[x]];
    return fa[x] = t;
}

inline void yhm_clear()
{
    res = 0;
    memset(fa, 0, sizeof fa);
    memset(sum, 0, sizeof sum);
    return;
}

inline void yhm_func()
{
    int i, l, r, k, x, y;
    for (i = 1; i <= n; ++ i) fa[i] = i;

    for (i = 1; i <= m; ++ i)
    {
        l = read(), r = read(), k = read();
        x = yhm_find(l - 1), y = yhm_find(r);
        if (x != y)
        {
            fa[x] = y;
            sum[x] = sum[r] - sum[l - 1] + k;
        }
        else if (sum[l - 1] - sum[r] != k) ++ res;
    }
    return (void)(put(res));
}

signed main()
{
    while (scanf ("%d%d", &n, &m) != EOF)
    {
        yhm_clear();
        yhm_func();
    }
    return 0;
}

后记:

并查集经典应用