1829년. 각 쿼리에 대한 최대 XOR
난이도:중
주제: 배열, 비트 조작, 접두사 합계
음이 아닌 정수 n개로 구성된 정렬된 배열 수와 정수 maximumBit가 제공됩니다. 다음 쿼리를 n 번 수행하려고 합니다:
배열 답변을 반환합니다. 여기서 답변[i]는 i번째 쿼리에 대한 답변입니다.
예 1:
예 2:
예 3:
제약조건:
힌트:
해결책:
배열에 있는 요소의 XOR을 효율적으로 계산하고 k가 2^maximumBit보다 작도록 k 값을 사용하여 결과를 최대화해야 합니다. 이 문제를 해결하는 방법은 다음과 같습니다.
XOR 최대화:
maximumBit 비트에 대한 접두어 합계와 XOR할 수 있는 최대 수는 ( 2^{text{maximumBit}} - 1 )입니다. 이는 모두 1인 개수(예: 이진수로 111...1)를 XOR하면 항상 결과가 최대화되기 때문입니다.
접두사 XOR 계산:
각 쿼리에 대해 XOR을 다시 계산하는 대신 전체 배열에 대해 누적 XOR을 유지할 수 있습니다. XOR에는 A XOR B XOR B = A라는 속성이 있으므로 배열의 마지막 요소를 제거하려면 누적 XOR에서 해당 요소를 XOR하면 됩니다.
알고리즘:
PHP에서 이 솔루션을 구현해 보겠습니다: 1829. 각 쿼리에 대한 최대 XOR
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 |
|