0822 연습

셋 제작자: sean9892

• A - 동차 수열
• B - 핑크 플로이드
• C - 복도 뚫기
• D - Xor Maximization
• E - 성싶당
• F - 2,3 거듭제곱의 합
• G - XOR과 집합과 트리와 쿼리
• H - 다각형 자르기

 

A: 모든  2x2 부분행렬만 살펴보면 됩니다. 각각의 독립인 위치에 대하여 버블 정렬 느낌으로 2개씩 교환했을 때도 값이 바뀌지 않아야 때문.
https://www.acmicpc.net/source/share/fa847a663c5a45b99ac4074096e15d89

B:MST를 만들어주면 되는걸 알 수 있습니다. MST를 만드는 과정에서 가장 작은 경로를 고르기 때문.
https://www.acmicpc.net/source/share/510077d7aed645fab6b9e1d3e1fbecd6

C:

D:UPD 0822
a 수열의 기저(basis = maximal linear indpendent set)을 만듭니다. 각 수에 대해 59번째 비트부터 차례대로 내려가면서 비트가 켜져 있을 경우 a)기저가 없다 기저로 설정해주고, 탐색 중지, b)기저가 있다, 그 수에 기저를 XOR, 탐색 재개
이 경우 기저의 원소를 적당히 XOR 연산해서 모든 원소를 만들 수 있으니,
높은 비트를 가지는 기저부터 차례대로 XOR 해주면 됩니다. (xor해서 더 커지는 경우 xor)
http://boj.kr/64e639474f3f4e3fa01b31ecf425f70f

E:

F:3으로 나눌 수 있으면 먼저 나눠줍니다.
뺄 수 있는 가장 큰 2의 거듭제곱을 뺐을 때 3의 배수면 그걸 빼주고,
아니라면 그것의 절반을 빼줘서 재귀적으로 풀어나가면 됩니다.
ex) 15 = 3(2+3(1))

이렇게 하면 뒤로 갈 수록 2의 지수가 감소하고, 3의 지수가 증가하는 것이 보장됩니다.
http://boj.kr/6d6bcb2df0944783aff144d872800ac3

G:

H: