Meet in the middle - P2962

超级玛丽王子 · 2021-08-27 13:53:37 · 题解

“折半”搜索好题。

请注意，这不是二分！

Stop learning useless algorithms, LEARN BINARY SEARCH

Meet in the middle 搜索方法，中文译作“折半搜索”，是一种用来优化暴力搜索的方法。其思想类似归并排序，将搜索空间分成两半，分别搜索后再按一定方式合并。

对于本题，可以发现每个点最多进行一次操作（否则就变回去了没有意义），考虑对每个点的操作状态压到一个 long long 里。之后暴力搜索所有状态的复杂度是 O(2^n)。使用 Meet int the middle 可以优化到 O(2^{\frac n 2}n)。具体方法是先暴搜 1 到 mid 的所有开关，再暴搜后面的两个部分。如果两个部分搜到的结果刚好能点亮所有的灯，就得到一个可行解。最后找到最优解即可。

实际实现比较复杂，需要用到 map 和位运算。具体见下：

#include <bits/stdc++.h>
using namespace std;

int n, m, ans = 0x7fffffff;
map<long long, int> f;
long long a[40];

int main(void) {
  ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
  cin >> n >> m;
  a[0] = 1;
  for (int i = 1; i < n; ++i) a[i] = a[i - 1] << 1; //预处理每个点都能影响到自己

  for (int i = 1; i <= m; ++i) {
    int u, v;
    cin >> u >> v;
    --u,--v; //与二进制位匹配
    a[u] |= (1ll << v),a[v] |= (1ll << u); //压位记录每个点操作影响到的点
  }

  for (int i = 0; i < (1 << (n >> 1)); ++i) {  //前半段
    long long t = 0;  //状态压缩
    int cnt = 0;
    for (int j = 0; j < (n >> 1); ++j) {
      if ((i >> j) & 1) {
        t ^= a[j];
        ++cnt;
      }
    }
    if (!f.count(t))  //前半段记录在 map 里
      f[t] = cnt;
    else
      f[t] = min(f[t], cnt);
  }

  for (int i = 0; i < (1 << (n - (n >> 1))); ++i) {  //后半段
    long long t = 0;
    int cnt = 0;
    for (int j = 0; j < (n - (n >> 1)); ++j) {
      if ((i >> j) & 1) {
        t ^= a[(n >> 1) + j];
        ++cnt;
      }
    }
    if (f.count((((long long)1 << n) - 1) ^ t))  //后半段与前半段匹配
      ans = min(ans, cnt + f[(((long long)1 << n) - 1) ^ t]);
  }
  cout << ans;
  return 0;
}

（代码修改自 OI-wiki 提供的参考代码）