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】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

5金3银！2026 IOAI国际人工智能奥赛收官！中国队取得历史性突破！

AI奥赛2026国家队名单公布！ 新赛季翰林助力直通IOAI全球总决赛！