블로그 옮겼습니다

1c, a->c 가 연결 되어있다면 a->c 가 없어도 a에서 b를 통해 c로 갈 수 있기 때문에 a->c 는 필요 없는 간선이 된다. 아무튼 이런 쓸모없는 간선들을 찾아서 지워주는게 문제의 핵심인데, 문제는 어떻게 해야하느냐이다. 우선 확실한건 같은 SCC내에 있는 노드 K개가 있다면 이 들이 SCC를 이루기 위한 최소한의 간선 수는 K개 이다. 이 것은 자명하다. 그리고 다른 SCC간의 간선은 딱 하나만 필요하므로 정점 압축을 한뒤 플로이드로 불필요한 간선을 지울 수가 있다. u -> k 이고 k -> v이면 u -> v 는 필요없다는 식으로 지울수있다. 그리고 SCC를 묶지않고 처음부터 플로이드로만 불필요한 간선을 지우면 되지않을까해서 새로 짜봤는데 틀렸는데, 생각을 좀 해보면. 같은 SCC 내에 ..

https://oj.uz/problem/view/OJUZ11_rail 2

http://codeforces.com/contest/776/problem/C 1 ≤ n ≤ 105, 1 ≤ |k| ≤ 10 sequence 의 길이 n과 k가 입력으로 주어지고 n개의 원소가 입력으로 주어질때 원소의 합이 k^x 의 형태인 non-empty, continuous subsequence 의 개수를 찾는 문제 우선 모든 경우를 다 따져준다면 O(n^2) 로 TLE 가 난다. 우선 누적합 pSum 을 모든 인덱스에 대해 다 구해준다. 그러면 [l,r] 의 subsequence 의 원소의 합은 pSum[r]-pSum[l-1] 로 나타낼수있다. 즉pSum[r] - pSum[l-1] = k^x 인 (l,r) 쌍의 수를 찾으면 되는데 만약 위의 식이 성립한다면 항을 적절히 넘겨서 이런식을 도출해 낼 ..