역시나 오늘도 문제 조건을 빼먹어서 틀렸다 ㅎㅎ 굿 곰은 1000마리 까지 들어오고 차이는 1백만 까지 들어온다그럼 다 set에 넣고 확인해보면 된다 1. 먼저 set을 하나 만들어 주자2. 곰의 위치 A[i]를 받자3. set에서 A[i]-d에 대한 lower,upper_bound를 확인하자4. lower는 같거나 && A[i]+d보다 같거나 커야한다5. upper는 A[i]+d보다 같거나 크고 s.end()여야 한다6. 만약 조건에 맞으면 출력 ㄱㄱ 하고 set.insert7. 조건 틀리면 앞에서부터 찾아야 하므로 set 다 뒤지면서 똑같이 ㄱㄱ8. 이 때 A[i]보다 같거나 커야한다 모든 위치는 ㅎㅎ(빼먹으면 틀림) 소스코드123456789101112131415161718192021222324252..
문제를 읽어보면 최대값은각 정점에서 가장 먼 정점과의 거리 중 최소값이다 트리의 지름 공부할 때 배워둔각 정점에서 가장 먼 거리를 구하면 된다 ㅎㅎ유용하게 쓰이는 것 같다 소스코드12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include #include using namespace std;const int MAXN = 1e5 + 5;vector Graph;bool check[MAXN];int n, dist[MAXN], dist2[MAXN], far[MAXN]; void dist_dfs(int x) { check[x] = true; for (int i = 0; i
벡터 정렬 잘못해서 계속 틀렸다 굿사소한거로 매일 틀린다 .. 이 문제는 최소 가격차가 D미만이면 된다그럼 가격대로 정렬시키고 D미만인 경우만 다 더해보면 된다부분합으로 미리 구해도 괜찮고 그냥 하나하나 보면서 앞에는 빼고 뒤는 더해도 괜찮다벡터 정렬할 때 1베이스로 할거면 begin() +1 ~ end() 까지 하자..end()+1로 계속 하고있었는데 70퍼 까지 가길ㄹ ㅐ 오타찾았는데... 나중에야 찾았다.. 소스코드123456789101112131415161718192021#include #include #include using namespace std;#define ll long longconst int MAXN = 1e5 + 3;ll ans, temp;int n, d, l, r;int main..
너무너무너무너무너무너무너무 많이 틀린 문제다틀린 이유는 mod를 잘못써서... 입력이 5000만이기 때문에 그대로 입력받고 하라는대로 하면 시간초과다10억을 log2로 해도 30정도 되기 때문에 미리 구해놓아야 한다 그리고 모듈러를 잘써야한다아직도 잘 모르겠지만 출력해야 할 답을 계속 모듈러 했더니 틀리고마지막에만 하니 맞았따.. 모듈러 초보에겐 너무나 어려운 문제다 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include using namespace std;#define ll long longconst ll mod = 1e9 + 7;int n;ll A, D, H, MA, MD..
트라이 하다보니 재밌다 ㅋㅋㅋ이 문제는 트라이를 그려보면 쉽다 먼저 트라이를 그릴 때 처음 입력받는 N개는 지울 수 있는 변수 del을 true로 넣어준다 두번째로 입력받는 M개는지울 수 없으므로 del = false로 놔준다 그럼 이제 트라이를 모두 돌아보며 지울 수 있는지 없는지 판단하자지울 수 있는 조건은 1. del이 참일 때 지울 수 있따 이 때는 *를 쓴다고 생각해 return 해준다2. del이 거짓이여도 단어의 끝부분이여서 vaild==true일 때 지울 수 있다 한번 쭉돌면 답이 나온다~ 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#inc..
처음에 그리디라고 생각했는데 틀렸다이 문제 메모리가 500메가라서 dp[10000][10000]를 잡고dp를 해도 통과한다 그리고 q가 100이라서 시간도 많이 안드나보다 테이블을 d[l][r]로 잡고l~r까지 탈출시킬 때 최소값 이라고 생각하고 돌리자그리고 q명의 죄수를 미리 set에 넣어두자함수에서 l~r까지 보다가 만약 set에 있는 k라는 값을 만난다면(r-l) + d[l][k-1] + d[k+1][r]을 구하러 가보자그리고 ret값은 1e9로 잡아두고 만약 죄수를 아무도 못만나면0을 리턴해줘야 식에 맞게 답을 구할 수 있다이렇게 다 해보면 나온다! 소스코드123456789101112131415161718192021222324252627282930313233#include #include #inc..
세그먼트트리에서 K번째를 찾는 유형의 문제200만개의 배열을 미리 잡아두고 쿼리가 1로 들어오면 그 숫자를 인덱스로 보고배열에서 인덱스를 찾아가 1업데이트 시켜준다세그먼트트리는 합으로 만들어준다 쿼리가 2라면 K번째를 찾아가자..! 그리고 -1로 업데이트해서 삭제시킨다 소스코드1234567891011121314151617181920212223242526272829303132333435363738#include #include #include #include using namespace std;const int MAXN = 2000020;int n;void update(vector&tree, int node, int start, int end, int index,int val) { if (index end..
조합으로 풀 수 있다1부터 n까지 2^k * nCk를 하면 된다다 풀고보니 규칙이 있다3^n -1... 소스코드12345678910111213141516171819202122232425262728293031323334353637#include using namespace std;#define ll long longconst int MAXN = 1e5 + 2;const ll mod = 1e9 + 7;ll fact[MAXN],ans,n;ll mypow(ll x, ll y) { if (!y) return 1; if (y & 1) return x*mypow(x, y - 1) % mod; return mypow((x*x) % mod, y / 2) % mod;}int main() { fact[0] = 1; for ..
트리를 높이 그리면 규칙을 찾을 수 있다테두리를 쭉~ 제일크게 1개로 감싸보자그럼 안쪽에는 [나의 높이-2]*2 개가 필요하다는 것을 알 수 있다물론 높이가 2 이상일 때 부터 그리고 그 다음에는 1 + 이전에 필요했던것 + [나의 높이-2]*2 개이런 식으로 계속 간다!미리 60까지 구해두자! 소스코드1234567891011121314#include using namespace std;#define ll long longll d[66];int main() { int n; scanf(" %d", &n); d[0] = d[1] = 1; d[2] = 3; ll sum = d[0] * 2; for (int i = 3; i
어렵고 어렵고 어려운 트라이 문제다트라이는 언제나 어렵다 트라이 그림을 그려보면 대충 문제 풀 수 있는 방법이 나온다근데 처음에 짠 코드는 답도 잘나왔는데 계속 틀렸다. ㅎㅎ 단어를 다 입력 해주고 다시 하나하나 보며 각 단어마다 몇번 눌러야 하는지 세주면 된다 세야하는 경우는1) 루트일때2) 길이 2개 이상일 때3) 가는 도중에 끝나는 단어를 포함할 때 이다 트라이를 만들 때 NULL인 곳에 새롭게 동적할당 하면서 branch++ ! 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include using namespace std;const in..