전체 글36 CF 1736D https://codeforces.com/contest/1736/problem/D Problem - D - Codeforces codeforces.com 이것저것 시도해보다 못풀고 그냥 튜토리얼 보고 업솔빙. 일단 1, 0 개수가 짝수개면 가능. 모든 경우에 s[i] == s[i + 1]를 만들 수 있다.(i는 홀수) s[i] != s[i + 1]인 모든 i에 대해 홀수번째는 0을 고르고 짝수번째는 1을 고르면 된다. 이 경우의 i개수는 짝수개 이기 때문이다. 증명) s[i] != s[i + 1]인 i의 개수를 x, s[i] == s[i + 1] 이고 s[i] == 1인 i의 개수를 y라고 하면 1의 개수는 x + y * 2이다. 이때, 1의 개수가 짝수이려면 x도 짝수여야 한다. 2022. 10. 21. Euler circuit, Euler tour technique Euler circuit vector adj; vector circuit; void dfs(int cur) { for (int next = 0; next 0) { adj[cur][next]--; adj[next][cur]--; dfs(next); } } circuit.push_back(cur); } Euler tour technique int S[100010], E[100010], cnt; vector adj; void dfs(int cur, int prev) { S[cur] = ++cnt; for (auto next: adj[cur]) { if (next == prev) continue; dfs(next, c.. 2022. 10. 14. BOJ 14591 https://www.acmicpc.net/problem/14591 14591번: KUBC League (Large) 고려대학교 중앙 배드민턴 동아리 KUBC에서 정회원들을 대상으로 리그를 했다. 태양이를 포함해서 N명의 정회원들이 리그에 참여했고, 총 N(N-1)/2번의 경기를 진행하였다. 그 결과 모든 경기가 승 www.acmicpc.net 먼저 모든 정점에 대해 p가 q를 이기면 p -> q 간선을 만들어준다. 그 다음 dfs트리를 만들어 보자. 그러면 이런 모양이 나온다.(정점 번호는 방문 순서) 정답은 그냥 빨간색 edge를 따라가서 방문하는 모든 정점을 출력하면 된다. 왜냐하면 어떤 정점 p의 부모 노드가 아니면서 dfs트리 방문 순서가 p보다 먼저라면 p에서 그 정점으로 향하는 간선이 있기 .. 2022. 10. 14. CF 1741E https://codeforces.com/contest/1741/problem/E Problem - E - Codeforces codeforces.com 너무 많이 풀렸길래 쫄려서 무지성 o(n^2) dp 썼다가 핵맞고 뒤짐. 기본 dp풀이에다 세그먼트의 원소수가 뒤로 오는 경우에 대해 전처리만 해주면 된다. 모든 i에서 (i - b[i]) -> i 인 간선을 만든다. (i - b[i] >= 0) 이러면 dp[i] = dp[i+b[i]+1] | dp[adj[i][j] + 1] 가 된다. 2022. 10. 12. 이전 1 2 3 4 5 6 7 8 9 다음
