https://codeforces.com/contest/1285/problem/D
코포에서 분할정복 처음 풀어봐서 코드만 남겨둠
<문제설명>
최대 1e5개의 숫자를 입력받는다. 이 숫자들과 임의의 수 X를 xor할 때 가장 큰 ai xor X의 값이 가장 작도록 X를 구해라
<풀이>
코드로 대체
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int MAX = 1e5 + 5;
int n, a[MAX];
int minV(int st, int en, int bt) {
int mid = -1;
for (int i = st; i <= en - 1; i++)
if ((a[i] & (1<<bt)) != (a[i + 1]&(1<<bt)))
mid = i;
if (bt == -1) return 0;
if (mid == -1)
return minV(st, en, bt - 1);
else
return (1<<bt) + min(minV(st, mid, bt - 1), minV(mid + 1, en, bt - 1));
}
int main() {
FAST;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
sort(a, a + n);
int ans = minV(0, n - 1, 29);
cout << ans << '\n';
}
'알고리즘 > 코드포스' 카테고리의 다른 글
codeforces 614 div2 C - Neko's maze game (발상) (0) | 2020.01.20 |
---|---|
Educational codeforces #80 D - Minimax Problem(이분탐색, 비트마스크) (0) | 2020.01.17 |
codeforces #612 div2 D - Numbers on Tree (그래프, 수학, 구현) (0) | 2020.01.07 |
Educational codeforces #69 div2 D - Yet Another Subarray Problem (dp) (0) | 2020.01.05 |
codeforces #610 div2 B2 - K for the Price of One (구현) (0) | 2019.12.30 |