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】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！

2026理工科競賽“大洗牌”：線上考試終結、報名門檻收緊、晉級規則重塑...你準備好了嗎？