아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

XOR 카드 게임

면접 대비

시간 제한1초메모리 제한1024 MB

요약
카드 더미를 두 장 또는 세 장씩 묶어 각 묶음의 XOR 값에서 1의 개수를 점수로 얻을 때, 카드 한 장이 남지 않도록 하면서 얻을 수 있는 최고 점수를 구한다.
난이도

보통10점 중 5점

유형
동적 계획법, 비트 연산, 배열, 누적 합
정답자
아직 제출이 없습니다

문제

XOR 카드 게임이란 NN장의 카드 더미가 있을 때, 맨 위에서부터 카드를 두 장 혹은 세 장씩 가져가 점수를 획득하는 게임이다. 이 게임에서 점수는 아래 단계를 거쳐 누적해서 획득할 수 있다.

  1. 한 번에 가져가는 카드들에 적혀있는 번호를 XOR 연산한다.
  2. 1에서 구한 값을 이진수로 변환했을 때, 1의 개수만큼 점수를 획득한다.

게임을 진행하며 주의할 점은 마지막에 카드 한 장이 남는 상황이 존재할 수 있는데, 이 경우엔 모든 점수를 잃고 0점으로 게임을 종료하게 된다. 이 게임에서 얻을 수 있는 최고 점수를 계산하시오.

입력

첫째 줄에 카드 더미에 있는 카드의 개수 NN이 주어진다. (1≤N≤100,000)(1 \le N \le 100\\,000)

둘째 줄에 각 카드에 적힌 정수 A_1,A_2,⋯ ,A_NA\_1, A\_2, \cdots, A\_N이 공백으로 구분되어 주어진다. (20≤A_i<210;(2^0 \le A\_i < 2^{10}; A_iA\_i는 카드 더미의 위에서부터 ii번째 카드에 적힌 수이다.))

출력

이 게임에서 획득할 수 있는 최고 점수를 출력한다.

힌트

비트 XOR (Bitwise XOR) 연산자에 대한 자세한 정보는 위키백과에서 확인할 수 있다.

예제3

  1. 예제 1

    입력
    5
    2 1 3 8 4
    
    예상 출력
    6
    
  2. 예제 2

    입력
    7
    67 351 9 1023 497 261 1001
    
    예상 출력
    18
    
  3. 예제 3

    입력
    1
    5
    
    예상 출력
    0