목록Algorithm (121)
블로그 옮겼습니다
문제 링크 \(1\le{N, M}\le{10^5}\)\(0\le{Q}\le{10^5}\)이 문제는 N개의 노드가 있고, 각 노드는 M개의 그룹중 하나에 속한다. 그리고 총 Q개의 간선을 설치할건데1번부터 순차적으로 설치할것이다. 그럴 때에 각 그룹에 대해 그룹에 속한 노드들이 모두 하나의 컴포넌트로연결되는 최소 간선 번호를 구하는것이다. 그러므로 최종적으로 M개의 정수를 출력하면된다.Q번 간선까지 설치했는데도 모든 그룹 노드들이 연결되지않는다면 -1을 출력, 그리고 하나도 간선을 설치하지않아도 모두 연결되면 0을 출력하면된다. 일단 0을 출력하는 경우는 그룹에 속한 노드가 딱 하나만있는 경우밖에 없다. 그러므로 이경우만 따로 처리해주면 될 것이다. 일단 naive 하게 생각해보자. M개의 그룹에 대해서 ..
문제 링크 노드의 수가 100개 이하인 두개의 트리 g1, g2 가 주어진다. 두 트리의 루트 노드는 모두 1번 노드이다. 두 트리의 최대 공통 노드 수를 출력하는 문제이다. 쉽게 말해서 각 노드에 대해서 자식 노드들의 순서를 요리 조리 바꿔도 여전히 같은 트리이기 때문에 각 노드의 자식들의 순서를 요리 조리 바꿨을 때 두 트리중 모양이 일치하는 가장 노드가 많은 부분 트리의 노드 수를 구하는 문제이다. dp[a][b] : 트리 g1에서 노드 a를 루트로 하는 서브트리와, 트리 g2에서 노드 b를 루트로 하는 서브트리의 최대 공통 노드 수 라고 부분 문제를 정의하면 트리 dp 로 해결할 수가 있다. 그렇다면 부분 문제 테이블의 하나의 셀을 어떻게 채울까? 답은 MCMF 이다. dp[a][b] 에서 a의 ..
문제 링크 n, m, d (1 ≤ n ≤ 150000; 1 ≤ m ≤ 300; 1 ≤ d ≤ n).수직선에 1, 2, ..., n 의 장소가 있다. m 개의 폭죽이 임의의 시간과 장소에서 발사된다.주인공은 1초에 d만큼 이동할 수 있다. 시작 위치는 아무데서나 시작해도 된다.i번 폭죽이 발사될 때 주인공이 x 지점에 있을 때 얻게되는 행복은 \(b_i - |a_i - x|\) 이다.이 때 모든 폭죽이 발사되고 난 후에 주인공이 얻은 행복의 양이 최대가 되도록 하고싶다.그 아랫줄부터는 m개의 폭죽의 대한 정보 ai, bi, ti 가 주어진다.ai, bi, ti (1 ≤ ai ≤ n; 1 ≤ bi ≤ 109; 1 ≤ ti ≤ 109) dp[i][j] : t_i 시간에 j 위치에 있을 때 최대 행복도\(dp[..
문제 링크 N > y; ps[i] = {x, y}; vx[i] = x, vy[i] = y; } sort(all(vx)), sort(all(vy)); for(int i = 0 ; i
문제 링크 \(1 A[i]; while(!dq.empty() && dq.front() = A[i]) dq.pop_back(); dq.push_back(i); cout
문제 링크 N
문제 링크 \(1 L; pos.resize(N); for(int i = 0 ; i > pos[i]; auto s = upper_bound(all(pos), 0); auto m = upper_bound(all(pos), L / 2); vector ss = vector(s, m); vector ee = vector(m, pos.end()); reverse(all(ee)); for(int i = 0 ; i
https://community.topcoder.com/stat?c=problem_statement&pm=11817 A, B, X
http://codeforces.com/contest/831/problem/E N > N; for(int i = 1 ; i > a; idxs[a].push_back(i); st.insert(a); update(i, 1); } int pos = 0; ll ans = 0; nums.assign(all(st)); for(int i = 0 ; i