해주심 ㄳ
[일반] E랑 F2 풀이좀 설명해주실분
익명(112.187)
2021-10-24 22:09
추천 0
댓글 4
다른 게시글
-
오늘 코포 점수 갱신 언제 되나요?[일반] 익명(175.194) | 21.10.24추천 0
-
시발 A번 틀린거같네 [3][일반] 익명(210.96) | 21.10.24추천 0
-
행렬 + 미분 vs 알고리즘 뭐가 더 중요? [1][일반] 익명(223.38) | 21.10.24추천 0
-
코드포스할까말까고민했는데 이미돌고있네 [1][일반] EN_SA(encludingsalt) | 21.10.24추천 0
-
이거 뭔데 웃긴거지 ㅋㅋㅋ [2][일반] 익명(122.37) | 21.10.24추천 10
-
본인 백준 maze 코드 시간 왤케 많이 걸리는 거임?? [4][일반] 익명(175.196) | 21.10.24추천 1
-
요즘 koi에 [3][일반] 익명(110.70) | 21.10.24추천 0
-
컴파일 에러 정보에 [7][일반] 즈티(heeda0528) | 21.10.24추천 0
-
Kks 227 블로그 따라가면서 다풀면 [4][일반] 익명(180.226) | 21.10.24추천 0
-
800솔브 달성 [7][일반] 익명(175.208) | 21.10.24추천 5
E는 그냥 뒤에서 부터 보면서 DP하면 됨. N이 주어져있고 현재 1~k-1개짜리 덩어리를 만들었으면, k개짜리 덩어리를 만들 수 있는지 보면 됨. 이러면 시간복잡도가 N^2일것 같지만, 실제로 k개의 덩어리가 된다 = 적어도 판에 k(k+1)/2개가 있어야 한다는 의미가 되서, k<=sqrt(2N)만 보면 됨. 그래서 시간복잡도 O(N sqrt(N))
F2는 핵심이 a1 XOR a2 XOR ... ak = value면, ak 이후에 나오는 값중 value는 무시할 수 있다는거임. 그래서 작은거부터 쭉 뽑아가면서 last[value]라는 배열을 만드는데, last[value] = t 가 무슨뜻이냐면 a1 ~ at의 값중 적당한 increasing을 골라서 value를 만들 수 있다는거임. last 배열 갱신은 이진탐색을 이용해서 할 수 있고 총 시간은 5000^2 log (N)이 걸림
https://codeforces.com/contest/1582/submission/132915886
F2 풀이설명 귀찮으니 걍 내 코드 보셈
아 업데이트가 5000logN이 되네... 감사합니다