Happy_2018Summer_Week01

  1. 7-1 一元多项式的乘法与加法运算（20 分）
  2. 7-2 一元多项式求导（20 分）
  3. 7-4 求链式线性表的倒数第K项（20 分）
  4. 7-7 两个有序链表序列的合并（20 分）
  5. 7-11 2n皇后问题(qdulq)（40 分）

7-1 一元多项式的乘法与加法运算（20 分）

设计函数分别求两个一元多项式的乘积与和。

输入格式:

输入分2行，每行分别先给出多项式非零项的个数，再以指数递降方式输入一个多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

输出分2行，分别以指数递降方式输出乘积多项式以及和多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。零多项式应输出0 0。

输入样例:

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

输出样例:

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

题解:

根据多项式的定义:anx叫做多项式：anxn+an-1xn-1+…+a2x2+a1x+ a0(an≠0)的最高次项或首项。an称为首项系数，非负整数 n 叫做多项式的次数。所以不需要担心指数是负数这回事,因为数据并不大,所以可以用数组下标表示指数,数组元素代表系数.

本题第三个点是在系数指数都趋近于最大值的时候,这时候如果执行乘法的话,最大指数会趋近于2000,所以要开一个大于2000的数组.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

typedef long long ll;

int index1[2000],index2[2000];
int ans[5000];

void FUCK1() {
    int cnt = 0;
    for (int i = 0; i <= 1005; i++) {
        if(index1[i]) {
            for (int j = 0; j <= 1005; j++) {
                if(index2[j]) {
                    ans[i + j] += index1[i] * index2[j];
                    if(ans[i + j]) {
                        cnt++;
                    }
                }
            }
        }
    }
    if (!cnt) {
        printf("0 0\n");
        return ;
    }
    int k = 0;
    for (int i = 2010; i >= 0; i--) {
        if (ans[i]) {
            if (!k) {
                printf("%d %d",ans[i],i);
                k++;
            } else {
                printf(" %d %d",ans[i],i);
                k++;
            }
        }
    }
    printf("\n");
    return;
}



void FUCK2() {
    int cnt = 0;
    for (int i = 0; i <= 1005; i++) {
        ans[i] = index1[i] + index2[i];
        if(ans[i]) {
            cnt++;
        }
    }
    if (!cnt) {
        printf("0 0\n");
        return ;
    }
    int k = 0;
    for (int i = 1005; i >= 0; i--) {
        if(ans[i]) {
            if(!k) {
                printf("%d %d",ans[i],i);
                k++;
            } else {
                printf(" %d %d",ans[i],i);
                k++;
            }
        }
    }
    printf("\n");
    return;
}


int main() {
    int fir,sec;
    int ind,coe;
    scanf("%d",&fir);
    for (int i = 0; i < fir; i++) {
        scanf("%d%d",&coe,&ind);
        index1[ind] = coe;
    }
    scanf("%d",&sec);
    for (int i = 0; i < sec; i++) {
        scanf("%d%d",&coe,&ind);
        index2[ind] = coe;
    }
    FUCK1();
    FUCK2();
    
    return 0;
}

7-2 一元多项式求导（20 分）

设计函数求一元多项式的导数。

输入格式:

以指数递降方式输入多项式非零项系数和指数（绝对值均为不超过1000的整数）。数字间以空格分隔。

输出格式:

以与输入相同的格式输出导数多项式非零项的系数和指数。数字间以空格分隔，但结尾不能有多余空格。

输入样例:

3 4 -5 2 6 1 -2 0

输出样例:

12 3 -10 1 6 0

题解:

如果指数为0,那么不需要输出,反之指数*系数 指数-1;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

int main() {
    int soc,ind,k = 0;
    while(scanf("%d %d", &soc, &ind) != EOF) {
        if(soc * ind == 0) {
            continue;
        } else {
            if(!k) {
                printf("%d %d", soc * ind, ind-1);
                k++;
            } else {
                printf(" %d %d", soc*ind, ind-1);
                k++;
            }
        }
    }
    if(!k) {
        printf("0 0");
    }
    return 0;
}

7-4 求链式线性表的倒数第K项（20 分）

给定一系列正整数，请设计一个尽可能高效的算法，查找倒数第K个位置上的数字。

输入格式:

输入首先给出一个正整数K，随后是若干正整数，最后以一个负整数表示结尾（该负数不算在序列内，不要处理）。

输出格式:

输出倒数第K个位置上的数据。如果这个位置不存在，输出错误信息NULL。

输入样例:

4 1 2 3 4 5 6 7 8 9 0 -1

输出样例:

7

太水了,压根不值20分.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

typedef long long ll;
const int INF = 0x7ffffff;

int arr[10000000];

int main(int argc, char *argv[]) {
	int n,num,ans = 0;
	scanf("%d",&n);
	
	while(scanf("%d",&num) && num >= 0) {
		arr[ans++] = num;
	}
	if(n > ans) {
		printf("NULL");
	} else {
		printf("%d",arr[ans - n]);
	}
	
	return 0;
}

7-7 两个有序链表序列的合并（20 分）

已知两个非降序链表序列S1与S2，设计函数构造出S1与S2合并后的新的非降序链表S3。

输入格式:

输入分两行，分别在每行给出由若干个正整数构成的非降序序列，用−1表示序列的结尾（−1不属于这个序列）。数字用空格间隔。

输出格式:

在一行中输出合并后新的非降序链表，数字间用空格分开，结尾不能有多余空格；若新链表为空，输出NULL。

输入样例:

1 3 5 -1
2 4 6 8 10 -1

输出样例:

1 2 3 4 5 6 8 10

题解:

手写链表,排序的思路是从两个链表第一个节点开始比较,如果list1 > list2 list3指向list2的这个结点,然后list2 = list2 -> next,接下来不断用当前所指向的结点比较,知道其中一个list -> next = NULL,然后指向list3 -> next指向另一个链表剩余部分.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>


typedef struct Node {
    int data;
    struct Node* next;
}Node;

Node* Creat() {
    Node* list;
    list = (Node*)malloc(sizeof(Node));
    list -> next = NULL;
    return list;
}

void getList(Node* list) {
    Node* tmp;
    
    int data;
    while (scanf("%d",&data) && data > 0) {
        tmp = (Node*)malloc(sizeof(Node));
        tmp -> data = data;
        tmp -> next = NULL;
        list -> next = tmp;
        list = list -> next;
    }
    return;
}

void ListSort(Node* l1,Node* l2,Node* l3) {
    Node* s1 = l1 -> next;
    Node* s2 = l2 -> next;
    Node* s3 = l3;
    while (s1 != NULL && s2 != NULL) {
        if(s1 -> data > s2 -> data) {
            s3 -> next = s2;
            s3 = s3 -> next;
            s2 = s2 -> next;
        } else {
            s3 -> next = s1;
            s3 = s3 -> next;
            s1 = s1 -> next;
        }
    }
    if(s1 != NULL) {
        s3 -> next = s1;
    } else {
        s3 -> next = s2;
    }
    return;
}



void print(Node* list) {
    list = list -> next;
    if(list == NULL) {
        printf("NULL");
        return ;
    }
    while (list != NULL) {
        if(list -> next == NULL) {
            printf("%d",list -> data);
        } else {
            printf("%d ",list -> data);
        }
        list = list -> next;
    }
    return;
}


int main(int argc, char *argv[]) {
    Node* l1;
    Node* l2;
    Node* l3;
    l1 = Creat();
    l2 = Creat();
    l3 = Creat();
    getList(l1);
    getList(l2);
    ListSort(l1, l2, l3);
    print(l3);
    
    
    return 0;
}

7-11 2n皇后问题(qdulq)（40 分）

给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入格式:

输入的第一行为一个整数n，表示棋盘的大小。 　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

输出格式:

输出一个整数，表示总共有多少种放法。

输入样例1:

4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出样例1:

2

输入样例2:

4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

输出样例2:

0

这道题实质上跟N皇后没有什么区别,仅仅是多了一种棋而已.题解中我写了两种思路.一个是黑白交替放,一个是放完一种颜色再放另一种颜色.

judge函数很常规,就是验证当前行放的列数合不合法.递归函数里面,是枚举所有列,在当前行选中一列然后摆放,用judge判断是否合法,然后同样的思路放另一个颜色的棋子,判断合法后开始下一行的递归.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

int Board[10][10];
int Black_book[10];
int White_book[10];
int n,count;

int judge(int k,int *arr) {
    for (int i = 1; i < k; i++) {
        if (arr[i] == arr[k] || abs(i - k) == abs(arr[i] - arr[k])) {
            return 0;
        }
    }
    return 1;
}
void Put(int k) {
    if (k == n + 1) {
        count++;
        return;
    }
    for (int i = 1; i <= n; i++) {
        Black_book[k] = i;
        if (judge(k,Black_book) == 1 && Board[k][i] == 1) {
            for (int j = 1; j <= n; j++) {
                if (i == j) {
                    continue;
                }
                White_book[k] = j;
                if (judge(k,White_book) == 1 && Board[k][j] == 1) {
                    Put(k + 1);
                }
                White_book[k] = 0;
            }
        }
        Black_book[k] = 0;
    }
    return;
}



void PutWhite(int k) {
    if(k == n + 1) {
        count++;
    }
    for (int i = 1; i <= n; i++) {
        if(Black_book[k] != i && Board[k][i]) {
            White_book[k] = i;
            if (judge(k, White_book)) {
                PutWhite(k + 1);
            }
        }
    }
    
}
void PutBlack(int k) {
    if (k == n + 1) {
        PutWhite(1);
    }
    for (int i = 1; i <= n; i++) {
        if (Board[k][i]) {
            Black_book[k] = i;
            if(judge(k, Black_book)) {
                PutBlack(k + 1);
            }
        }
    }
}


int main(int argc, const char * argv[]) {
    scanf("%d",&n);
    memset(Black_book,0,sizeof(Black_book));
    memset(White_book,0,sizeof(White_book));
    if (n == 0) {
        printf("0\n");
        return 0;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d",&Board[i][j]);
        }
    }
    Put(1);
    printf("%d\n",count);
    return 0;
}
script>