AOJ/數據結構習題集

ALDS1_3_A-Stack.

Description:

Write a program which reads an expression in the Reverse Polish notation and prints the computational result.

An expression in the Reverse Polish notation is calculated using a stack. To evaluate the expression, the program should read symbols in order. If the symbol is an operand, the corresponding value should be pushed into the stack. On the other hand, if the symbols is an operator, the program should pop two elements from the stack, perform the corresponding operations, then push the result in to the stack. The program should repeat this operations.

Input:

An expression is given in a line. Two consequtive symbols (operand or operator) are separated by a space character.

You can assume that +, - and * are given as the operator and an operand is a positive integer less than 106

Output:

Print the computational result in a line.

Constraints:

2 ≤ the number of operands in the expression ≤ 100
1 ≤ the number of operators in the expression ≤ 99
-1 × 109 ≤ values in the stack ≤ 109

Sample Input 1:

1 2 +

Sample Output 1:

3

Sample Input 2:

1 2 + 3 4 - *

Sample Output 2:

-3

Codes:

//#define LOCAL

#include <cstdio>
#include <cstdlib>

#define maxSize 1000
char s[maxSize];
int top, S[maxSize];

void push(int x) {
    S[++top] = x;
}

int pop() {
    --top;
    return S[top+1];
}

int main()
{
    #ifdef LOCAL
        freopen("E:\\Temp\\input.txt", "r", stdin);
        freopen("E:\\Temp\\output.txt", "w", stdout);
    #endif

    int a, b;
    while(scanf("%s", s) != EOF) {
        if(s[0] == '+') {
            a = pop(); b = pop();
            push(a+b);
        } else if(s[0] == '-') {
            b = pop(); a = pop();
            push(a-b);
        } else if(s[0] == '*') {
            a = pop(); b = pop();
            push(a*b);
        } else push(atoi(s));
    }

    printf("%d\n", pop());

    return 0;
}

ALDS1_3_B-Queue.

Description:

For example, we have the following queue with the quantum of 100ms.

A(150) - B(80) - C(200) - D(200)
First, process A is handled for 100ms, then the process is moved to the end of the queue with the remaining time (50ms).

B(80) - C(200) - D(200) - A(50)
Next, process B is handled for 80ms. The process is completed with the time stamp of 180ms and removed from the queue.

C(200) - D(200) - A(50)
Your task is to write a program which simulates the round-robin scheduling .

Input:

n q
name1 time1
name2 time2
...
namen timen
In the first line the number of processes n and the quantum q are given separated by a single space.

In the following n lines, names and times for the n processes are given. namei and timei are separated by a single space.

Output:

For each process, prints its name and the time the process finished in order.

Constraints:

1 ≤ n ≤ 100000
1 ≤ q ≤ 1000
1 ≤ timei ≤ 50000
1 ≤ length of namei ≤ 10
1 ≤ Sum of timei ≤ 1000000

Sample Input:

5 100
p1 150
p2 80
p3 200
p4 350
p5 20

Sample Output:

p2 180
p5 400
p1 450
p3 550
p4 800

Codes:

//#define LOCAL

#include <cstdio>

int head, tail;
#define len 100010
typedef struct pp {
    char name[20];
    int time;
} P;
P Q[len];

void enqueue(P x) {
    Q[tail] = x;
    tail = (tail+1)%len;
}
P dequeue() {
    P x = Q[head];
    head = (head+1)%len;
    return x;
}
int min(int a, int b) {return a<b?a:b;}

int main()
{
    #ifdef LOCAL
        freopen("E:\\Temp\\input.txt", "r", stdin);
        freopen("E:\\Temp\\output.txt", "w", stdout);
    #endif

    int n, q, last = 0;
    scanf("%d%d", &n, &q);
    for(int i=0; i<n; ++i)
        scanf("%s%d", Q[i].name, &Q[i].time);

    head = 0, tail = n;
    while(head != tail) {
        P u = dequeue();
        int x = min(q, u.time);
        u.time -= x; last += x;
        if(u.time) enqueue(u);
        else printf("%s %d\n", u.name, last);
    } 

    return 0;
}

ALDS1_3_C-DoublyLinkedList.

Description:

Your task is to implement a double linked list.

Write a program which performs the following operations:

insert x: insert an element with key x into the front of the list.
delete x: delete the first element which has the key of x from the list. If there is not such element, you need not do anything.
deleteFirst: delete the first element from the list.
deleteLast: delete the last element from the list.

Input:

The input is given in the following format:

n
command1
command2
...
commandn
In the first line, the number of operations n is given. In the following n lines, the above mentioned operations are given in the following format:

insert x
delete x
deleteFirst
deleteLast

Output:

Print all the element (key) in the list after the given operations. Two consequtive keys should be separated by a single space.

Constraints:

The number of operations ≤ 2,000,000
The number of delete operations ≤ 20
0 ≤ value of a key ≤ 109
The number of elements in the list does not exceed 106
For a delete, deleteFirst or deleteLast operation, there is at least one element in the list.

Sample Input 1:

7
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5

Sample Output 1:

6 1 2

Sample Input 2:

9
insert 5
insert 2
insert 3
insert 1
delete 3
insert 6
delete 5
deleteFirst
deleteLast

Sample Output 2:

1

Codes:

//#define LOCAL

#include <cstdio>
#include <cstring>
#include <cstdlib>

struct Node{
    int key;
    Node *prev, *next;
};
Node *nil;

Node* listSearch(int key) {
    Node *cur = nil->next;
    while(cur!=nil && cur->key!=key) cur = cur->next;
    return cur;
}

void init() {
    nil = (Node *)malloc(sizeof(Node));
    nil->next = nil, nil->prev = nil;
}

void printList() {
    Node *cur = nil->next;
    int isf = 0;
    while(1) {
        if(cur == nil) break;
        if(isf++ > 0) printf(" ");
        printf("%d", cur->key);
        cur = cur->next;
    }
    printf("\n");
}

void deletNode(Node *t) {
    if(t == nil) return;
    t->prev->next = t->next;
    t->next->prev = t->prev;
    free(t);
}

void deleteFirst() {deletNode(nil->next);}
void deleteLast() {deletNode(nil->prev);}
void deleteKey(int key) {deletNode(listSearch(key));}

void insert(int key) {
    Node *x = (Node *)malloc(sizeof(Node));
    x->key = key;
    x->next = nil->next, nil->next->prev = x;
    nil->next = x, x->prev = nil;
}

int main()
{
    #ifdef LOCAL
        freopen("E:\\Temp\\input.txt", "r", stdin);
        freopen("E:\\Temp\\output.txt", "w", stdout);
    #endif

    char com[20];
    int key, n, i, size, np, nd;
    size = np = nd = 0;
    scanf("%d", &n);

    init();
    for(i=0; i<n; ++i) {
        scanf("%s%d", com, &key);
        int len = strlen(com);
        if(com[0] == 'i') {
            insert(key);
            ++np, ++size;
        } else if(com[0] == 'd') {
            if(len > 6) {
                if(com[6] == 'F') deleteFirst();
                else if(com[6] == 'L') deleteLast();
            } else {
                deleteKey(key); ++nd;
            }
            --size;
        }
    }
    printList();

    return 0;
}

ALDS1_3_D-AreasOnTheCross-SectionDiagram.

Codes:

#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    stack<int> S1;
    stack<pair<int, int> > S2;
    char ch; int sum = 0;
    for(int i=0; cin>>ch; ++i) {
        if(ch == '\\') S1.push(i);
        else if(ch=='/' && S1.size()>0) {
            int j = S1.top(); S1.pop();
            sum += i-j; int a = i-j;
            while(S2.size()>0 && S2.top().first>j) {
                a += S2.top().second; S2.pop();
            }
            S2.push(make_pair(j, a));
        }
    }

    vector<int> ans;
    while(S2.size() > 0) {
        ans.push_back(S2.top().second); S2.pop();
    }
    reverse(ans.begin(), ans.end());
    cout << sum << endl << ans.size();
    for(int i=0; i<ans.size(); ++i) cout << " " << ans[i];
    cout << endl;

    return 0;
}