17129번 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유
https://www.acmicpc.net/problem/17129 17129번: 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 첫째 줄에 정보섬 2층의 크기 n과 m이 주어진다. (1 ≤ n,m ≤ 3000, 4 ≤ n×m ≤ 9×106) 이후 n행 m열에 걸쳐 0, 1, 2, 3, 4, 5로만 구성된 Ai,j가 주어진다. Ai,j와 Ai,j+1사이에 공백은 주어지지 않는다. 2, www.acmicpc.net bfs문제이다. 음식이 있는 곳을 다 돌면서 가장 최소의 cnt값만 출력하면 된다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #define S second using namespace std; typede..
16978번 수열과 쿼리 22
https://www.acmicpc.net/problem/16978 16978번: 수열과 쿼리 22 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. www.acmicpc.net 오프라인 쿼리, 세그먼트 트리를 활용하는 문제이다. 오프라인 쿼리를 사용해주는 이유는 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. 이러한 조건이 있기 때문이다. 만약 k = 0이라면 1번 쿼리가 한 번도 적용 안 될 때 출력해야 하는데 온라인 쿼리를 사용한 경우 1번 쿼리..
10165번 버스 노선
https://www.acmicpc.net/problem/10165 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 백준 2170번 선 긋기와 매우매우매우 유사한 문제이다. 단 추가된 것은 원형으로 바뀌었다. 1. 노선을 원형으로 만들지 말고 수직선으로 만든다. 2. a > b일 때 n 이상을 더 추가한다. 예) n = 9이고 a = 5, b = 0일 때 5, 6, 7, 8, 9, 0이 아니라 5, 6, 7, 8, 9, 10으로 한다. 3(가장 중요). 그럼 n = 9..
12844번 XOR
https://www.acmicpc.net/problem/12844 12844번: XOR 크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다. www.acmicpc.net lazy propagation문제이다. XOR특성상 a ^ a = 0 이고 a ^ 0 = 0 이다. 따라서 a를 짝수번 XOR 하면 0이므로 XOR을 안해도 되고 a를 홀수번 XOR하면 XOR을 해야한다. #include #define all(v) v.begin(), v.end() #define INF 2e9 #define F first #def..
13701번 중복 제거
https://www.acmicpc.net/problem/13701 13701번: 중복 제거 문제: N개의 정수 A1, A2, ..., AN 을 읽고, 이들 중에서 반복되는 수를 제외하고 남은 N'개의 수 B1, B2, ..., BN’ 을 입력된 순서대로 출력하시오. 이때, 0 ≤ Ai < 225 = 33554432, i=1,2,…,N. 입력의 개수 N은 1 www.acmicpc.net 비트마스크를 이용한 문제이다. 메모리 초과가 안 나기 위해서 unsigned char를 이용해 메모리를 줄였으며 8개의 비트에 각 정보를 담은(전체 크기 / 8) 만큼의 메로리로 더 줄였다. #include #define l long long #define INF 2e9 #define p pair #define vc ve..
