ARC111-B

前言

一道不错的并查集题目,对于权值建图连边。最初模拟的时候队友一波就出来这个是并查集题,然后我跟着写了一发,可惜赛时$wa$了三个点。赛后发现,在合并的时候我的细节处理出了一些问题。

题意

传送门: B - Reversible Cards

给定$n$张牌,每张牌的正反面各有一个权值,为$a_i, b_i$,你可以随意翻转这些牌,使得最后这$n$张牌朝上展示的不同的数字数目最多。

思路

以样例展开:

$Input$

1
2
3
4
5
4
1 2
1 3
4 2
2 3

$Output$

1
4

最开始的时候,我想的是维护一个反悔操作,使得前面选中的牌尽可能的不同。

如下图:

image-20210328170938806


  • 每一次贪心的选择第一个
  • 维护某个数字上一次出现的地方,如果出现相同的数字,就尝试修改该数字上一次出现的位置,如果能够更改就更改,如果不能更改,就考虑修改当前牌选择的数字。
  • 主要思想是保障前$i$个数不同个数最多

理论上是可以通过的,但是维护写起来比较麻烦,所以后面就没写下去了,写了队友的并查集想法。

如图所示:

image-20210328171541281

把同一张牌两面的权值,当作点的编号,进行连边。

其实题目的数据范围也暗示了这一点,保证了权值范围在$4 * 10^5$内。(当然这也不绝对,某些时候可能需要使用$map$等重编号对应的点)

这样,选择不同权值的问题,就转化成了选择某条边连接的两点中某一个的问题。

我们容易发现,这样建出来的图,每一个连通块对答案的贡献是互不影响的。

也就是说,我们只要对每一个连通块求解就行。

设当前连通块的元素个数为$size$:

  • 当目前这个连通块内不存在环,重边时,或者说当前连通块是一颗树时,对答案的贡献为$size-1$;

  • 否则,每一个点都能够被选择到,对答案的贡献为$size$;

在实现的时候,我们可以使用并查集。

若当前连边的两个元素,有共同的祖先(已经在同一连通块内),则当前连通块存在环。

我这里选择使用一个$flag$数组进行标记连通块情况。

最后,在连接完所有边后,使用一个$map$,计算对应祖先下的连通块的元素个数。

得到每个连通块的大小后,就可以根据$flag$计算对应的贡献了。

这里开始的时候我写挂了一发,最初我的$flag$是只标记了合并时发现有环的集合。在一个不为树的集合合并到一个为树的集合时,flag数组不会更新,因此$wa$了三个点。

修改后交了一发就过了。

代码

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
#include <bits/stdc++.h>
#define maxn 800005
#define int long long
using namespace std;
int n, a, b, uset[maxn], flag[maxn], vis[maxn];
map<int, int> mp;
int find(int x){
return x == uset[x] ? x : uset[x] = find(uset[x]);
}
void unioon(int x, int y){
int fx = find(x);
int fy = find(y);
if(fx == fy)
{
flag[fx] = 1;
return;
}
uset[fx] = fy;
flag[fx] = flag[fy] = (flag[fx] | flag[fy]);
}
signed main(void)
{
//freopen("1_009.txt", "r", stdin);
scanf("%lld", &n);
for(int i = 1; i <= maxn - 5; i++) uset[i] = i;
for(int i = 1; i <= n; i++)
{
scanf("%lld %lld", &a, &b);
unioon(a, b);
vis[a] = vis[b] = 1;
}
for(int i = 1; i <= maxn - 5; i++)
{
if(vis[i])
{
mp[find(i)]++;
}
}
int ans = 0;
for(map<int, int>::iterator iter = mp.begin(); iter != mp.end(); iter++)
{
if(flag[(*iter).first])
ans += (*iter).second;
else
ans += (*iter).second - 1;
}
printf("%lld\n", ans);
return 0;
}

别的

(没有思维的我是弟弟)