나 요리학원 출신임

최대값이 T이고 +A,+B가 가능하다추가로 한번 /2를 할 수 있다 이때 얻을 수 있는 최대값을 구하는 문제다 나누기는 내가 가질 수 있는 최대값에서 나누는게 최적이다그래서 pq를 이용해서 문제를 풀면 된다 pq에 {(나누기 가능여부, 값)}를 넣고 쭉 돌려보면된다!이때 진짜 +A,+B를 하면 시간초과가 나니까A,B를 넣을 수 있는만큼 최대로 넣고 돌면된다! 소스코드12345678910111213141516171819202122232425#include #include #include using namespace std;#define ll long longint t, a, b,ans;bool check[5000050][2];int main() { scanf(" %d %d %d", &t, &a, &b); ..

전에 weeklyps 에서 트리의 지름을 공부할 배운 방법을 이용했다!자세한 설명은 weeklyps에 있는 트리의 지름을 보는게 빠를듯.. ㅎㅎㅎ 정점 x를 기준으로 x의 서브트리에 속하는 최장거리, 안속하는 최장거리를 구해서 비교해주면 far 배열을 채울 수 있다..! 서브트리 속하는건 쉬워서 바로 구할 수 있다 트리의 깊이를 구하듯이 구하면 된다 속하지 않는 경우에는 다시 또 경우를 나눠서 구하면 된다...!자세한 설명은 weeklyps 꼭 가보시길..! 저도 3번읽음 ㅎㅎ다들 열공~~! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #includ..

나무를 심는 비용을 다~~ 구해서 곱하는 문제다비용은 지금 심는 나무와 현재 심어져있는 모든 나무까지의 거리의 합이다 이 문제는 펜윅트리를 2개 만들어서 풀 수 있다 하나는 나무가 (0~200000) 중 몇번째 좌표에 몇개가 있는지 아는 용도고두번째는 (나무의 거리 X 수) 를 담아두는 트리다 어떤 좌표 X에 나무를 심는다고 가정하면 우리는 비용을 2가지 작업으로 구할 수 있다. 1) X보다 큰 좌표에 나무가 심어져 있을 때 = (심어진 나무의 거리 합) - (현재 좌표)X(심어진 나무의 수) 2) X보다 작은 좌표에 나무가 심어져 있을 때 = (현재 좌표)X(심어진 나무의 수) - (심어진 나무의 거리 합) 이렇게 하면 비용을 구할 수 있다!트리로 만들어 두면 시간안에 충분히 할 수 있다!근데 문제를 ..

중앙값은 말 그대로 중앙에 있는 값이다K개 중에서 (K+1)/2번째 에 있는 값을 구하면 된다 이 문제는 세그먼트트리로 풀 수 있다.온도가 0~65536 까지니까 넉넉하게 66666까지 잡고온도가 측정될 때 마다 tree에서 온도를 +1 해준다그리고 K개 이상이면 i-k번째를 -1 하고 중앙값을 찾는다! - 세그먼트트리에서 K번째를 찾기 위해서는 나의 왼쪽 자식인 tree[node*2]와 값을 비교해보면 된다만약 K가 같거나 작다면 왼쪽에 있는 것이니까 왼쪽으로가고아니라면 오른쪽으로 가는데 K에서 왼쪽만큼을 빼고 가야한다!그래야 전체적으로 볼때 K번째를 찾을 수 있다. 소스코드123456789101112131415161718192021222324252627282930313233343536373839404..

전에 공장 문제에서 iarr[j]인 수를 찾는 것을 했다.이 문제는 i arr[k] 이므로 j를 기준으로1. i arr[j]2. j 0; i -= (i&-i)) ret += arr[i]; return ret;}int sum(vector&arr, int s, int e) { return _sum(arr, e) - _sum(arr, s - 1);}void update(vector&arr, int x, int val) { for (int i = x; i

각 작업을 1번부터 N번까지 한번에 1초씩 실행시킬 때, 각 작업이 언제 완료되는지 구하는 문제다.이 문제는 작업의 양이 적은 순으로 보면 된다. 직접 써보면 규칙을 찾을 수 있다.총 걸린 시간 - 내 뒤에 남은 작업을 하면 내가 끝나는 시간을 알 수 있다..! 이 때 총 걸린 시간은 if(현재 작업 시간 != 이전 작업 시간)==> 이전에 총 걸린 시간 + 남은 작업*(현재 작업의시간 - 이전 작업의 시간)이다 이것만 안다면 인덱스 트리로 문제를 풀 수있다..! 소스코드123456789101112131415161718192021222324252627282930313233#include #include using namespace std;#define ll long long#define MAXN 1000..

2차원 펜윅트리로 풀 수 있는 문제다.펜윅트리를 2차원으로 생각하면 x축으로 펜윅트리가 있고 그 x축을 가진 y축 펜윅트리가 있다고 생각하면 편하다 업데이트와 합을 구할 때는 2중 포문으로 x축을 먼저 업데이트 해주고 그에 맞게 y축을 업데이트 해주면 된다 (a,b) ~ (x,y) 에 대한 합을 구하는건 그림을 그려보면 이해하기 쉽다(x,y) 까지의 합에서 - (a-1,y) - (x,b-1) + (a-1,b-1)을 하면 원하는 구간이 나온다! 그림으로 색칠해보는 것이 이해하기 쉬운 것 같다 소스코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #inc..

문제를 읽고 해석해보면 사이클이 아닌 정점을 찾는 문제다SCC를 이용해서 풀었다. 처음 입력 받을 때 자기자신으로 간선이 있으면 self배열을 통해 체크했다SCC를 찾는 dfs를 돌면서 scc크기가 1이고 !self[x]면 답이다~! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465#include #include #include #include #include #include #include using namespace std;#define MAXN 100010stack ST;int t, n, low[MAXN], num[MAXN],..

문제가 처음에 이해하기 어려웠다3과목을 시험보는데 A가 B보다 모든과목을 잘보면 '대단한 학생'C라는 학생보다 '대단한 학생'이 한명도 없다면 '굉장한 학생' 이다 처음에 세그먼트 트리를 2개 만들어서 비교하려했는데 실패했다 ㅎㅎ 3과목이라 조건이 3가지이기 때문에 아이디어를 잘 떠올려야 한다 문제를 푸는 방법은1. 첫번째 등수 기준으로 정렬을 한다2. 세그먼트 트리를 만든다. 이 때 트리는 최소값 트리다3. 트리의 i번째에는 두번째 과목을 i등한 사람의 3번째 과목 등수를 넣는다4. 0~n-1까지 for문을 돌며 두번째 과목 등수까지의 값이 3번째 등수 값보다 크다면 이학생은 굉장한 학생이다! 이렇게 3가지 조건을 다 만족시켜주게 트리를 만들면 되는데.... 어렵다! 소스코드123456789101112..

N 개의 정점이 있고 0번에서 1번 까지의 최단거리를 구하는 문제다이 때 가 간선은 가중치를 2개 가진다.최단거리는 0번부터 1번 까지의 1번가중치 합 X 2번가중치 합 이다. 처음에 완탐인줄알고 백트래킹했는데 생각해보니 최악일 때 20!이다..! 문제를 푸는방법은 그냥 다익스트라를 쓰면 된다 ㅋㅋpq에 (가중치1의 합, 가중치2의 합)을 추가로 넣어가면 쉽게 풀 수 있다! 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include #include #include using namespace std;int n, ans = 1e9;bool check[22]..