구사과

Hill Walk (USACO 2013.03 Gold)https://www.acmicpc.net/problem/5835x좌표를 쭉 증가시키면서, 현재 f(x) 값으로 정렬된 선분들을 들고 다니면 쉽게 풀 수 있다. 이런걸 하는 데 가장 좋은 툴은 뭐니뭐니해도 BST. 선분이 교차할 일이 없기 때문에 한번 삽입 할 때 제대로 삽입하면 끝까지 문제가 생기지 않음을 알 수 있다. 저런 정렬된 선분들을 제대로 들고 다니려면 1. comparator를 재정의해야 하고, 2. comparator의 반환값이 가변적이라는 사실에 언어가 x랄을 하지 않아야 문제를 풀 수 있다는 점을 유념해야 한다. 1번은 http://amugelab.tistory.com/entry/STL-priority-queue-%ED%99%9C%E..

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개 이상 포함하고 있다. 이 때, 모든 개체는 정확히 한개의 노드에 속한다. 말로 하기가 너무 뭐한데.. 저 말대로 예제를 그려보면 대충 이런 느낌의 트리가 나온다. 이렇..