본문 바로가기

알고리즘/코드포스44

codeforces 613 div2 D - Dr. Evil Underscores (분할정복) https://codeforces.com/contest/1285/problem/D 코포에서 분할정복 처음 풀어봐서 코드만 남겨둠 최대 1e5개의 숫자를 입력받는다. 이 숫자들과 임의의 수 X를 xor할 때 가장 큰 ai xor X의 값이 가장 작도록 X를 구해라 코드로 대체 #include #include #include #include #include #include #include #define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); using namespace std; const int MAX = 1e5 + 5; int n, a[MAX]; int minV(int st, int en, int bt) { int mid = -1; for (.. 2020. 1. 11.
codeforces #612 div2 D - Numbers on Tree (그래프, 수학, 구현) https://codeforces.com/contest/1287/problem/D 실패할 조건을 찾은데서 그친 문제. 시험볼 당시엔 좀만 보면 풀 수 있을 것 같다고 생각했지만, 꽤 오래 생각해봐도 못풀었다. 최대크기 2000의 트리가 주어진다. 각 정점마다 a[i]값을 갖는다. (이 값은 주어지지 않는다. 찾아내야 함) 이 때, 각 정점이 루트가되는 서브트리에서 현재 정점의 a값보다 작은 a값을 갖는 정점들의 수를 c값이 주어질때 가능한 a배열을 구해라. 위->아래, 왼쪽->오른쪽 순서대로 각 정점 번호가 1,2,3,4,5이다. (오른쪽 리프노드가 5번정점이다.) 크게 쓰인 수가 a값이고 괄호 안의 값이 c값이다. 1. 실패조건 각 정점을 루트로 하는 서브트리의 크기를 sz[i]라고 하자. 그러면 c[.. 2020. 1. 7.
Educational codeforces #69 div2 D - Yet Another Subarray Problem (dp) https://codeforces.com/contest/1197/problem/D 까다로운 dp문제 최대 3e5개의 숫자 배열이 주어진다. 연속된 부분수열 a[l..r]의 비용이 다음과 같을 때, 그 최대값을 구해라. (빈 부분수열의 비용은 0이다. 따라서 답의 최댓값은 0이다.) i번째에서 끝나는 연속된 부분수열은 다음 네 가지 경우로 나눌 수 있다. 첫번째 경우: 0 두번째 경우: a[i]-k 세번째 경우: 네번째 경우: psum(0,i)-k 이걸로 for문 디피하면된다. #include #include #include #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); using namespace st.. 2020. 1. 5.
codeforces #610 div2 B2 - K for the Price of One (구현) https://codeforces.com/contest/1282/problem/B2 빡구현 초기 돈 p와 세트로 살 수 있는 묶음단위 k, 최대 2e5개의 물품 가격이 주어질 때, 최대한 많은 물품을 구하는 경우 몇개를 사는지 구하는 문제. 한번 물건을 살 땐 단 한개를 사거나 딱 k개를 사야 한다. k개 묶음을 살 땐 가장 비싼 물품에 대해만 돈을 내면 된다. 돈 6, 묶음단위 3, 가격 2 3 4 5 7 8이 주어질 때를 생각해보면.. (초기돈은 신경쓰지 말자) 물건 1개 살 때 -> (2) 가격:2 물건 2개 살 때 -> (2),(3) 가격:5 -> 일단 신경쓰지 않는다. 더 싼 값으로 더 많이 살 수 있기 때문. 물건 3개 살 때 -> (2,3,4) 가격:4 물건 4개 살 때 -> (2),(3,4.. 2019. 12. 30.

티스토리툴바