AOJ/堆与动态规划习题集

ALDS1_9_A-CompleteBinaryTree.

Codes:

//#define LOCAL

#include <cstdio>

int parent(int i) { return i/2; }

int left(int i) { return i*2; }

int right(int i) { return i*2+1; }

int main()

{

	#ifdef LOCAL

		freopen("E:\\Temp\\input.txt", "r", stdin);

		freopen("E:\\Temp\\output.txt", "w", stdout);

	#endif

	int i, n, A[300];

	scanf("%d", &n);

	for(i=1; i<=n; ++i) scanf("%d", &A[i]);

	for(i=1; i<=n; ++i) {

		printf("node %d: key = %d, ", i, A[i]);

		if(parent(i) >= 1) printf("parent key = %d, ", A[i/2]);

		if(left(i) <= n) printf("left key = %d, ", A[i*2]);

		if(right(i) <= n) printf("right key = %d, ", A[i*2+1]);

		printf("\n");

	}

	return 0;

}

ALDS1_9_B-MaximumHeap.

Codes:

//#define LOCAL

#include <cstdio>

int i, n, A[500010];

void swap(int &a, int &b) {

	int t = a;

	a = b; b = t;

}

void maxHeapify(int a) {

	int l = a*2, r = a*2+1, maxn;

	if(l<=n && A[l]>A[a]) maxn = l;

	else maxn = a;

	if(r<=n && A[r]>A[maxn]) maxn = r;

	if(maxn != a) {

		swap(A[maxn], A[a]);

		maxHeapify(maxn);

	}

}

int main()

{

	#ifdef LOCAL

		freopen("E:\\Temp\\input.txt", "r", stdin);

		freopen("E:\\Temp\\output.txt", "w", stdout);

	#endif

	scanf("%d", &n);

	for(i=1; i<=n; ++i) scanf("%d", &A[i]);

	for(i=n/2; i>=1; --i) maxHeapify(i);

	for(i=1; i<=n; ++i) printf(" %d", A[i]);

	printf("\n");

	return 0;

}

ALDS1_9_C-PriorityQueue.

Codes:

//#define LOCAL

#include <cstdio>

#define M 2000000

#define I (1<<30)

int i, n, A[M];

void swap(int &a, int &b) {

	int t = a;

	a = b; b = t;

}

void maxHeapify(int a) {

	int l = a*2, r = a*2+1, maxn;

	if(l<=n && A[l]>A[a]) maxn = l;

	else maxn = a;

	if(r<=n && A[r]>A[maxn]) maxn = r;

	if(maxn != a) {

		swap(A[maxn], A[a]);

		maxHeapify(maxn);

	}

}

int extract() {

	int maxv;

	if(n < 1) return -I;

	maxv = A[1]; A[1] = A[n--];

	maxHeapify(1);

	return maxv;

}

void increaseKey(int i, int key) {

	if(key < A[i]) return;

	A[i] = key;

	while(i>1 && A[i/2]<A[i]) {

		swap(A[i], A[i/2]);

		i /= 2;

	}

}

void insert(int key) {

	++n;

	A[n] = -I;

	increaseKey(n, key);

}

int main()

{

	#ifdef LOCAL

		freopen("E:\\Temp\\input.txt", "r", stdin);

		freopen("E:\\Temp\\output.txt", "w", stdout);

	#endif

	int key;

	char com[10];

	while(1) {

		scanf("%s", com);

		if(com[0]=='e' && com[1]=='n') break;

		if(com[0] == 'i') {

			scanf("%d", &key);

			insert(key);

		} else printf("%d\n", extract());

	}

	return 0;

}

ALDS1_10_A-FibonacciNumber.

Codes:

//#define LOCAL

#include <cstdio>

int main()

{

	#ifdef LOCAL

		freopen("E:\\Temp\\input.txt", "r", stdin);

		freopen("E:\\Temp\\output.txt", "w", stdout);

	#endif

	int i, n, F[50];

	F[0] = 1, F[1] = 1;

	scanf("%d", &n);

	for(i=2; i<=n; ++i)

		F[i] = F[i-1]+F[i-2];

	printf("%d\n", F[n]);

	return 0;

}

ALDS1_10_C-LongestCommonSubsequence.

Codes: