https://www.acmicpc.net/problem/24500
문제요약
- 1부터 n까지 숫자가 있음(10^18)
- 임의의 숫자를 골라서 xor 최대 만들기
- 고르는 숫자가 적을수록, 사전순으로 빠를 수록
접근법
- 연산을 하면 n의 최고 비트 이하는 다 채울 수 있음.
- 왜냐하면 가장 높은 자리 비트를 제외하고 나머지가 1인 것들은 항상 n보다 작기 때문임. n이 1....이라면 1000000.. 과 011111..을 고를 수 있음
- 숫자를 적게 골라야하기 때문에 1개 아니면 두개임
- 1개 : n이 11111의 형태인 경우 더 고를 것도 없음
- 2개 : 1000...과 01111...고르면 일단 두개임
- 그런데 2개를 고르는 방법을 사전순으로 앞서게 하려면 작은 숫자를 가장 작게 해야함. 01111...보다 더 작게 할 수 있음
- n을 반전시킨 숫자가 가장 작음
- 만약에 이 숫자보다 더 작게 하려면 이 숫자에서 특정 비트를 0으로 바꾸고, 그 바꾼 비트가 다른쪽 에 포함되어야하는데, 다른쪽에 포함되면서 n의 비트도 포함하려면 n보다 커지거나 3개 이상이 되어야함
newbieski