목록Algorithm (121)
블로그 옮겼습니다
https://www.acmicpc.net/problem/2365 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697#include using namespace std;typedef long long ll;const int mod = 1e9+7;const int INF = 0x3c3c3c3c;const long long INFL = 0x3c3c3c3c3c3c3c3c; struct edge{int to, cap, rev;};int..
https://community.topcoder.com/stat?c=problem_statement&pm=11308 풀이를 떠올린 속도는 나쁘지는 않았는데 cache 의 초기값을 -inf 로 안주고 0으로 줬다가 디버깅하느라 시간이 좀 걸렸다. 트리의 간선의 수 N이 정해지면 모든 노드들의 degree 의 합도 2N 으로정해지기 때문에 노드 수와 degree의 합이 N+1과 2N이 되게 하는 모든 degree의 조합의 최대 점수를 dp로 계산하면 된다. 트리의 노드 수와 트리 노드들의 degree 의 합만 기준에 일치한다면 각 노드의 degree 에 대한 조합이어떻게 되던 그에 해당하는 트리를 만들 수가 있다는 사실을 캐치하는 것이 중요한 것같다.이 것만 캐치하면 dp로는 바로 연결되기때문에. 12345..
LCA(A, C) = C, LCA(B, C) = LCA(A, B) or LCA(B, C) = C, LCA(A, C) = LCA(A, B)가 참이면 존재하는거임
https://www.acmicpc.net/problem/1444 하나의 단어는 알파벳 소문자하나와 대문자 하나로 이루어진다. 소문자가 앞에 나오는 경우와 뒤에 나오는 경우이렇게 두가지 경우가 있다. 알파벳 소문자와 대문자가 번갈아 나오는 문장이 입력으로 들어올 때이 문장은 몇 개의 단어로 이루어 질 것이다. 이 때 여러가지 케이스가 있을 텐데 그중 최소 단어 개수를 찾는 문제이다.예를 들어 aAbAc 가 있으면 aA, bB, Ac 로 이루어 졌을 수도 있고 aA, Ab, Ac 로 이루어 졌을 수도 있는 것이다. 이 문제는 결국 최소 정점 덮개 이다. 최소 정점 덮개란 이분 그래프에서 모든 간선이 자신과 접한 두 정점 중최소한 하나는 선택하도록 할 때 최소로 선택하는 정점의 수이다. 그니까 하나의 정점을..
https://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2376 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104#include using namespace std;typedef long long ll;const int mod = 1e9+7;const int inf = 0x3c3c3c3c;const l..
https://csacademy.com/contest/round-36/task/tree-nodes-sets/ N p; G[p].push_back(i); } for(int i = 1; i > K; for(int j = 0 ; j > a; oper[i].push_back(a); } } dfs(1, stt); for(int i = 1 ; i
https://www.acmicpc.net/problem/1804 2*B 격자에 음식이 N개 놓여져 있다. K개의 랩을 사용하여 음식을 덮을 때 덮이는 칸의 최소 개수를 구하는 문제이다. 랩은 어느 크기로든 늘리거나 줄일 수 있다. N > K >> B; for(int i = 0 ; i > r >> c; mp[c] = mp[c] | (1
https://www.acmicpc.net/problem/11570 N N; for(int i = 0 ; i > A[i]; cout
https://www.acmicpc.net/problem/14437 정수 S 와 문자열 str 가 입력으로 주어진다. S
http://codeforces.com/contest/822/problem/C n과 k가 주어진다.n은 비행기 티켓의 개수 이다. 각 티켓에는 l,r,c 세개의 정수가 있고 l은 출국일, r은 입국일, c는 티켓 가격이다.범위는 l,r l >> r >> c; v.push_back(ticket{l,r-l+1,c,0}); v.push_back(ticket{r,r-l+1,c,1}); } sort(v.begin(), v.end()); ll ans = infl; for(int i = 0 ; i