基础数据结构

习题1

考点：multiset / deque + 排序

总结：

  1. 在使用set时要注意数据是否有重复
  2. 有重复只能用multiset，或者用pair区分

题解：UVA11136 Hoax or what_牛客博客 (nowcoder.net)

习题2

考点：带权并查集 + 异或次数得奇偶性 + 虚根建立

总结：

  1. 一个数异或另一个数偶数次则等于这个数本身，异或奇数次等于异或上另一个数
  2. 一个数异或上0是他本身
  3. 维护的是边的异或值

题解：UVALive4487 Exclusive-OR_牛客博客 (nowcoder.net)

习题3

考点：用带拓展域的并查集维护可删除并查集

总结：

  1. 真正的集合的代表元素不是集合中的某个元素而是一个编号
  2. 删除一个并查集中的某个元素就将他的根节点改变即可（这样不会影响其他元素的根节点）

题解：UVA11987 Almost Union-Find_牛客博客 (nowcoder.net)