USACO 2015 US Open, Bronze Problem 1. Moocryption

原题下载

USACO2015OPEN-B1

答案

(Analysis by Nick Wu)

There are too many substitution ciphers for us to check every single one and see which one gives the maximum number of MOOs.

However, if we only care about appearances of the word MOO, then we only care about two letters in the substitution cipher - which letter gets converted to M, and which letters gets converted to O.

We can brute force over all such pairs, making sure that we don't map M to M, O to O, or try to map the same letter to both M and O. The grid has at most 502⋅8=20000502⋅8=20000words, and there are at most 262=676262=676 pairs that we would brute force (we would ignore some of them), so the number of operations is roughly 20 million, which is small enough.

Here is Mark Gordon's C++ code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>

using namespace std;

int N, M;
vector<string> A;

int dr[] = {-1, -1, -1, 0, 1, 1, 1, 0};
int dc[] = {-1, 0, 1, 1, 1, 0, -1, -1};

char get(int r, int c) {
  if (r < 0 || N <= r || c < 0 || M <= c) {
    // we are outside the grid, return a non-letter
    return '_';
  }
  return A[r][c];
}

int main() {
  freopen("moocrypt.in", "r", stdin);
  freopen("moocrypt.out", "w", stdout);

  cin >> N >> M;
  A.resize(N);
  for (int i = 0; i < M; i++) {
    cin >> A[i];
  }

  int best = 0;
  for (char mch = 'A'; mch <= 'Z'; mch++) {
    // pick a character that will be set to M
    if (mch == 'M') {
      continue;
    }
    for (char och = 'A'; och <= 'Z'; och++) {
      // pick a character that will be set to O
      if (och == 'O' || mch == och) {
        continue;
      }
      int result = 0;
      for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
          // check the first character would be M
          if (get(i, j) != mch) {
            continue;
          }
          // try all possible words starting at square (i,j)
          for (int k = 0; k < 8; k++) {
            // check the next two characters would be O
            if (get(i + 1 * dr[k], j + 1 * dc[k]) == och &&
                get(i + 2 * dr[k], j + 2 * dc[k]) == och) {
              result++;
            }
          }
        }
      }
      best = max(best, result);
    }
  }
  cout << best << endl;

  return 0;
}

以上就是关于【USACO 2015 US Open, Bronze Problem 1. Moocryption】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

2026 NOAI国际AI奥赛中国站即将开考！赛事地址&日程已出！

2027 USAAIO美国AI奥赛启动报名！MIT/谷歌/Jane Street集体站台！