F같은 애매한 constructive?? 문제는 진짜 너무어렵다 뭔가 답 log2 와 관련이 있을거같은데 몰?루

G는 9명 H는 2명 풀어서 열어보지도 않음


A. 

전체 sum이 합성수이면 전부사용

아니면 홀수인거 하나 배제해서 짝수로 만들어줌


B.

이거 빨리 보이면 개 쉽고 안 보이면 개삽질 할듯

m이 n보다 작아서 가운데에 낑겨도 되는 애가 하나 무조건 존재함

그 애를 가운데에 놓고 성게모양 트리를 만들면됨

약간 constraint로 억지부리는 킹받는 문제같음 ㅋㅋ 


C.

column 두께가 1이면 무조건 YES인건 자명

.X

X. 

이런 모양이 보이면 무조건 안됨(오른쪽 아래 점을 확정불가)

이걸 prefix sum을 이용해서 쿼리당 O(1)로 빠르게 판별하면됨


D.

1 1 1 1 x

x x x x 1 

각각 n-1개씩

쿼리 2(n-1)개 날려주면됨


E.

증명은 못했는데 맞는거같음

그래프를 일단 생각하기 쉽게 MST처럼 트리로 만듬

그래프를 트리로 만들면 생각이 쉬워지는게

각 노드는 무조건 짝수번씩 나와야함 

홀수번 나오면 어떤 간선은 분명히 홀수번 쓰임

추가해줘야하는 쿼리의 최소 갯수는 홀수인 노드 / 2

그리고 경로는 LCA를 이용해서 구하면됨


체감난이도 E>C>D>B>A


퍼플간다! 응애