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

往期文章阅读推荐：

美国AI奥赛首次新增低龄组！2027 USAAIO报名中，2月正式开考！

不考编程实操？2026 CAICP人工智能能力认证首轮11月22日开考，备考指南速递！