[AtCoder] ABC 197 C – ORXOR
問題
方針
長さ \( N \) の数列から得られる長さ \( 1 \) 以上の連続した部分数列は、\( 2^{N-1} \) 通りあるので、ビット全探索します。イメージとして、分割される位置をビット列で表し、その値を更新していけば良いです。
また、論理和と排他的論理和の性質として、非負整数 \( x \) に対して、
\begin{eqnarray}
x \ \mathrm{OR} \ 0 &=& x\\
x \ \mathrm{XOR} \ 0 &=& x
\end{eqnarray}
であることを利用して初期値を決めています。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; int A[20]; int func(int l, int r) { int ret = 0; for (int i = l; i < r; i++) { ret = ret | A[i]; } return ret; } int main() { int N; cin >> N; for (int i = 0; i < N; i++) { cin >> A[i]; } int ans = INT32_MAX; for (int i = 0; i < (1<<(N - 1)); i++) { int tmp = 0; int l = 0; for (int j = 0; j < N - 1; j++) { if (i & (1<<j)) { tmp = tmp ^ func(l, j + 1); l = j + 1; } } tmp = tmp ^ func(l, N); ans = min(ans, tmp); } cout << ans << "\n"; return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません