본문 바로가기

알고리즘 관련/BOJ

BOJ)11338 XOR Sum

문제: icpc.me/11338


n개의 쿼리가 주어질 때 2가지 쿼리에 따라서 문제를 해결하는 문제이다.


insert 쿼리는 리스트에 숫자를 추가하는것이며 


print 쿼리는 리스트 중에 상위 K숫자를 XOR한 값을 출력하는 문제이다.


우리는 매 print마다 리스트에서 XOR을 할 경우 시간초과가 나므로 insert 될 때 마다 모든 값을 XOR해준 뒤 minheap을 이용하여 리스트 숫자가 K를 초과할때 마다 최솟값을 XOR해준다. 이는 A^X^X=A가 되는 원리를 이용하는 풀이이다.


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
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
char a[7];
int t, m, k, n, r, c;
int main() {
    scanf("%d"&t);
    while (t--) {
        r = c = 0;
        priority_queue<int> pq;
        scanf("%d%d"&m, &k);
        for (int i = 0; i < m; i++) {
            scanf("%s"&a);
            if (a[0== 'i') {
                scanf("%d"&n);
                pq.push(-n);
                r ^= n;
                c++;
                if (c > k) {
                    r ^= -pq.top();
                    pq.pop();
                }
                    
            }
            else {
                printf("%d\n", r);
            }
        }
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)2233 사과나무  (0) 2017.02.01
BOJ)3682 동치 증명  (0) 2017.01.31
BOJ)2211 네트워크 복구  (0) 2017.01.26
BOJ)2275 트리의 높이 줄이기  (0) 2017.01.25
BOJ)8012 한동이는 영업사원!  (2) 2017.01.25