力扣第 393 场周赛

这场周赛是由【衍复投资】主办的，很偏数论，所以只做了两道题。

1 替换字符可以得到的最晚时间

题目描述：

给你一个字符串 s，表示一个 12 小时制的时间格式，其中一些数字（可能没有）被 "?" 替换。

12 小时制时间格式为 "HH:MM" ，其中 HH 的取值范围为 00 至 11，MM 的取值范围为 00 至 59。最早的时间为 00:00，最晚的时间为 11:59。

你需要将 s 中的 所有 "?" 字符替换为数字，使得结果字符串代表的时间是一个 有效 的 12 小时制时间，并且是可能的 最晚 时间。

返回结果字符串。

数据约束：无

解题思路：

贪心。但是有点坑。对于分钟，确实可以贪心，两位数尽可能去最大；对于小时，不能这么干了（因为这个 WA 了两发），小时的取值范围是 0~11，不能认为 11 就是最大的，有可能是 0? 的形式，在个形式下，09 才是最大的。还有一种情况是 ?3，不可以取 13，超过了可以表示的时间的范围。

所以，对于小时，我们分成以下几种情况：

• ??：可以直接取 11。
• ?1：第 2 位为 1 或者是 0。这种情况下，第 1 位可以取 1 而使其最大。
• ?2：第 2 位是 2 以上的的数，这种情况下，第 1 位只能取 0。
• 0?：第 2 位取 9。
• 1?：第 2 位取 1。
• 无 ?：取原数。

复杂度：时间复杂度 $O(1)$。

2 素数的最大距离

题目描述：

给你一个整数数组 nums。

返回两个（不一定不同的）素数在 nums 中 下标 的 最大距离。

数据约束：

数组大小 $n \leq 3 \times 10^5$；每个数值的大小 $nums_i \leq 100$。

解题思路：

• 第一步，找出 100 以内的所有素数。数据大小都在 100 以内，那么这个范围的素数暴力做法都可以做出来。
• 第二步，从左向右和从右向左找到最左边和最右边的素数。

最后结果为最右边的下标，和最左边的下标的差值。

筛素数的方法

• 埃氏筛

考虑这样一件事情：对于任意一个大于

的正整数

，那么它的

倍就是合数（

）。利用这个结论，我们可以避免很多次不必要的检测。

如果我们从小到大考虑每个数，然后同时把当前这个数的所有（比自己大的）倍数记为合数，那么运行结束的时候没有被标记的数就是素数了。

时间复杂度：$O(n \log \log n)$。

• 线性筛

vector pri;
bool not_prime[N];

void pre(int n) {
  for (int i = 2; i <= n; ++i) {
    if (!not_prime[i]) {
      pri.push_back(i);
    }
    for (int pri_j : pri) {
      if (i * pri_j > n) break;
      not_prime[i * pri_j] = true;
      if (i % pri_j == 0) {
        // i % pri_j == 0
        // 换言之，i 之前被 pri_j 筛过了
        // 由于 pri 里面质数是从小到大的，所以 i 乘上其他的质数的结果一定会被
        // pri_j 的倍数筛掉，就不需要在这里先筛一次，所以这里直接 break
        // 掉就好了
        break;
      }
    }
  }
}

时间复杂度：$O(n)$

复杂度：时间复杂度 $O(n)$，空间复杂度 $O(1)$。

3 单面值组合的第 K 小金额

题目描述：

给你一个整数数组 coins 表示不同面额的硬币，另给你一个整数 k 。

你有无限量的每种面额的硬币。但是，你 不能 组合使用不同面额的硬币。

返回使用这些硬币能制造的 第 kth 小 金额。

数据约束：

硬币种数 $type \leq 15$；硬币面值 $coins_i \leq 25$；$k$ 在 32 位整型范围内。

解题思路：

转换一下题目的描述，就是将一组数的所有的倍数去重后排序，第 $k$ 小的数是什么？

虽然当时并没有想到怎么解决，但是想到了容斥。这些数的倍数中一定是有重复的，比如 [2, 3]，倍数中 6 就重复了。如何去除掉这个重复的数呢？容斥原理就可以解决这个问题。

容斥原理

设 U 中元素有 n 种不同的属性，而第 i 种属性称为

，拥有属性

的元素构成集合

，那么
$$
\begin{aligned} \left|\bigcup_{i=1}^{n}Si\right|=&\sum{i}|Si|-\sum{i<j}|S_i\cap Sj|+\sum{i<j<k}|S_i\cap S_j\cap Sk|-\cdots\ &+(-1)^{m-1}\sum{ai<a{i+1} }\left|\bigcap{i=1}^{m}S{a_i}\right|+\cdots+(-1)^{n-1}|S_1\cap\cdots\cap Sn| \end{aligned}
$$
即
$$
\left|\bigcup{i=1}^{n}Si\right|=\sum{m=1}^n(-1)^{m-1}\sum_{ai<a{i+1} }\left|\bigcap{i=1}^mS{a_i}\right|
$$

用这些硬币，我们可以为每一个数列出它的所有倍数：
$$
a_i, 2a_i, 3a_i,\cdots
$$
那么重复的数字就是两两组合，三组合、四组合等的最小公倍数的倍数集。例如两两组合：
$$
lcm(a_i, a_j), 2lcm(a_i, a_j), 3lcm(a_i, a_j), \cdots
$$
这些数绝对在前面每个数的倍数列中重复了，需要容斥原理解决。然后就做不下去了，不知道如何求出这么多组合的最小公倍数。

忽视了数据范围，硬币种数 $type \leq 15$，故所有组合的种数就只有 $2^{15}$ 种（状态压缩），其实暴力枚举组合，求最小公倍数就好。

找到了所有的公倍数，我们就能知道一个数 $m$ 以内，有多少个公倍数出现。出现的次数 $cnt = \frac{m}{lcm}$，再通过容斥，去除掉重复的部分。这个时候，问题又转变了，找到一个最小的数，使得 $cnt_m \leq k$，这个最小的数，就是题目要要的数。此时可以二分求解了。

在 C++17 中，可以直接使用 lcm 和 gcd 求解最小公倍数以及最大公因数。C++11 可以直接 __gcd 求最大公因数，最小公因数可以 $lcm(a, b) = \frac{a \times b}{gcd(a, b)}$ 求解。

复杂度：时间复杂度 $O(\alpha 2^{t})$，空间复杂度 $O(1)$。