2022. 9. 4. 23:40ㆍPS/Problem Solving
연습 주기를 바꿨습니다.
월화수목 셋은 4문제, 금토일 셋은 6문제
셋 제작자: pentagon03
A. dfs + 에라토스테네스의 체
B. 우선순위큐로. 이를 구조화하면 다익이라고 하는데 다익 생각 안 나도 우선순위큐 쓰는게 당연해 보입니다
C. Step 1 원문을 쉬프트하는게 아니라, 거꾸로 암호문을 쉬프트합시다
Step2: 원문의 pi배열이 그대로이므로 각 쉬프트마다 빠르게 kmp를 쓸 수 있습니다~
D. Step1: 한 번 움직일 때 경로 상에 있는 모든 경유 점을 방문하는게 이득입니다. 즉 (start,start)구간에서 한 번 움직일 때마다 구간의 길이가 1씩 늘어나는 방식으로 움직입니다. 가로등 끄기 문제와 유사
Step2: dp(s,e): s~e 구간을 둘러봤고 현재 e에 있을 때 전체 구간을 커버할때까지 남은 경로값으로 정의합시다
Step3: 전이할 때 현재 위치에서 다음으로 움직이는 만큼, 남은 움직임 (N-1-경로의 길이)개에 경로값이 추가되므로 개수에 곱해서 더해주면 됩니다. s<e라 가정하면 dp(s,e) = min( dp(다음 구간) + 움직인 거리 x (n-1-현재구간길이) )
E: 펜윅 + PST. pre[i]를 A[i]와 같은 값을 가지는 수열의 바로 전 인덱스라고 하자. (없으면 0)
l,r,k 쿼리가 주어졌을 때 l<=i<=r에 대해 어떤 구간 s,e에서 s<=A[i]<=e이고 pre[i]<l인 i의 개수를 빠르게 새주면 된다.
pre[i]를 바깥축, i를 PST의 시간축, A[i]를 PST의 노드축으로 하면 빠르게 구할 수 있다.
'PS > Problem Solving' 카테고리의 다른 글
[BOJ 1006] 습격자 초라기 "컷" (1) | 2022.11.07 |
---|---|
VS Code C/C++/Python 설정 방법 - PS를 위한 (3) | 2022.10.22 |
[서평] 백엔드를 위한 GO 프로그래밍 (4) | 2022.08.28 |
0826 연습 (0) | 2022.08.26 |
0824 연습 (0) | 2022.08.24 |