본문 바로가기

알고리즘225

cf #656 div3 E - Directing Edges(위상정렬, 사이클 유무) https://codeforces.com/contest/1385/problem/E 방향그래프와 무향그래프가 섞인 그래프에서 위상정렬을 구해야 해서 헷갈렸다. 위상정렬 결과로 사이클 판단하는 방법도 숙지해 뒀어야 하는 문제 정점u,v사이엔 최대 하나의 무향또는 유향간선만 존재하는 그래프가 주어진다. 유향간선을 적절히 조정해서 accyclic그래프를 만들 수 있다면 그 간선들을 출력하라 손으로 좀 그리다보면 유향간선만 가지고 사이클이 존재하지 않는다면 항상 정답이 존재함을 알 수 있다. 유향간선 기준 ind로 topological sort를 한 순서벡터로 각 정점마다 순서를 매긴다. 유향간선 u->v 중 rank[u]>rank[v]인 경우가 존재하면 사이클이 있다는 것 의미함. 사이클이 없다면 ,모든 간선을.. 2020. 7. 20.
cf #653 div3 F - Cyclic Shifts Sorting (그리디, constructive, sorting, inversion) https://codeforces.com/contest/1374/problem/F 소팅 문제에서 inversion개수로 규칙찾기 원소의 수가 n개인 배열 a에서 다음 연산을 최대 $n^2$번 수행하여 정렬하여라. 정렬 못하면 -1 출력 1. i번째 원소를 맨 앞으로 가져올 수 있다. 2. a의 원소가 모두 distinct하면 위 operation으로 inversion 개수의 parity를 바꿀 수 없다. 따라서 이 때 inversion 개수의 parity가 홀수면 정렬 불가능하다. 3. a의 원소에 중복 원소가 있다면 일단 distinct한 배열로 바꿔준 후에, inversion 개수의 parity가 홀수라면 중복 원소 한 쌍을 swap하여 parity를 짝수로 맞춰주면 된다. 예를들어 $a = [2,1.. 2020. 7. 13.
BOJ 7469 - K번째 수 ( 머지소트트리, pst ) https://www.acmicpc.net/problem/7469 두가지 방법으로 가능 머지소트트리, 퍼시스턴트세그트리 pst론 구간 k번째 수를 효과적으로 셀 수 있다. (세그먼트트리에서 전체 k번째 수를 세는 것이랑 비슷함) 최대 1e5개의 정수 배열이 주어진다. 배열의 원소는 절대값이 1e9보다 작은 정수이다. 다음 쿼리를 처리 s,e,k : 구간[s,e]의 k번째 수를 출력 - 머지소트트리 머지소트트리를 만든 후, 1. 쿼리마다 -1e9~1e9사이에서 k번째 수가 될 수 있는 최소값을 구한다. 구간에서 x미만의 수의 개수가 k-1개이상인 수 중 최소값을 구해주면 된다. (이분탐색 시 음수범위에 주의) 2. 구간에서 x이상 최소값을 찾아 출력해준다. const int MAX = 2e5 + 4; co.. 2020. 6. 10.
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.

티스토리툴바