leetcode 周赛 497 排名44

零、背景

这次比赛最后一题有一点点难，需要枚举数组中删除某个位置后其余元素的 GCD，需要一点点小贪心才能不超时。

本场题型概览如下。
A 题：循环。
B 题：数学。
C 题：前缀和。
D 题：高级线段树。

一、统计每个顶点的度

题意：给一个无向图的邻接矩阵，问每个顶点的度数。
邻接矩阵含义：n*n的矩阵，1代表有边，0代表无边。
顶点度数含义：与某个顶点相连的边的个数

思路：循环求和即可。

二、三角形的内角度数

题意：给三条边，问是否可以组成三角形，可以的话，三个角的度数分别是多少。

思考：数学公式

首先，是否可以组成三角形可以使用两边之和是否大于第三边来判断。

而对于角的度数，则可以使用余弦定理来做。

cos(A) = (b^2 + c^2 - a^2) / (2bc);
cos(B) = (a^2 + c^2 - b^2) / (2ac);
cos(C) = (a^2 + b^2 - c^2) / (2ab);

直接使用cos的反函数 acos 求出角度，再乘以 180/PI 转化为 360 度的形式。

三、一次交换后的最长平衡子串

题意：给一个字符串，问最多选择两个字符交换后，求最长的平衡子串。
平衡子串定义：子串内 0 与 1 字符的个数相等。

思路：前缀和

第一步，先考虑不交换的情况。
显然一个前缀和即可求出每个位置为后缀的最长平衡前缀。

前缀和存储的是当前位置整个前缀 1 与 0 的个数差。
我们需要在前缀里找到个数差相等的最小下标，则这个下标到当前位置形成的子串就是一个最长平衡子串。

第二步：贪心。
假设存在两个位置交换后得到一个最长平衡子串，则显然，这两个位置不可能都在这个最长平衡子串中。
即一个字符在平衡子串中，一个不在平衡子串中。

如上图，这时候依旧可以使用前缀和来做，不过此时查找的就不是相等的 01 个数差了，而是再差两个数。

具体来说，假设当前位置的 diff = cnt[1] - cnt[0]，后边至少有一个 1。
则通过后面的 1 与前缀的 0 交换，则 diff 中少了一个 0，多了一个 1, 相当于值增加了2，即查找 diff + 2。

同理，后边至少有一个 0 时，则可以把后面的 0 与前缀的 1 交换，则 diff 中少了一个 1，多了一个 0，相当于值减少了 2，即查找 diff - 2。

就这样，就可以做这道题了。

注意事项：第二步贪心处理要计算前缀和，还需要计算后缀和。
我遗漏了，WA 了一次。
比较简洁的做法是先求答案，字符串翻转，再求答案取最大值即可。

四、好子序列查询

题意：给一个数组，定义好子序列为一个不等于原数组的非空子序列，使得子序列的 GCD 等于 P。
现在，给若干次修改，问每次修改后，是否存在这样的好子序列。

思路：线段树

显然，不是 P 的倍数的数字不可能选择，所以直接把值设置为 0。
然后构造线段树，即可求任意区间忽略 0 值的 GCD。

可以看下线段树的 PushUp 函数，大概长这样，后续我找机会介绍一下这种高级线段树。

  // 合并函数，按需进行合并
  void PushUp(int rt, int l, int r) {
    ll leftVal = gcdVal[rt << 1];
    ll rightVal = gcdVal[rt << 1 | 1];
    if (leftVal == 0) {
      gcdVal[rt] = rightVal;
    } else if (rightVal == 0) {
      gcdVal[rt] = leftVal;
    } else {
      gcdVal[rt] = __gcd(leftVal, rightVal);
    }
  }

回到这道题，首先贪心存在一个性质：选的数字越多，GCD 会越小。
这意味着，当所有数字都选择时，GCD 一定是最小的。

所以，这道题就变成了选择所有数字，GCD 是否是 P。

情况1：不是 P 显然没有答案。
情况2：是 P 了，再看选择的数字个数是否等于整个数组，不是的话，就存在答案。
情况3：选择整个数组的 GCD 为 P，此时需要判断排除某个位置后，GCD 是否仍为 P。

针对情况 3，默认情况下需要 O(n) 的时间复杂度来判断。
此时我们可以去分析，什么情况下枚举排除所有位置，都依旧没有答案。

假设排除位置 1，则剩余数字的 GCD 为 GCD(2,n)。
如果 GCD(2,n) > P，且 GCD(1,n) = P，则 nums[1] 的值不能包含 GCD(2,n)/P 的所有素因子。
同理，每个位置的值都不能包含其他位置 GCD/P 的所有素因子。

最大值是 5*10^4，素因子为 2*3*5*7*...，不超过 10 个。
假设每个位置至多不包含一个素因子，而素因子不超过 10 个，如果数字个数大于 10 个，则至少有 1 个数字是多余的。
也就是说，数组大小大于 10 时，必然存在答案。

当数组小于 10 时，暴力枚举每一个位置计算 GCD 即可。
复杂度：O(n log(n))

五、最后

这次比赛最后一题稍微有点难。
首先，涉及到高级线段树，允许有无关值，PushUp 时需要特殊判断。
其次，需要枚举所有位置时，进行贪心，小数据暴力，大数据贪心推导出肯定存在答案。
这种题目之前很少见，所以大部分都做不出来了吧。

《完》。

-EOF-

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