각 작업을 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],..