도수를 mid값으로 생각해보자 최대 32번 봐야하고 볼때마다 NlogN연산을 한다고 생각해보자 mid값까지의 도수 중 선호도가 높은 N개를 정해보는 것이다 이분탐색을 통해 찾으면 되지만 오래걸린다! 다른사람들은 pq를 통해 풀었는데 그럼 빠르다..!! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 #include #include #include #include using namespace std; #define ll long long ll n,m,k; vector vt; bool check(ll mid){ vector temp; for(int i..
거꾸로 생각하면 쉽게 풀 수 있다 시프트게 전체가 되므로 그냥 시작점을 옮겨보면 된다 시작점을 기준으로 k칸 뒤에 값을 더해주면 되고 오른쪽 왼쪽 시프트를 할때는 시작점을 움직여보자! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include using namespace std; #define ll long long int n,q,s; ll arr[200020]; int main(){ cin>>n>>q; for(int i=0;i>arr[i]; for(int i=0;i>x; int a,b; if(x==1){ cin>>a>>b; a--; arr[(s+a)%n]+=b; } else if(x==2){ ..
DP로 풀 수 있는 문제다! d[N*M]로 테이블을 잡아보자 d[pos] = 계산값 + d[pos+|d|]로 칸에서의 최대값을 저장하며 풀어나가보자 이 때 최대값이 음수값으로 나올 수 있으므로 inf값을 잘 설정해야한다 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include #include #include #include using namespace std; #define ll long long const int SIZE = 200005; ll inf = 1e12; ll d[SIZE]; ll arr[SIZE]; int..
생각을 결국 떠올리지 못한 문제다!! 한번 2진수로 생각을 해보자 N -> 0까지 갈 예정이다 그럼 내가 0번째 비트가 1이라면 사라지게 할 방법이 없다 그래서 뒤로 한칸 밀어버려야한다(곱하기) 만약 1번째 비트가 1이라면 결국 2라는 값이 포함된다는 말이고 2를 빼면 된다는 말이다(빼기) 만약 0,1비트가 다 0이면 계속 앞으로 땡겨오자(나누기) 그럼 결론적으로 10^13 => 2^45승 정도의 비트를 이런식으로 다 처리하면 된다 N부터 거꾸로 보기때문에 반대로 연산자를 담아주자 0번째 비트가 1인경우,0인경우를 다 생각해보면 어떻게해도 99번을 넘지 않는다 신기하고 쉬워보이지만 나에게는 처음에 어려운 문제였따..!! 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ..