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: