1002 - Dragon slayer

给一个 $n * m$ 迷宫，里面有 $k$ 堵墙，上下左右四个方向走，每次碰到一堵墙就会摧毁这堵墙。问从起点到终点最少要破坏几堵墙。

$k$ 的范围非常小，考虑二进制枚举摧毁哪些墙，然后暴力 bfs 判一下能不能到。

由于起点和终点都往右上角移了 $0.5$，边界条件需要特别注意一下。

杭电的评测机好恶心，用STL结果T了，换成数组才过

#define _GLIBCXX_DEBUG 1

#include <bits/stdc++.h>

using namespace std;

const int mxN = 30;

int n, m, k;
int sx, sy, tx, ty;
pair<pair<int, int>, pair<int, int>> walls[mxN];
int can[1 << 16];
int f[mxN][mxN];

vector<pair<int, int>> dir1 = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
vector<pair<int, int>> dir2 = {{-2, 0}, {2, 0}, {0, 2}, {0, -2}};

bool Bfs(int mask) {
  memset(f, 0, sizeof f);
  for (int i = 0; i < k; i++) {
    if (!(mask >> i & 1)) {
      auto &wall = walls[i];
      auto p = wall.first, q = wall.second;
      assert(p <= q);
      for (int x = p.first; x <= q.first; x++) {
        for (int y = p.second; y <= q.second; y++) {
          f[x][y] = 2;
        }
      }
    }
  }
  for (int i = 0; i < n; i++) {
    f[i][0] = f[i][m - 1] = 2;
  }
  for (int i = 0; i < m; i++) {
    f[0][i] = f[n - 1][i] = 2;
  }
  vector<pair<int, int>> que;
  que.emplace_back(sx, sy);
  for (int i = 0; i < (int) que.size(); i++) {
    auto &v = que[i];
    int x = v.first, y = v.second;
    if (x == tx && y == ty) {
      return true;
    }
    for (int i = 0; i < 4; i++) {
      int x1 = x + dir1[i].first, y1 = y + dir1[i].second;
      int x2 = x + dir2[i].first, y2 = y + dir2[i].second;
      if (x1 < 0 || x1 >= n || y1 < 0 || y1 >= m) continue;
      if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m) continue;          
      if (f[x1][y1] == 2 || f[x2][y2] == 1) continue;
      que.emplace_back(x2, y2);
      f[x2][y2] = 1;
    }
  }
  return false;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    cin >> n >> m >> k;
    cin >> sx >> sy >> tx >> ty;
    n *= 2, m *= 2;
    n++; m++;
    sx *= 2, sy *= 2, tx *= 2, ty *= 2;
    sx++; sy++; tx++; ty++;  
    for (int i = 0; i < k; i++) {
      int a, b, c, d;
      cin >> a >> b >> c >> d;
      a *= 2, b *= 2, c *= 2, d *= 2;
      pair<int, int> p = {a, b}, q = {c, d};
      if (p > q) {
        swap(p, q);
      }
      walls[i] = {p, q};
    }
    int ans = 123;
    memset(can, 0, sizeof can);
    for (int mask = 0; mask < (1 << k); mask++) {
      if (can[mask]) {
      // continue;
      }
      if (Bfs(mask)) {
        for (int i = 0; i < k; i++) {
          can[mask | (1 << i)] |= 1;
        }
        ans = min(ans, __builtin_popcount(mask));
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

1009 - Backpack

给定 $n$ 个物品和体积为 $m$ 的背包，物品有体积和价值。要求选择若干个物品恰好填满背包，并且使得物品价值的异或和最大。

这题在考虑 $dp$ 的时候，不能把 xor 的值作为 $dp$ 的结果来转移，因为异或不满足最优子结构。也就是不能有$dp[某状态]=某异或值$。所以考虑把异或加入到维度里。
$$dp(i, j, k) := 在前 i 个物品里选，xor为j，体积恰好为k的情况是否存在 \\ 易得\\ dp(i, j, k) = dp(i - 1, j, k) \lor dp(i - 1, j\oplus w, k - v)$$
答案是：找到最大的异或值且 $dp(n, 异或值, m) == true$

如果直接转移的话显然是 $n^3$ 的。

for (i)
  for (j)
    for (k)
      dp[i][j][k] = dp[i - 1][j][k] | dp[i - 1][j ^ w[i]][k - v[i]]

观察这个 dp 的结果，全部都是 0 或者 1，也就是 $dp(i, j)$ 的值按照 $k$ 的顺序排起来是一个二进制串。考虑用 bitset 把 k 这一维压进去，原本的减法相当于左移。$i$ 这一维显然也可以压掉，滚动数组或者啥的。

#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int tt;
  cin >> tt;
  while (tt--) {
    int n, m;
    cin >> n >> m;
    vector<int> v(n), w(n);
    for (int i = 0; i < n; i++) {
      cin >> v[i] >> w[i];
    }
    const int B = 1024;
    vector<bitset<B>> dp(B + 1, bitset<B>());
    dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
      auto new_dp = dp;
      for (int j = 0; j < B; j++) {
        new_dp[j] |= dp[j ^ w[i]] << v[i];
      }
      swap(dp, new_dp);
    }
    int ans = -1;
    for (int i = B; i >= 0; i--) {
      if (dp[i][m]) {
        ans = i;
        break;
      }
    }
    cout << ans << '\n';
  }
  return 0;
}