Nexon Youth Programming Challenge(NYPC) 2022 Round 2-B 풀이
1. 비트문자열 특정 규칙으로 만들어지는 길이 $2^i$인 이진문자열 $S_i$가 있다. 구간 $[s, e]$가 있을 때, $S_i$의 $s$ 번째 문자부터 $e$ 번째 문자까지 문자 중에서 1의 개수를 구하는 문제다. 단, 하나의 입력 파일에 최대 20만 개의 테스트 케이스가 들어올 수 있어서 상당히 빠른 시간 안에 문제를 해결해야 한다. 문제 설명에 적힌 규칙과 다른 방식으로 $S_i$를 설명할 수 있다. $S_0$는 "0"이며, $1$ 이상인 $i$에 대해 $S_i$는 $S_{i-1}$에서 0/1을 뒤집은 것과 $S_{i-1}$을 이어 붙인 문자열이 된다. 즉, $S_1$은 "10"이며, $S_2$는 "10"에서 0/1을 뒤집은 "01"에 "10"을 이어 붙인 "0110"이 된다. $S_3$은 "0..
해법
2022. 9. 3. 18:01
공지사항
최근에 달린 댓글
- Total
- 257,047
- Today
- 0
- Yesterday
- 50
링크
TAG
- optimization
- IOI2013
- Splay Tree
- idea
- IOI2014
- USACO
- moore
- BOI 2001
- z-trening
- Tree
- ioi
- Boyer
- Knuth Optimization
- majority
- Algorithm
- vote
- Dijkstra
- Parametric Search
- HackerRank
- BOI
- Segment tree
- Greedy Method
- Dynamic Pramming
- dynamic programming
- IOI2011
- IOI2012
- Boyer-Moore Majority Vote Algorithm
- TRIE
- BOI 2009
- Divide & Conquer