Problem Solving

두 정점 사이 경로에 1을 더한다.

dfs를 돌리듯이 지금까지 걸어온 과정들을 기록하면서 다음 노드를 갈 수 있었는가?를 체크하자.

문제 그대로 큐에 넣으면서 시뮬레이션해볼 수 있겠다.

문제를 정리하면 다음과 같다.

비트마스킹적으로 접근해보면, 여러 장난감 상자들의 or 연산결과가 이 되도록 하는 조합의 개수를 찾으면 되는 것 같다.

어... 문제가 상당히 곤란해보인다. ㅋㅋㅋㅋ 첫번째 예제부터 친절해서 망정이지, 저런거 없었으면 당연히 1357번 1등한테 먹이고 3 출력했을 것 같다.

수열에서의 swap연산이 주어지고, 수열의 범위가 주어졌을 때 해당 범위에 의 모든 수가 있는지 묻는 문제이다.

로 나눈 나머지가 같다 = 고른 부분집합의 원소들의 차이가 모두 의 배수이다.

일단 세개를 따로 구하면 되는 것 같다.

자명한 세그먼트 트리 연습 문제이다.