알고리즘/백준 & swacademy108 BOJ 17306 - 전쟁 중의 삶 (트라이, 완전이진트리) https://www.acmicpc.net/problem/17306 무한완전 이진트리가 주어지고 루트(1)부터 각 정점에 순서대로 번호가 매겨진다. 최대 25e4개의 정짐의 번호(2^50보다 작음)가 주어진다. 정점간의 경로 상에 포함되는 모든 정점의 수를 구하라 각 정점의 번호를 2진수로 나타내면 1에서부터 그 정점까지의 경로를 트라이로 표현할 수 있다. 각 정점마다 1에서부터 경로 상의 최대 정점 수는 50개이므로 트라이의 총 노드의 수는 최대 50n개이다. 트라이의 각 노드 u마다 u를 루트로하는 서브트리에 포함된 정점의 수(term==1인 정점의 수)를 d[u]라고 할 때, d[u]가 1이상 n미만인 경우 u는 경로상에 반드시 포함된다. #include #define FAST ios_base::s.. 2020. 6. 10. BOJ 3392 - 화성지도 (세그트리 응용) https://www.acmicpc.net/problem/3392 코드는 다음 블로그의 코드를 많이 참조했습니다. https://jason9319.tistory.com/58 일반적인 세그트리의 형태를 따르지 않고, 세그먼트트리의 구조를 이용하여 풀 수 있는 문제. 좌표가 최대 30000인 2차원 평면 상에 최대 1e4개의 직사각형이 주어질 때, 직사각형들이 이루는 영역의 크기를 구하라 x좌표가 증가하는 순서대로 막대기들을 볼 때, "이전 x좌표와의 차 dx"와 "y좌표들의 psum이 1이상인 곳의 개수"를 곱해나가면 된다. 지금 막대기가 [y1,y2)일 떄 이 막대기가 시작 막대기인 경우 해당구간을 모두 +1, 끝 막대기인 경우 해당구간을 모두 -1해주며 배열을 유지해 나간다고 생각해야 한다. 이걸 la.. 2020. 6. 6. BOJ 15899 - 트리의 색깔 (ett, 머지소트트리) https://www.acmicpc.net/problem/15899 기록용 최대 2e5개의 정점을 갖는 트리가 주어진다. 각 정점마다 최대 2e5의 값(색)을 하나씩 갖는다. 다음 쿼리를 처리하자 v c : 정점v를 루트로 하는 서브트리에서 값이 c이하인 정점의 수 서브트리를 구간트리로 처리할 수 있는지? 할 수 있다면 머지소트트리가 가장 적합함 (update쿼리가 없어서 가능) ett번호를 붙여주고 머지소트트리 일반적인 풀이 쓰면 된다. const int MAX = 2e5 + 4; const int MOD = 1e9 + 7; const int SMAX = (1 = 1; i--) { seg[i] = seg[i * 2 + 1]; seg[i].insert(seg[i].end(), seg[i * 2].begi.. 2020. 6. 2. BOJ 2912 - 백설공주와 난쟁이 (머지소트트리, 구간 과반수) https://www.acmicpc.net/problem/2912 한 구간의 원소중 무작위로 하나 골랐을 때 그 원소가 그 구간의 과반수일 확률은 (1/2) 이상이다. 이를 이용해서, 한 쿼리당 20번씩 무작위로 골라서 확률을 높이는 방법도 존재한다. ~~(1e6-1)/1e6의 쿼리개수 승 = 99.00++% 최대 길이 3e5의 배열이 주어진다. 모자 색의 가짓수는 1e4 이하이다. 다음 쿼리를 처리하자 s, e : 구간[s,e]의 과반수값이 존재하면 "yes 과반수값", 존재하지 않으면 "no" 출력 vector c[i] : i색상 모자를 갖는 인덱스들 (오름차순) 구간[s,e] 사이에 i색상 모자가 몇 개 들어있는지는 위 벡터에서 이분탐색하여 알 수 있다. 머지소트트리 상에서 해당 구간에 포함되는 블.. 2020. 6. 2. 이전 1 2 3 4 5 ··· 27 다음