leetcode 周赛 483 - 状态压缩

零、背景

这次比赛在元旦假期后的调休日举行，那天我休假还在重庆，所以就没有参加比赛。

本场四道题的大致思路如下：

A 题：贪心
B 题：枚举
C 题：贪心
D 题：状压 DP

下面按题号依次简单记录一下解题思路。

最终排名：无
代码仓库：https://github.com/tiankonguse/leetcode-solutions

一、最大的偶数

题意：给一个数字字符串，问怎么删除才能得到最大的偶数。

思路：贪心，从后到前依次删除末尾的奇数，直到遇到第一个偶数为止；因为我们只删后缀，不改变前缀，相当于在所有以偶数结尾的前缀中保留最长的那个，自然就是最大的偶数。

二、单词方块 II

题意：给 n 个长度相等且互不相同的字符串，求 4 个字符串，使得它们上下左右可以组成一个正方形，按字典序输出所有满足要求的组合。
4 个字符串的位置约定为：第一个为从左到右的 top，第二个为从上到下的 left，第三个为从上到下的 right，第四个为从左到右的 bottom，四个交点为四个顶点。

思路：枚举。

n 不大，可以直接用 n^4 枚举所有 4 元组组合，判断在四个顶点处字符是否两两一致、行列是否完全匹配，筛出合法解后再按字典序排序输出即可。

三、使二进制字符串相等的最小成本

题意：给两个二进制字符串，有三种操作，求使两个字符串相等的最小成本。

操作 1：选择任意一个字符串的任意位置，翻转该位置的值。
操作 2：选择任意一个字符串的任意两个不同位置，交换这两个位置的值。
操作 3：选择任意一个位置，交换两个字符串该位置的值。

思路：贪心。

可以发现，这些操作并不关心具体是哪些下标，只关心两串在对应位置上的值是否相同，所以可以只对“对应位置值不同”的情况进行统计。
共分两种情况：第一个字符串值是 1、第二个字符串值是 0，或者第一个字符串值是 0、第二个字符串值是 1，分别记作 v01 和 v10。

如果操作 2 的成本比两次操作 1 更低，就优先用操作 2 在同一条字符串上成对消掉差异，此时 v01 和 v10 中会有一种被消成 0，另一种可能还有剩余。
接着可以考虑先做一次操作 3，把两串某个位置的值对调，再配合操作 2 一起使用，在某些情况下依旧比直接做两次操作 1 更划算。

最后，如果 v01 和 v10 还有剩余，那么就只能用操作 1 分别单点翻转，把剩下的所有差异消掉。
整体上就是优先用成本更低的操作 2 和操作 3 配对消差，剩余的零散差异再用操作 1 收尾。

四、合并有序列表的最小成本

题意：给若干一维数组，每次可以选择两个一维数组进行合并，求将所有数组合并成一个数组的最小成本。
合并成本定义为：两个数组长度之和，加上两个数组中位数的差的绝对值。

思路：状态压缩 DP。

从最后一步往前倒推：最后一次合并时，参与合并的两个一维数组，都可能已经是“若干个原始数组先合并好的结果”，合并顺序对最终结果已经不重要。
这相当于有两个集合，每个集合包含若干个原始数组，每次合并两个集合，合并成本为两个集合里元素总个数之和，加上两个集合中位数的差的绝对值。
由于不知道怎样分组、怎样合并顺序才最优，只能枚举所有可能的划分方式，求出其中的最小成本。

把“一个集合由哪些原始数组组成”压缩成一个二进制状态：每个原始数组对应二进制的一位，该位为 1 表示在集合中，这样集合的大小就是二进制中 1 的个数。
对每个非空状态 mask，设 costs[mask] 表示把 mask 中所有数组合并成一个数组的最小成本，转移时枚举它的一个非空真子集 sub，令 other = mask ^ sub，那么可以从 sub 和 other 已经各自合并好的状态转移过来。

ll minMergeCost(vector<vector<int>>& lists_) {
  Init(lists_);
  return Dfs(M - 1);
}
ll Dfs(int mask) {
  ll& ret = costs[mask];
  if (ret != INT64_MAX) {
    return ret;
  }
  if ((mask & (mask - 1)) == 0) {
    return ret = 0;  // 1个，不需要合并
  }
  // 枚举所有子集
  for (int sub = (mask - 1) & mask; sub > (sub ^ mask); sub = (sub - 1) & mask) {
    int other = mask ^ sub;
    ret = min(ret, Dfs(sub) + Dfs(other) + lens[sub] + lens[other] + abs(Median(sub) - Median(other)));
  }
  return ret;
}

接下来就是如何高效求一个集合（状态）的中位数。
直接把集合里的所有数字合并、排序再取中位数太慢，只能通过值域二分来做。
具体做法是：先对所有一维数组分别排序，二分一个候选值 mid，统计集合里所有数组中小于等于 mid 的元素个数，根据个数与目标中位数位置的大小关系调整二分区间。

复杂度大致为 O(2^n * log V * log N)：状态数是 2^n，每个状态要通过值域二分查找中位数，再在所有相关数组里做二分统计。

ll Median(int mask) {  //
  ll& ret = medians[mask];
  if (ret != INT64_MAX) {
    return ret;
  }
  vector<int> ps;
  for (int i = 0; i < n; i++) {
    if (mask & (1 << i)) {
      ps.push_back(i);
    }
  }
  ll midCnt = (lens[mask] + 1) / 2;
  ll l = minVal, r = maxVal + 1;
  while (l < r) {
    ll len = r - l + 1;
    ll mid = l + (len - 1) / 2;
    ll cnt = 0;
    for (int i : ps) {
      cnt += upper_bound(lists[i].begin(), lists[i].end(), mid) - lists[i].begin();
    }
    if (cnt < midCnt) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return ret = l + 1;
}

五、最后

这次比赛最后一题的实现细节稍微多一些，但整体思路还是比较清晰的：先把“怎么划分集合”这个组合结构用状态压缩描述出来，再配上中位数的值域二分。
当元素个数不大（比如不超过 20）时，遇到这种“枚举所有子集 / 划分”的问题，很值得优先考虑用状态压缩 DP 来尝试建模。

《完》

-EOF-

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