본문 바로가기

분류 전체보기327

lazy propagation - 세그먼트 트리 확장 코드의 상당부분은 kks227(라이)님의 코드를 참고했음을 밝힙니다. 기본문제 https://www.acmicpc.net/problem/10999 https://www.acmicpc.net/problem/12844 https://www.acmicpc.net/problem/1395 구간 합을 빠르게 구하기 위해서 prefix 배열을 이용 -> update 등의 다수의 쿼리가 발생했을 때도 구간 합을 빠르게 구하기 위해서 segment tree 사용 -> 구간 update 등 다수의 쿼리가 발생했을 때 구간 합을 빠르게 구하기 위해 lazy배열과 propagation 사용 필요한 것: segment tree, lazy 배열 propagate(node, ns, ne) : add나 val 함수에서의 node에 .. 2019. 9. 18.
BOJ 7535 - A Bug's Life https://www.acmicpc.net/problem/7535 7535번: A Bug’s Life The output for every scenario is a line containing “Scenario #i:”, where i is the number of the scenario starting at 1, followed by one line saying either “No suspicious bugs found!” if the experiment is consistent with his assumption about the bugs’ sexua www.acmicpc.net 각 항이 xor로 묶여있는 2-Sat문제이다. p번 벌레가 q번 벌레와 소통했을 때 둘의 성별이 달라야 한다. 이를 p x.. 2019. 8. 19.
BOJ 4013 - ATM https://www.acmicpc.net/problem/4013 4013번: ATM 첫째 줄에 교차로의 수와 도로의 수를 나타내는 2개의 정수 N과 M(N, M ≤ 500,000)이 차례로 주어진다. 교차로는 1부터 N까지 번호로 표시된다. 그 다음 M개의 줄에는 각 줄마다 각 도로의 시작 교차로 번호와 끝 교차로 번호를 나타내는 2개의 정수가 주어진다. 그 다음 N개의 줄에는 1번 교차로부터 차례대로 각 교차로의 ATM 기기가 보유한 현금의 액수를 나타내는 정수가 각 줄에 하나씩 주어진다. 그 다음 줄에는 두 개의 정수 S와 P가 주어 www.acmicpc.net 중요한 문제라고 생각함. 유니온파인드 말고 SN, sn[MAX] 쓰면 더 쉽다. scc를 나누는데 레스토랑이 있는지, 시작점인지 등등 정보.. 2019. 8. 19.
BOJ 1005 - ACM 크래프트 (위상정렬) https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N 과 건물간의 건설순서규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부터 N번까지 존재한다) 둘째 줄에는 각 건물당 건설에 걸리는 시간 D가 공백을 사이로 주어진다. 셋째 줄부터 K+2줄까지 건설순서 X Y가 주어진다. (이는 건물 X를 지은 다음에 건물 Y를 짓는 것이 가능하다는 의미이다) 마지막 줄에는 백준이가 승리하기 위해 건 www.acmicpc.net 주석에 중요문장이라고 표시한 문장이 다른 곳에서도 종종 쓰인다. #include #include #include #include u.. 2019. 8. 19.

티스토리툴바