Official
C - ORXOR Editorial by QCFium
\(A\) を \(1\) つ以上の空でない連続した区間に分ける方法を全て試し、問題文に定められている値が最小になるものを探します。
\(N\) 要素の数列を \(1\) つ以上の空でない連続した区間に分ける方法を全て試すには、隣り合う要素の間 (\(N - 1\) 個ある) それぞれに仕切りを入れるか入れないかの \(2^{N - 1}\) 通りを試せばよいです。
実装時には、この \(N - 1\) 個の入れるか入れないかを、\(N - 1\) 桁の \(2\) 進数とみなして \(0\) 以上 \(2^{N - 1}\) 未満の整数と対応させる bit 全探索と呼ばれている方法が便利です。
解答例 (C++)
#include <bits/stdc++.h>
int ri() {
int n;
scanf("%d", &n);
return n;
}
int main() {
int n = ri();
int a[n];
for (auto &i : a) i = ri();
int res = 2000000000;
for (int i = 0; i < 1 << (n - 1); i++) {
int xored = 0;
int ored = 0;
for (int j = 0; j <= n; j++) {
if (j < n) ored |= a[j];
if (j == n || (i >> j & 1)) xored ^= ored, ored = 0;
}
res = std::min(res, xored);
}
printf("%d\n", res);
return 0;
}
posted:
last update: