【7.5】Codeforces 刷题

${}^{\ast }1700{,}^{\ast }1800{,}^{\ast }1900$

---

D. Harmonious Graph

题意：定义一张无向图是和谐的当且仅当：假设图中存在一条从 $l$ 到 $r$ （$l<r$）的路径，则图中也存在从 $l$ 到 $l+1,l+2,\cdots ,r-1$ 的路径。

给出一张无向图，求至少需要添加多少条边才能将其变为和谐的。

$3\le n\le 200000$ and $1\le m\le 200000$

题解：
Harmonious Graph(并查集)

• 思路：

自己的思路是，把边当作区间，进行一个区间合并，合并为若干个区间。在每个区间中，进行并查集的联通维护，看看有几个联通块，连起来即可。

题解的思路是：在输入边的同时维护一个从左指向右（即指向集合内最大数）的并查集，然后指针右移枚举区间内的数，如果枚举数所在集合的最大数不等于当前集合的最大数，即不在同一个集合内，那么连一条边保证连通，并更新右边界。

指向为右的并查集的目的是使集合内的元素指向唯一，方便描述区间边界。

AC代码：https://codeforces.com/contest/1253/submission/162855449
https://codeforces.com/contest/1253/submission/162856918

---

B. Stoned Game

• 题意：

有n堆石子，每堆分别有$a_i$个石子。

两者轮流取其中一个石子。但不能取上次对手取过的那一堆。特殊的，第一次取可以取任何一堆的石子。

当前先手取完要取的石子之后使对手无路可走时，先手获胜。

t (t <= 100) 组数据，每组数据给出n (n <= 100) 和a (a <= 100) ，输出谁必会胜利。若先手胜利输出“T”，若后者胜利输出“HL”。无引号。

• 题解：https://www.luogu.com.cn/problem/solution/CF1396B

• 思路：首先分析一个先手必胜态：存在某一堆大于其他堆的总和，这样的话只要先手锁定最大堆即可。否则，我们发现，每个人只会拿一个，因为先手选择了最大堆，如果后手只拿一个，差值不会变；否则，差值会变大，容易导致先手胜。这样考虑所有的奇偶性即可。

• AC代码：https://codeforces.com/contest/1396/submission/162858606

---

C. Longest Regular Bracket Sequence

• 题意：给出一个括号序列（$n\le 10^6$），求出最长合法 括号子串 和它的数量。 合法的定义：这个序列中左右括号匹配

• 题解：题解 CF5C 【Longest Regular Bracket Sequence】

• 思路：题解给出了一个巧妙地线性解法。我们用栈来匹配括号，匹配到的两个括号打上标记。关注标记中的 1 连通块，因为如果两个括号匹配上了，那中间的一段必然已经匹配好并出栈，不然这两个括号不会匹配。然后找最长的 1 连通块即可。

• AC代码：https://codeforces.com/contest/5/submission/162862333