Water Tree (CF 343D)http://codeforces.com/problemset/problem/343/D거꾸로 생각한다. 기본적으로 모든 노드에 물이 채워져 있고, 1 ~ N개의 노드에 물을 비우는 연산을 넣어 줬다고 가정하자. 비우는 연산이라 함은 해당 노드와 그 부모에 있는 물을 모두 제거함을 뜻한다. * Query 1 : v의 서브트리에, 물이 비우는 연산이 적용되어 있는 노드가 있다면, 모두 지워주고, v의 부모에 물을 비우는 연산을 적용한다. * Query 2 : v에 물을 비우는 연산을 적용한다. * Query 3 : v의 서브트리에 물이 비우는 연산이 적용되어 있었다면 0, 아니면 1을 출력한다. 문제가 아주 깔끔해졌으며, dfs number 순서대로 수를 보관해두면, 세그먼트..
http://59.23.113.171/pool/koi_tree/koi_tree.php?pname=koi_tree Observation 1.문제를 쉽게 해서 유사도가 2일 때를 가정해보자. 그 때는 - 부모가 같으면 연결되어 있다. - 부모가 다르면 연결이 안되어 있다.고로 완전 그래프인 컴포넌트들이 떠다니는 그래프를 상상할 수 있다. 부모가 같은 게 뭔가 중요해 보인다는 사실을 알 수 있고, 난 여기서 착안해서 계통 트리를 다음과 같이 재정의했다. * 계통 트리는 S+1개의 노드로 이루어진 트리로, 각각의 노드는 1 ~ N의 개체들을 0개 이상 포함하고 있다. 이 때, 모든 개체는 정확히 한개의 노드에 속한다. 말로 하기가 너무 뭐한데.. 저 말대로 예제를 그려보면 대충 이런 느낌의 트리가 나온다. 이렇..
프리스비 (USACO Gold 2014.12)https://www.acmicpc.net/problem/10649N이 작은 문제다. 1) 비트 DP를 한다. dp(S) = 현재 집합의 추가 가능한 스택 양 이라 정의하면, Min(dp(S\j), Pj - Sum(S\j)) 중 최대인 j를 고르면 된다. 이후 모든 부분집합 S 중에 높이 합이 H 이상인 애들에 대해서 최댓값을 고른다. 2) 그리디를 한다. 집합이 고정되어 있을때, P + W 순으로 정렬한 후 구한 Min(P + W - S) 값이 항상 가능한 순열 중 최대를 낼 수 있다는 것을 증명할 수 있다. 고로 초기에 P+W 순으로 정렬후 모든 집합에 대해서 시뮬레이션하면 된다. 이런걸 그리디로 할 때는, deadline first라는 걸 기억해두면 편한..
- Total
- Today
- Yesterday