第二講 線性結構

02-線性結構2：一元多項式的乘法與加法運算

Description:

設計函數分別求兩個一元多項式的乘積與和。

Input:

輸入分2行，每行分別先給出多項式非零項的個數，再以指數遞降方式輸入一個多項式非零項繫數和指數（絕對值均為不超過1000的整數）。數字間以空格分隔。

Output:

輸出分2行，分別以指數遞降方式輸出乘積多項式以及和多項式非零項的繫數和指數。數字間以空格分隔，但結尾不能有多餘空格。零多項式應輸出0 0。

SampleInput:

4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1

SampleOutput:

15 24 -25 22 30 21 -10 20 -21 8 35 6 -33 5 14 4 -15 3 18 2 -6 1
5 20 -4 4 -5 2 9 1 -2 0

Codes:

//#define LOCAL

#include <cstdio>

#define M 2010
int A[M], B[M], C[M], D[M];

void add() {
    int i, j, f = 0;
    for(i=0; i<M; ++i)
        C[i] = A[i]+B[i];
    for(i=M; i>=0; --i) {
        if(C[i] != 0) {
            if(!f) f = 1;
            else printf(" ");
            printf("%d %d", C[i], i);
        }
    }
    if(f == 0) printf("0 0");
    printf("\n");
}

void mul() {
    int i, j, f = 0;
    for(i=0; i<M; ++i) 
        for(j=0; j<M; ++j)
            D[i+j] += A[i]*B[j];
     for(i=M; i>=0; --i) {
        if(D[i] != 0) {
            if(!f) f = 1;
            else printf(" ");
            printf("%d %d", D[i], i);
        }
    }
    if(f == 0) printf("0 0");
    printf("\n");
}

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

    int n1, n2, i, p, q;
    scanf("%d", &n1);
    for(i=0; i<n1; ++i) {
        scanf("%d%d", &q, &p);
        A[p] = q;
    }
    scanf("%d", &n2);
    for(i=0; i<n2; ++i) {
        scanf("%d%d", &q, &p);
        B[p] = q;
    }

    mul(); add();

    return 0;
}

PAT-1074:Reversing Linked List.

Description:

Given a constant K and a singly linked list L, you are supposed to reverse the links of every K elements on L. For example, given L being 1→2→3→4→5→6, if K = 3, then you must output 3→2→1→6→5→4; if K = 4, you must output 4→3→2→1→5→6.

Input:

Each input file contains one test case. For each case, the first line contains the address of the first node, a positive N (<= 105) which is the total number of nodes, and a positive K (<=N) which is the length of the sublist to be reversed. The address of a node is a 5-digit nonnegative integer, and NULL is represented by -1.

Then N lines follow, each describes a node in the format:

Address Data Next

where Address is the position of the node, Data is an integer, and Next is the position of the next node.

Output:

For each case, output the resulting ordered linked list. Each node occupies a line, and is printed in the same format as in the input.

SampleInput:

00100 6 4
00000 4 99999
00100 1 12309
68237 6 -1
33218 3 00000
99999 5 68237
12309 2 33218

SampleOutput:

00000 4 33218
33218 3 12309
12309 2 00100
00100 1 99999
99999 5 68237
68237 6 -1

Codes:

//#define LOCAL

#include <cstdio>
#include <algorithm>

#define M 100010
struct Node { int d, p; };
Node A[M]; int B[M];

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

    int a, b, c, f, n, i, k, j = 0;
    scanf("%d%d%d", &f, &n, &k);
    for(i=0; i<n; ++i) {
        scanf("%d%d%d", &a, &b, &c);
        A[a].d = b, A[a].p = c;
    }
    
    while(f != -1) { B[j++] = f; f = A[f].p; } i = 0;
    while(i+k <= j) { std::reverse(&B[i], &B[i+k]); i+=k; }

    for(i=0; i<j-1; ++i) printf("%05d %d %05d\n", B[i], A[B[i]].d, B[i+1]);
    printf("%05d %d -1\n", B[i], A[B[i]].d);

    return 0;
}

PAT-1051:Pop Sequence.

Description:

Given a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, ..., N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is 7, we can obtain 1, 2, 3, 4, 5, 6, 7 from the stack, but not 3, 2, 1, 7, 5, 6, 4.

Input:

Each input file contains one test case. For each case, the first line contains 3 numbers (all no more than 1000): M (the maximum capacity of the stack), N (the length of push sequence), and K (the number of pop sequences to be checked). Then K lines follow, each contains a pop sequence of N numbers. All the numbers in a line are separated by a space.

Output:

For each pop sequence, print in one line "YES" if it is indeed a possible pop sequence of the stack, or "NO" if not.

SampleInput:

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

SampleOutput:

YES
NO
NO
YES
NO

Codes:

//#define LOCAL

#include <cstdio>

#define M 1010
int A[M], B[M];

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

    int m, n, k, i, j, t;
    scanf("%d%d%d", &m, &n, &k);
   
    while(k--) {
        for(i=0; i<n; ++i) scanf("%d", &A[i]);
        j = 1, i = t = 0;
        while(i < n) {
            if(A[i] == j) ++i, ++j;
            else if(B[t] == A[i]) ++i, --t;
            else if(t < m-1) B[++t] = j++;
            else break;
        }
        if(i == n) printf("YES\n");
        else printf("NO\n");
    }

    return 0;
}