문제풀이
- trie 자료 구조를 구현한다.
- 현재까지의 누적합과 trie 자료 구조 내부의 값을 xor한 것 중에 가장 큰 값을 구한다.
- 현재까지의 누적합을 trie 자료 구조에 add한다.
- N개의 수에 대하여 2, 3번을 반복한다.
주의사항
소요시간
35분
package 백준.Platinum.P3.p13504_XOR합
class Trie(val idx: Int) {
val children = Array<Trie?>(2) { null }
fun add(str: String) {
if (str.length == idx) return
getChild(str[idx]).add(str)
}
private fun getChild(c: Char): Trie {
if (children[c.digitToInt()] == null) children[c.digitToInt()] = Trie(idx + 1)
return children[c.digitToInt()]!!
}
fun result(str: String): String? {
if (str.length == idx) return ""
val curBit = str[idx].digitToInt()
if (children[(curBit + 1) % 2] != null) children[(curBit + 1) % 2]!!.result(str)?.let { return "1$it" }
if (children[curBit] != null) children[curBit]!!.result(str)?.let { return "0$it" }
return null
}
}
fun main() {
fun Int.toBinaryString() = toString(2).let { "${"0".repeat(32 - it.length)}$it" }
val sb = StringBuilder()
repeat(readln().toInt()) {
readln()
val trie = Trie(0)
var result = 0
var sum = 0
for (elm in readln().trim().split(" ").map(String::toInt)) {
sum = sum xor elm
val str = sum.toBinaryString()
result = maxOf(result, sum, trie.result(str)?.toInt(2) ?: 0)
trie.add(str)
}
sb.appendLine(result)
}
println(sb)
}