USACO 2015 February Contest, Silver Problem 3. Superbull

原題下載

USACO2015FEB-S3

答案

#include <iostream>
#include <vector>
#include <cstdio>

using namespace std;

int main() {
  freopen("superbull.in", "r", stdin);
  freopen("superbull.out", "w", stdout);

  int N;
  cin >> N;
  vector<int> A(N);
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }

  long long result = 0;
  vector<bool> used(N, false);
  vector<int> D(N, 0);
  for (int i = 0; i < N; i++) {
    /* Find the index, j, of the 'furthest' node from the current spanning tree. */
    int j = -1;
    for (int k = 0; k < N; k++) {
      if (used[k]) continue;
      if (j == -1 || D[k] > D[j]) {
        j = k;
      }
    }

    /* Update the result and 'relax' the edges out of vertex j. */
    result += D[j];
    used[j] = true;
    for (int k = 0; k < N; k++) {
      D[k] = max(D[k], A[j] ^ A[k]);
    }
  }

  cout << result << endl;
  return 0;
}

以上就是關于【USACO 2015 February Contest, Silver Problem 3. Superbull】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

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

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