USACO 2016 January Contest, Gold Problem 3. Lights Out

答案:

(Analysis by Mark Gordon)

This problem asks us to simulate Bessie tracing the barn clockwise until she knows where she is. One way to think about this is to abstract away the polygon aspect of the problem and instead treat the angles and side lengths as a string. Now we need to help Bessie explore a string instead. Therefore we want try, for each starting position, extending the string until we get a unique substring.

It's efficient enough to simply use a set structure to test for uniqueness of a substring. To make it faster one could use hashes or suffix arrays instead.

Here's my solution to this problem

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;

#define MAXN 210

int opt[MAXN];

int main() {
  int N; cin >> N;
  vector<pair<long long, long long> > A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i].first >> A[i].second;
  }

  /* Create the underlying string from the polygon.  Represent the exit as
   * 0.  Represent clockwise turns as -1, counter clockwise as -2.  Represent
   * lengths by their length.
   */
  vector<int> S(1, 0);
  for (int i = 0; i < N; i++) {
    int j = (i + 1) % N;
    int k = (i + 2) % N;
    S.push_back(abs(A[i].first - A[j].first) +
                abs(A[i].second - A[j].second));

    /* Use a cross product to determine which way the polygon turned. */
    if ((A[i].first - A[j].first) * (A[k].second - A[j].second) -
        (A[k].first - A[j].first) * (A[i].second - A[j].second) > 0) {
      S.push_back(-1);
    } else {
      S.push_back(-2);
    }
  }
  S.back() = 0;

  /* Compute the lights-on cost for each corner. */
  for (int i = 0; i < N; i++) {
    opt[i + 1] = opt[i] + S[2 * i + 1];
  }
  opt[N] = 0;
  for (int i = N - 1; i >= 0; i--) {
    opt[i] = min(opt[i], opt[i + 1] + S[2 * i + 1]);
  }

  multiset<vector<int> > st;
  for (int i = 0; i < S.size(); i += 2) {
    for (int ln = 1; i + ln <= S.size(); ln += 2) {
      st.insert(vector<int>(S.begin() + i, S.begin() + i + ln));
    }
  }

  int result = 0;
  for (int i = 2; i + 2 < S.size(); i += 2) {
    int ln;
    int cost = 0;
    for (ln = 1; ; ln += 2) {
      if (st.count(vector<int>(S.begin() + i, S.begin() + i + ln)) == 1) {
        break;
      }
      cost += S[i + ln];
    }
    result = max(result, cost + opt[(i + ln) / 2] - opt[i / 2]);
  }
  
  cout << result << endl;
  
  return 0;
}

以上就是关于【USACO 2016 January Contest, Gold Problem 3. Lights Out】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

USACO计算机奥赛如何认证成绩？2026赛季黄金铂金组“定时开赛”规则详解！

USACO计算机奥赛考试语言是什么？C++、Python、Java选哪个效率最高？