0901 금토일 연습

연습 주기를 바꿨습니다.

월화수목 셋은 4문제, 금토일 셋은 6문제

 

셋 제작자: pentagon03

• A - 산업 스파이의 편지
• B - 해킹
• C - 시저 암호
• D - 보안 업체
• E - 수열과 쿼리 14
• F - 여우 퀴즈

 

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의 노드축으로 하면 빠르게 구할 수 있다.