티스토리 뷰

알고리즘 관련/BOJ

BOJ)11338 XOR Sum

JASON 자손9319 2017. 1. 31. 15:12

문제: 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)11338 XOR Sum  (0) 2017.01.31
BOJ)2211 네트워크 복구  (0) 2017.01.26
BOJ)2275 트리의 높이 줄이기  (0) 2017.01.25
BOJ)8012 한동이는 영업사원!  (2) 2017.01.25
TAG
,
댓글
댓글쓰기 폼