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: