USACO 2016 January Contest, Gold Problem 3. Lights Out

原题下载

USACO2016-JAN-G3

答案:

(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;
}

关于翰林

翰林教育是一家涵盖各科目国际学术竞赛教辅(AMC/HiMCM/USACO/DECA)、国际课程辅导(IB/AP/Alevel/IGCSE)、国外著名夏校项目申请的专业国际教育培训机构。为广大学员家长提供高端本科研究生申请及就业咨询,有一对一等多种线上线下的教辅方式,为学员量身定制从9年级到研究生的权威全程国际竞赛方案。翰林拥有业内稀缺的竞赛资料和课程真题等珍贵的学术资源,国内课程辅导领域罕见的纯正海归精英教辅团队-翰林专业导师团-均有世界名校背景和欧美留学经历,都曾供职全球知名教育集团、国际学校,学术团队和世界500强公司了解更多翰林学院信息

翰林学院藤校牛剑录取成果

以藤校牛剑offers为导向的国际教育团队翰林学院专心学术和竞赛,5年来翰林学员共获得:

35张藤校offer

更有MIT、Caltech、UChicago 等offer

62张公立常春藤(UBC UNC UVA UMichigan William Mary等)offers

翰林学院为大家精心打造:

8大科目100个以上国际竞赛服务产品
覆盖全科的国际课程辅导(A-Level/IB/IGCSE/AP等)
1000家以上高端学术夏校项目
500个以上覆盖全科的科研主题