프로그래밍 (2) 썸네일형 리스트형 [BOJ 23719] K번째 음식 찾기 1 https://www.acmicpc.net/problem/23791 23791번: K번째 음식 찾기 1한식 [1..3], 양식 [1..3]을 오름차순으로 나열하면 1 2 3 5 8 10이고 여기서 세 번째로 맛있는 음식 맛은 3이므로 첫 번째 질의 정답은 양식 2번이다. 한식 [1..3], 양식 [1..4]를 오름차순으로 나열하면www.acmicpc.netTag : binary search 문제요약정렬된 배열 a, b가 입력으로 주어지고 쿼리마다 a[1 : p], b[1 : q]에서 k번째 수를 찾는 문제다. 풀이먼저 a의 인덱스를 기준으로 이분탐색을 진행한다. 결정함수 chk(m) := a[1 : p], b[1 : q]에서 a[m]이 k번째 수 이상이면 true b에 k번째 수가 있으면 a, b를 뒤.. [BOJ 17469] 트리의 색깔과 쿼리 https://www.acmicpc.net/problem/17469 17469번: 트리의 색깔과 쿼리N개의 정점으로 구성된 트리가 있다. 각 정점은 1번부터 N번까지 번호가 매겨져있고, 1 이상 10만 이하의 자연수로 표현되는 색깔을 하나 갖고 있다. 루트는 1번 정점이고, 트리이기 때문에 임의www.acmicpc.netTag : Offline Query, DSU, Small To Large 풀이간선을 제거하는 것은 일단 생각하지 말자. 어떠한 정점 \(A\)에서 갈 수 있는 점은 같은 컴포넌트에 있는 모든 정점이다. 컴포넌트들에 대해 서로 다른 색의 개수를 구하려면 일단 컴포넌트마다 std::set을 가지고 있어야할 듯하다.이 때 컴포넌트는 DSU로 처리하면 되니 2번쿼리를 std::set::size를.. 이전 1 다음
