leetcode 周赛 495

零、背景

这次比赛最后一题稍微有点难度，可以想到使用并查集，但是还需要判断路径和的奇偶性。
使用到根的路径和的异或，恰好可以完美解决这个问题。

本场题型概览如下。
A 题：循环。
B 题：map。
C 题：枚举。
D 题：带权并查集。

一、双端字符匹配

题意：给一个数组，找到最小的下标 i，满足下标 i 的值与下标 n-1-i 的值相等。

思路：按题意循环判断即可。

二、设计事件管理器

题意：交互题，给你一些事件的 ID 和优先级，有两个操作。
1）更新指定事件的优先级。
2）返回优先级最高的最小事件 ID。

思路：map 的使用

首先题意有一个活跃事件的概念，这个硬控了我 10 分钟，反复读题，最终确认不需要关心活跃事件的概念。

对于操作二，需要 map<priority,set<eventID>> 就可以搞定。
对于操作一，需要建立反向索引 map<eventID, priority>。

这里可以先封装一个删除操作。

void RemoveEvent(int eventId) {
  if (eventPriority.find(eventId) != eventPriority.end()) {
    int priority = eventPriority[eventId];
    mp[priority].erase(eventId);
    if (mp[priority].empty()) {
      mp.erase(priority);
    }
    eventPriority.erase(eventId);
  }
}

对于操作二，在 map 中找到最后一个优先级，然后在 set 中找到第一个事件 ID。
然后删除这个事件即可。

对于操作一，先删除事件 ID，再插入事件 ID 即可。

三、可排序整数求和

题意：给一个长度为 n 的数组，问是否可以将数组分割为长度为 n 的某个因子的小数组，小数组内可以循环移动，从而使得数组有序。

思路：枚举

一个数字的因子个数不超过 log(n) 个。
故可以先计算出所有的因子，然后枚举判断因子是否是答案。

计算一个数字的所有因子，直接暴力循环判断即可。
复杂度：O(n)
当然，也可以折半判断，复杂度降低半个数量级 O(sqrt(n))

std::vector<int> factors;
void CalFactor(int N) {
  factors.clear();
  for (int i = 1; i * i <= N; i++) {
    if (N % i == 0) {
      int j = N / i;
      factors.push_back(i);
      if (i != j) {
        factors.push_back(j);
      }
    }
  }
}

有了子数组的长度，接下来就是循环判断每个子数组是否符合要求。

假设一个子数组可以循环移动达到有序，则这个子数组要么是有序的，要么是两个非递减数组拼接而成。

我们可以从右向左找到这样一个下降的分界点。
然后从这个分界点开始，与最终有序的数组进行比较即可。

四、增量偶权环查询

题意：给 n 个顶点，若干带权的无向边一条条地加入图中，如果加入后形成的环的边权和是偶数，则可以加入图中。
问最终加入图中的边的个数。

思路：带权并查集

通过并查集可以快速判断两个点是否是连通的。
增加一个边权，也可以快速计算出每个点到连通分量根节点路径的边权和。

第一个问题是怎么判断两个点的路径边权和的奇偶性呢？
这就需要利用神奇的异或性质了。

如上图，我们知道前缀 u+pre 的值，也有前缀 v+pre 的值，要求 u+v 的值的奇偶性。
由于只关心奇偶性，所以所有值都可以简化为 0 或 1。

问题就转化为了知道前缀 u^pre 的值，也知道前缀 v^pre 的值，求 u^v 的值。
显而易见，两个前缀的值直接异或即可得到路径边权和的奇偶性。

第二个问题，两个点原先不连通，如何处理变为连通呢？
或者问题转化为，一个连通分量的根节点指向了另一个连通分量的根节点，这两个根节点之间的权重是设置为奇数还是偶数呢？

还是看图，我们知道前缀 preX 的值，也有前缀 preY 的值，现在 x 和 y 之间的边权值是 w，问两个根节点的权值设置为多少？
显然，加入边之后，x 和 y 的路径边权和的奇偶性需要是 w。

根据第一个问题的结论，需要满足 preX ^ preY ^ ? = w。
两边都异或上 preX ^ preY，就可以知道 ? = w ^ preX ^ preY。
故，两个不同的连通分量相连时，边权需要设置为 w ^ preX ^ preY。

由于存在路径压缩，可以理解为复杂度为 O(m)。

五、最后

这次比赛最后一题涉及到并查集结合异或，稍微有点难度。
不过题目已经点明奇偶性了，也很容易想到肯定是异或，所以只剩下推导出谁和谁异或即可。

《完》。

-EOF-

本文公众号：天空的代码世界 个人微信号：tiankonguse 公众号 ID：tiankonguse-code