折半搜索¶

前言¶

折半搜索并不是一个标准的译名，这种算法原名叫「Meet in the middle」，常见的译名有：折半搜索、中途相遇和双向搜索。

算法介绍¶

例题

给定一个 \(n\times n\) 的矩阵，你最开始在 \((1,1)\)，每次你都只能往下面或者右边走。问你有多少种走法使得经过的数他们的异或值正好为 \(0\)。\(1\le n\le 40\)

这题是方案数的题目，因此我们使用 dfs 来解决。设 \(f(x,y,s)\) 表示为当前搜到了 \((x,y)\)，异或值为 \(s\)。那么对于任意一个格子，可以往下面或者右边，递归解决即可。

代码

void dfs(int x, int y, int s) {
  if (x == n && y == m) {
    ans += !s;
    return;
  }
  dfs(x + 1, y, s ^ a[x + 1][y]);
  dfs(x, y + 1, s ^ a[x][y + 1]);
}

但是，这题 \(1\le n\le 40\)，而每一个状态有两种决策，那么我们的复杂度就达到了 \(\mathcal O(2^n)\)，无法承受。要是假如 \(n\) 只有一半，也就是 \(20\)，那该多好啊。

仔细思考一下，我们就发现了我们可以从前面和后面各搜索一次，然后在对角线相遇记录答案，那么 \(n\) 不久砍了一半了吗？因为 \(x\oplus x=0\)，因此我们可以用 std::unordered_map 记录答案，然后在往回搜索记录答案的时候加上过来的时候同样为 \(x\) 的数量就行了。

代码

#include <iostream>
#include <unordered_map>

using namespace std;
using ll = long long;

const ll kMaxN = 25;

ll a[kMaxN][kMaxN], n, ans;
unordered_map<ll, ll> f[kMaxN][kMaxN];

void dfs(ll x, ll y, ll s, bool b) {
  if (x + y == n) {
    b ? ans += f[x][y][s ^ a[x][y]] : f[x][y][s]++;
    return;
  }
  dfs(x + (b ? -1 : 1), y, s ^ a[x + (b ? -1 : 1)][y], b);
  dfs(x, y + (b ? -1 : 1), s ^ a[x][y + (b ? -1 : 1)], b);
}

int main() {
  cin >> n;
  for (ll i = 1; i <= n; i++) {
    for (ll j = 1; j <= n; j++) {
      cin >> a[i][j];
    }
  }
  dfs(1, 1, a[1][1], 0);
  dfs(n, n, a[n][n], 1);
  cout << ans << '\n';
  return 0;
}

这就是折半搜索的魅力。

折半搜索¶

前言¶

算法介绍¶

评论