P6176 [USACO16JAN] Lights Out P

简要题意: 按顺时针顺序给你 $n$ 个点，围成一个 $n$ 边形，每条边都和坐标轴平行。Bessie 从点 $p$ 出发要沿着边到达点 $1$，她不知道自己在哪个点，但是她可以判断当前位置是不是点 $1$。她可以按照某一策略走，并记录下所经过的每条边的长度以及转向的角度，且可以根据已知信息进行下一步的决策（决策指走哪个方向）。求一个最优的策略，使得在最坏情况下，Bessie 相较于 $p$ 到 $1$ 的最短路径所多走的距离最小，输出这个最坏情况下的最小距离。

数据规模: $n \le 200$。

题解: 首先解决第一个问题，即如何记录已知信息。容易发现可以将多边形转化为一个长度为 $2n$ 的序列，每个元素为边的长度或转角的度数，交替出现。已知的信息一定是该序列的一个子串，数量是 $O(n^2)$ 级别的。设这个序列为 $s$，长度为 $m$。

考虑 dp，设 $dp[l][r][p][0/1]$ 表示已知的信息为 $s[l\cdots r]$，且起始点在已知信息串的第 $p$ 个，最终停在了 $l$ 还是 $r$，此时的最小距离。但是现在可能有多组形如 $[l_1,r_1]$ 和 $[l_2,r_2]$ 的信息串，其中 $s[l_1 \cdots r_1] = s[l_2 \cdots r_2]$，根据题意我们无法根据已知信息区分出这两个串。所以假设 $l_1 < l_2$，我们只记录 $dp[l_1][r_1]$ 的值，将所有 $dp[l_2][r_2]$ 的转移挂到 $dp[l_1][r_1]$ 上面去。我们称 $(l_1,r_1)$ 为 $(l_2,r_2)$ 的代表串。

考虑这个 dp 如何转移，不难发现决策只有 $2$ 种，即向左走或向右走。对于每个 $(l,r)$ 的信息串，我们记录 $lpre_{l,r}$ 表示向左拓展一格可能到达的代表串，$rpre_{l,r}$ 同理表示向右拓展。那么向左走的代价就是 $\max dp[lpre]$，向右走就是 $\max dp[rpre]$，两者取 $\min$ 得到 $dp[l][r]$ 的答案。

至于最终的答案，就是所有 $dp[i][i][1][0/1]$ 的最坏情况（即最大值）。于是本题在 $O(n^3)$ 的时间复杂度内被解决。

代码:

C++

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
using ll = long long;
const int N = 210, M = 420, I = 1e9 + 10;
int n, m, id[N], dis[N], prf[N], str[M], pos[M], fir[M][M], dp[M][M][M][2];
vector<int> lpre[M][M], rpre[M][M];
inline int sgn(ll x) { return x > 0 ? -1 : -2; }
inline int pre(int x) { return x == 1 ? n : x - 1; }
inline int nxt(int x) { return x == n ? 1 : x + 1; }
struct Point {
  int x, y;
  Point operator-(const Point &p) const { return {x - p.x, y - p.y}; }
  ll operator*(const Point &p) const { return 1ll * x * p.y - 1ll * y * p.x; }
} pt[N];
bool m_ed;
signed main() {
  read(n);
  for (int i = 1; i <= n; ++i)
    read(pt[i].x), read(pt[i].y);
  for (int i = 1; i <= n; ++i) {
    int p1 = pre(i), p2 = nxt(i);
    str[++m] = sgn((pt[p2] - pt[i]) * (pt[i] - pt[p1]));
    str[++m] = abs(pt[p2].x - pt[i].x) + abs(pt[p2].y - pt[i].y);
    id[i] = m - 1, pos[m - 1] = i, prf[i + 1] += str[m], prf[i] += prf[i - 1];
  }
  str[1] = str[++m] = 0, id[n + 1] = m, pos[m] = n + 1, prf[n + 1] += prf[n];
  for (int i = 1; i <= n; ++i)
    dis[i] = min(prf[i], prf[n + 1] - prf[i]);
  for (int ln = 1; ln <= m; ++ln)
    for (int l = 1, r = ln; r <= m; ++l, ++r) {
      for (int i = 1; i < l; ++i) {
        if (str[r] != str[i + ln - 1])
          continue;
        if (fir[l][r - 1] != fir[i][i + ln - 2])
          continue;
        fir[l][r] = i;
        break;
      }
      if (!fir[l][r])
        fir[l][r] = l;
    }
  for (int ln = 3; ln <= m; ln += 2)
    for (int l = 1, r = ln; r <= m; l += 2, r += 2) {
      if (fir[l][r] != l)
        continue;
      lpre[pos[fir[l + 2][r]]][pos[fir[l + 2][r] + ln - 3]].push_back(pos[l]);
      rpre[pos[fir[l][r - 2]]][pos[fir[l][r - 2] + ln - 3]].push_back(pos[r]);
    }
  int ans = 0;
  for (int ln = n + 1; ln >= 1; --ln)
    for (int l = 1, r = ln; r <= n + 1; ++l, ++r) {
      if (fir[id[l]][id[r]] != id[l])
        continue;
      int ndis = prf[r] - prf[l];
      for (int s = 1; s <= ln; ++s)
        for (int x = 0; x < 2; ++x) {
          if (l == 1 || r == n + 1) {
            dp[l][r][s][x] = -dis[l + s - 1];
            continue;
          }
          int lcost = -I, rcost = -I;
          for (int p : lpre[l][r]) {
            int pl = p, pr = p + ln, ps = s + 1;
            lcost = max(lcost, dp[pl][pr][ps][0] + str[id[pl] + 1]);
          }
          for (int p : rpre[l][r]) {
            int pr = p, pl = p - ln, ps = s;
            rcost = max(rcost, dp[pl][pr][ps][1] + str[id[pr] - 1]);
          }
          (x ? lcost : rcost) += ndis;
          dp[l][r][s][x] = min(lcost, rcost);
          if (ln == 1)
            ans = max(ans, dp[l][r][s][x]);
        }
    }
  return write(ans), putchar('\n'), 0;
}

P3148 [USACO16OPEN] Bull in a China Shop P

简要题意: 问 $k$ 个小碎片中任取 $3$ 个拼成目标碎片的方案数，碎片的大小为 $n\times m$。

数据规模: $n,m \le 500,\ k \le 100$。

题解: $k$ 非常小，暴力的做法是枚举 $3$ 个碎片以及所有的 $8$ 种置换（旋转以及翻转），并枚举每个碎片的位置，用 hash 判断是否能组成目标碎片，$O((8knm)^3)$，期望得分 $0$。

注意到，可以先找到目标碎片最右下角的未覆盖位置，进而确定放在这里的碎片以及其坐标的偏移量。这样就不需要对每个碎片都枚举位置了，优化到 $O((8k)^3nm)$，期望得分 $0$。

算法的瓶颈在于求得目标碎片在覆盖了若干个碎片后的最右下的未覆盖位置。考虑对于每个碎片，令 $a[i][j]$ 表示碎片的 $(i,j)$ 位置是否有值，对 $a$ 数组按照 $a[1][1]\cdots,a[1][m],a[2][1],\cdots,a[n][m]$ 的顺序求后缀和，称这个后缀和数组为 $sum$。显然此时最右下的未覆盖位置就是最后一个 $sum[i][j] = 1$ 的位置。进而可以用目标碎片的 $sum$ 数组减去若干已确定碎片的后缀和，得到剩余碎片的后缀和，二分 $(i,j)$ 的位置加以判断，做到 $O(\log (nm))$ 地求出最右下角的未覆盖位置。至此算法被优化至 $O((8k)^3 \log (nm))$，期望得分 $0$。

继续优化此算法。注意到我们其实不需要枚举所有的 $3$ 个碎片，只需知道前 $2$ 个碎片就可以通过与目标碎片做差的方式得到第 $3$ 个碎片的 hash 值，再用一个 unordered_map 储存 hash 值对应的碎片编号，就可以判断是否有合法的第 $3$ 个碎片。至此算法被优化至 $O((8k)^2\log(nm))$，期望得分 $100$。

代码的实现较为复杂，我将给出一个加了很多注释的格式化后的代码。

代码: ~~（今天，我要写 Bull in a China Shop! :smiley::thumbsup:）~~

C++

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
/**
 * @file:           P3148.cpp
 * @author:         yaoxi-std
 * @url:            https://www.luogu.com.cn/problem/P3148
 */
#include <bits/stdc++.h>
using namespace std;

/*** 结构体别名定义 ***/

/* 无符号长整形（哈希用） */
using ull = unsigned long long;

/* 碎片信息 */
using piece = vector<string>;

/* 碎片覆盖信息前缀和 */
using sum_table = vector<vector<int>>;

/*** 常量定义部分 ***/

/* 碎片矩阵最大值 */
/* 由于可能需要加偏移量，所以开 2 倍 */
const int N = 1010;

/*** 哈希部分 ***/

/* 哈希种子 */
const ull hash_seed = 13131;

/* 哈希种子的幂次 */
ull seed_pow[N * N];

/* 哈希常量信息预处理 */
void init_hash() {
  if (seed_pow[0])
    return;
  for (int i = seed_pow[0] = 1; i < N * N; ++i)
    seed_pow[i] = seed_pow[i - 1] * hash_seed;
}

/* 哈希结构体 */
struct xhash {
  /* 哈希值 */
  ull value;

  xhash() {
    init_hash();
    value = 0;
  }

  xhash(const piece &p) {
    init_hash();
    value = 0;

    int n = p.size(), m = p[0].size();
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < m; ++j) {
        if (p[i][j] == '.')
          continue;
        value += seed_pow[i * N + j] * p[i][j];
      }
  }

  /* 对哈希值增加偏移量 */
  void offset(int r, int c) { value *= seed_pow[r * N + c]; }

  /* 减法，去除已匹配部分的哈希值 */
  xhash operator-(const xhash &rhs) const {
    xhash res;
    res.value = value - rhs.value;
    return res;
  }

  /* 判断哈希值的是否相等 */
  bool operator==(const xhash &rhs) const { return value == rhs.value; }
};

/* 用于 unordered_map 的伪函数定义 */
struct xhash_downhash {
  ull operator()(const xhash &h) const { return h.value; }
};

/*** 全局变量定义部分 ***/

/* 碎片总数 */
int k;
/* 目标碎片信息 */
piece target_piece;
/* 目标碎片哈希值 */
xhash target_hash;
/* 目标碎片前缀和信息 */
sum_table target_sums;
/* 残余碎片信息，无重复储存 */
map<piece, int> piece_map;
/* 同类型碎片的编号 */
vector<int> piece_index;
/* 同类型碎片数量 */
vector<int> piece_counts;
/* 同类型碎片本身最右下的有效位置的偏移量 */
vector<pair<int, int>> piece_offsets;
/* 同类型碎片的哈希值 */
vector<xhash> piece_hashes;
/* 同类型碎片的前缀和信息 */
vector<sum_table> piece_sums;
/* 哈希值对应的碎片编号，用于匹配 */
unordered_map<xhash, int, xhash_downhash> hash_index;

/*** 碎片的变换方式处理 ***/

/* 将碎片按照竖直方向翻转 */
void vflip(piece &p) {
  int n = p.size();
  for (int i = 0; i < n - i - 1; ++i)
    p[i].swap(p[n - i - 1]);
}

/* 将碎片顺时针旋转 90 度 */
void rotate(piece &p) {
  int n = p.size(), m = p[0].size();
  piece res(m, string(n, '.'));
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      res[m - j - 1][i] = p[i][j];
  p.swap(res);
}

/*** 读入/输出部分 ***/

/* 读入碎片信息 */
piece read_piece() {
  int n, m;
  cin >> n >> m;
  piece p(n, string(m, '.'));
  for (int i = 0; i < n; ++i)
    cin >> p[i];

  /* 对碎片信息进行处理，去除周围空白的行和列 */
  int mnx = n, mxx = 0;
  int mny = m, mxy = 0;
  piece result;
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j) {
      if (p[i][j] == '.')
        continue;
      mnx = min(mnx, i);
      mxx = max(mxx, i);
      mny = min(mny, j);
      mxy = max(mxy, j);
    }
  for (int i = mnx; i <= mxx; ++i)
    result.push_back(p[i].substr(mny, mxy - mny + 1));

  /* 找到几种自身变换方式中字典序最小的去重 */
  p = result;
  for (int i = 0; i < 2; ++i) {
    for (int j = 0; j < 4; ++j) {
      if (p < result)
        result = p;
      rotate(p);
    }
    vflip(p);
  }

  return result;
}

/* 输出碎片信息 */
void print_piece(const piece &p) {
  int n = p.size(), m = p[0].size();
  cout << "--- Begin of piece info ---\n";
  cout << "piece info (n = " << n << ", m = " << m << "):\n";
  for (int i = 0; i < n; ++i)
    cout << p[i] << "\n";
  cout << "---- End of piece info ----\n";
}

/*** 碎片前缀和信息处理部分 ***/

/* 计算前缀和信息，由原始碎片信息得到 */
sum_table calc_sums(const piece &p) {
  int n = p.size(), m = p[0].size();
  sum_table sums(n, vector<int>(m));
  int prf_cnt = 0;
  for (int i = n - 1; ~i; --i)
    for (int j = m - 1; ~j; --j) {
      if (p[i][j] != '.')
        ++prf_cnt;
      sums[i][j] = prf_cnt;
    }
  return sums;
}

/* 由前缀和信息，二分地快速得到最右下角的空位置 */
/*  - base:         基准前缀和的信息       */
/*  - used_ids:     已覆盖碎片的编号       */
/*  - used_offsets: 已覆盖碎片偏移量       */
pair<int, int> find_offset(const sum_table &base,
                           const vector<int> &used_ids = {},
                           const vector<pair<int, int>> &used_offsets = {}) {
  int n = base.size(), m = base[0].size();
  int hd = 0, tl = n * m - 1, res = 0;
  while (hd <= tl) {
    int mid = (hd + tl) >> 1;
    int r = mid / m, c = mid % m;
    int val = base[r][c];
    for (int i = 0; i < (int)used_ids.size(); ++i) {
      int j = used_ids[i];
      int tr = r - used_offsets[i].first;
      int tc = c - used_offsets[i].second;
      int pn = piece_sums[j].size();
      int pm = piece_sums[j][0].size();
      if (tc >= pm)
        ++tr, tc = 0;
      if (tr >= pn)
        continue;
      if (tr < 0) {
        val -= piece_sums[j][0][0];
      } else {
        val -= piece_sums[j][tr][max(0, tc)];
      }
    }
    if (val) {
      hd = mid + 1, res = mid;
    } else {
      tl = mid - 1;
    }
  }
  return make_pair(res / m, res % m);
}

/*** 主函数部分 ***/

signed main() {
  // freopen("_in.txt", "r", stdin);
  // freopen("_out.txt", "w", stdout);
  ios::sync_with_stdio(false);
  cin.tie(nullptr), cout.tie(nullptr);

  /* 读入部分 */
  cin >> k;
  target_piece = read_piece();
  for (int i = 0; i < k; ++i)
    ++piece_map[read_piece()];

  /* 目标碎片信息预处理 */
  int n = target_piece.size();
  int m = target_piece[0].size();
  target_hash = xhash(target_piece);
  target_sums = calc_sums(target_piece);

  for (auto it : piece_map) {
    piece p = it.first;
    int index = piece_counts.size();
    piece_counts.emplace_back(it.second);

    /* 枚举碎片自身的变换方式 */
    for (int j = 0; j < 2; ++j) {
      for (int k = 0; k < 4; ++k) {
        if ((int)p.size() > n || (int)p[0].size() > m) {
          rotate(p);
          continue;
        }
        xhash h(p);
        piece_sums.emplace_back(calc_sums(p));
        piece_offsets.emplace_back(find_offset(piece_sums.back()));
        piece_hashes.push_back(h);
        piece_index.push_back(index);

        h.offset(n - piece_offsets.back().first,
                 m - piece_offsets.back().second);
        hash_index[h] = index;
        rotate(p);
      }
      vflip(p);
    }
  }

  /* 枚举前两个碎片的编号，并求出第三个的编号计算 */
  set<tuple<int, int, int>> sols;
  pair<int, int> base1 = find_offset(target_sums);
  for (int i = 0; i < (int)piece_hashes.size(); ++i) {
    pair<int, int> offs1 = base1;
    offs1.first -= piece_offsets[i].first;
    offs1.second -= piece_offsets[i].second;
    if (offs1.first < 0 || offs1.second < 0)
      continue;

    xhash hash1 = piece_hashes[i];
    hash1.offset(offs1.first, offs1.second);

    pair<int, int> base2 = find_offset(target_sums, {i}, {offs1});
    for (int j = 0; j < (int)piece_hashes.size(); ++j) {
      pair<int, int> offs2 = base2;
      offs2.first -= piece_offsets[j].first;
      offs2.second -= piece_offsets[j].second;
      if (offs2.first < 0 || offs2.second < 0)
        continue;

      xhash hash2 = piece_hashes[j];
      hash2.offset(offs2.first, offs2.second);

      pair<int, int> offs3 = find_offset(target_sums, {i, j}, {offs1, offs2});
      if (offs3.first < 0 || offs3.second < 0)
        continue;

      xhash hash_remain = target_hash - hash1 - hash2;
      hash_remain.offset(n - offs3.first, m - offs3.second);

      /* 由目标哈希值与枚举的前两个哈希值，计算得到第三个，在哈希表中查询编号
       */
      auto it = hash_index.find(hash_remain);
      if (it != hash_index.end()) {
        int tmp[3];
        tmp[0] = piece_index[i];
        tmp[1] = piece_index[j];
        tmp[2] = it->second;
        sort(tmp, tmp + 3);
        sols.emplace(tmp[0], tmp[1], tmp[2]);
      }
    }
  }

  /* 使用组合数计算真实的答案数量 */
  int result = 0;
  for (auto sol : sols) {
    int c0 = piece_counts[get<0>(sol)];
    int c1 = piece_counts[get<1>(sol)];
    int c2 = piece_counts[get<2>(sol)];
    if (get<0>(sol) == get<2>(sol)) {
      result += c0 * (c0 - 1) * (c0 - 2) / 6;
    } else if (get<0>(sol) == get<1>(sol)) {
      result += c0 * (c0 - 1) / 2 * c2;
    } else if (get<1>(sol) == get<2>(sol)) {
      result += c0 * c1 * (c1 - 1) / 2;
    } else {
      result += c0 * c1 * c2;
    }
  }

  cout << result << "\n";

  return 0;
}

最后修改于 2025-07-05

Git 版本: de2abab