Generate Tree
#include "testlib.h" #include <vector> std::vector<int> P; int Root(int X) { return X == P[X] ? X : P[X] = Root(P[X]); } void GenTree(int N, std::vector<std::pair<int, int> > &M) { P.resize(N); for (int i = 0; i < N; i++) P[i] = i; M.resize(N - 1); for (int i = 0; i < N - 1; i++) { int u, v; do { u = rnd.next(N); v = rnd.next(N); } while (Root(u) == Root(v)); P[Root(u)] = Root(v); M[i].first = u; M[i].second = v; } } int main(int argc, char *argv[]) { registerGen(argc, argv, 1); int N = 7; std::vector<std::pair<int, int> > E; GenTree(N, E); printf("%d\n", N); for (int i = 0; i < N - 1; i++) printf("%d %d\n", E[i].first, E[i].second); return 0; }
'DM' 카테고리의 다른 글
Generate Connected Graph (0) | 2016.11.07 |
---|---|
Testlib (0) | 2016.11.07 |
Testlib는 Codeforces에서 만든 라이브러리이다.
Generator, Validator, Interactor 그리고 Checker를 만드는 데 사용할 수 있으며, C++ 표준을 따르는 어떤 컴파일러에서 실행시켜도 동일한 결과를 내놓으므로 컴파일러마다 작동이 다른 stdlib의 rand 함수로 만드는 것보다 데이터를 유지보수하기 좋다.
~
Testlib를 사용하려면 공식 GitHub에 들아가서 testlib.h 파일을 클릭한 뒤, 소스를 복사하거나 Raw 버튼을 클릭하여 저장하면 된다. 이후 소스 파일과 같은 폴더에 넣은 뒤, 소스코드의 가장 앞 부분에 #include "testlib.h" 한 줄만 적어주면 Testlib를 사용할 수 있다.
~
Microsoft Visual Studio 2015
Microsoft Visual Studio 2015에서 Testlib를 사용하려고 하면 에러가 두 개 발생한다. (Testlib 0.9.10)
첫 번째 에러는 426번째 줄에서 발생하는 에러로, 407줄~409줄에 있는 다음 부분을 주석처리하면 해결된다.
/* #ifndef _fileno #define _fileno(_stream) ((_stream)->_file) #endif */
두 번째 에러는 va_start와 관련해서 발생하는 에러인데, testlib.h의 가장 앞 부분에 다음을 추가하면 해결된다.
#define _CRT_NO_VA_START_VALIDATION
이 두 가지를 해결하면 Microsoft Visual Studio 2015에서 Testlib를 사용할 수 있다.
~
Generator
generator에서 쓸 수 있는 다양한 함수들이 존재하므로, 직접 testlib.h 파일의 함수들을 하나씩 보거나 많은 예제를 찾아보면서 익히는 것을 권장한다.
아래는 길이가 1 이상 argv[1] 이하인 무작위 수열을 생성하는 generator의 예시이다.
#include "testlib.h" #include <vector> int main(int argc, char *argv[]) { registerGen(argc, argv, 1); int MaxN = atoi(argv[1]); int N = rnd.next(1, MaxN); std::vector<int> A(N); for (int i = 0; i < N; i++) A[i] = i + 1; shuffle(A.begin(), A.end()); printf("%d\n", N); for (int i = 0; i < N; i++) { if (i) printf(" "); printf("%d", A[i]); } printf("\n"); return 0; }
Testlib로 만든 generator는 맨 처음에 registerGen(argc, argv, 1)을 실행해야 한다. 이를 실행하면 인자로 넘어온 값들을 시드로 하여 랜덤함수를 초기화한다. 이 덕분에 generator를 실행할 때 인자를 바꿔주는 것만으로 같은 방법으로 생성된 서로 다른 데이터를 쉽게 만들 수 있다.
'DM' 카테고리의 다른 글
Generate Connected Graph (0) | 2016.11.07 |
---|---|
Generate Tree (0) | 2016.11.07 |
Baekjoon Online Judge 13538
https://www.acmicpc.net/problem/13538
이 문제는 Persistent Segment Tree를 이용하면 효율적으로 해결할 수 있다.
수의 범위가 1~500000이므로 2^19(524288)개의 리프 노드를 만들고, 각 노드는 해당하는 구간에 포함되는 원소의 개수를 들고 있는다.
즉, k번째 Segment Tree의 [l, r) 노드는 1~k번째 원소 중 l 이상 r 미만인 수의 개수이다.
이렇게 트리를 만들면 각 쿼리는 다음과 같은 방법으로 처리할 수 있다.
0. 0번 트리를 만든다. 수열이 비어있으므로 모든 노드는 0을 값으로 갖는다.
1. 새로운 트리를 만든다. 이 트리는 현재까지의 수열에 x를 추가한 트리이고, 이를 N번 트리로 명명한다.
2. R번 트리와 L-1번 트리를 고려한다. 루트로부터 출발해서 x와 xor한 값이 더 큰 방향에 원소가 있으면 해당 방향으로, 없다면 반대 방향으로 움직이는 것을 19번 반복하면 y를 구할 수 있다.
3. N -= k
4. R번 트리와 L-1번 트리를 고려한다. 루트로부터 출발해서 x+1을 찾아가면서, 오른쪽 자식으로 갈 때 R번 트리에서 왼쪽 자식에 포함되는 원소의 개수를 더해주고 L-1번 트리에서 왼쪽 자식에 포함되는 원소의 개수를 빼 주는 것을 19번 반복하면 x보다 작거나 같은 원소의 개수를 구할 수 있다.
5. R번 트리와 L-1번 트리를 고려한다. 루트로부터 출발해서 R번 트리에서 왼쪽 자식에 포함되는 원소의 개수에서 L-1번 트리에서 왼쪽 자식에 포함되는 원소의 개수를 뺀 것이 k 이상이라면 왼쪽 자식으로 이동하고, 아니라면 그 값을 k에서 뺀 뒤 오른쪽 자식으로 이동한다. 이를 19번 반복해서 도착한 노드의 번호가 k번째로 작은 수이다.
전체 시간복잡도는 O(M log x)가 된다.
#include <cstdio> struct node { node *l, *r; int x; } T[11050000], *a[500005]; int Tn, n; void Add(node *p, node *q, int x, int y) { p->x = q->x + 1; if (y < 0) return; if (x >> y & 1) { p->r = T + ++Tn; p->l = q->l; Add(p->r, q->r, x, y - 1); } else { p->l = T + ++Tn; p->r = q->r; Add(p->l, q->l, x, y - 1); } } int Xor(node *p, node *q, int x, int y) { if (y < 0) return 0; if (x >> y & 1 ? p->l->x == q->l->x : p->r->x != q->r->x) return 1 << y | Xor(p->r, q->r, x, y - 1); return Xor(p->l, q->l, x, y - 1); } int Sum(node *p, int x, int y) { if (y < 0) return 0; if (x >> y & 1) return p->l->x + Sum(p->r, x, y - 1); return Sum(p->l, x, y - 1); } int Kth(node *p, node *q, int x, int y) { if (y < 0) return 0; if (p->l->x - q->l->x < x) return 1 << y | Kth(p->r, q->r, x - p->l->x + q->l->x, y - 1); return Kth(p->l, q->l, x, y - 1); } int main() { int i, j, k, m; scanf("%d", &m); for (i = 1; i < 1 << 19; i++) { T[i].l = T + (i << 1); T[i].r = T + (i << 1 | 1); } a[n = 0] = T + 1; Tn = 1 << 20; while (m--) { scanf("%d", &i); switch (i) { case 1: scanf("%d", &i); a[++n] = T + ++Tn; Add(a[n], a[n - 1], i, 18); break; case 2: scanf("%d%d%d", &i, &j, &k); printf("%d\n", Xor(a[j], a[i - 1], k, 18)); break; case 3: scanf("%d", &i); n -= i; break; case 4: scanf("%d%d%d", &i, &j, &k); printf("%d\n", Sum(a[j], k + 1, 18) - Sum(a[i - 1], k + 1, 18)); break; case 5: scanf("%d%d%d", &i, &j, &k); printf("%d\n", Kth(a[j], a[i - 1], k, 18)); break; } } }
'...' 카테고리의 다른 글
ONTAK 2010 Day 7 Generator (0) | 2018.07.17 |
---|---|
BOJ Achievements (0) | 2018.05.17 |
Ubuntu PPTP VPN Server (0) | 2017.12.17 |
Baekjoon Online Judge 1659 (0) | 2016.02.02 |
1 이상 N 이하의 정수에서 i의 빈도수 (0) | 2016.01.27 |