算法竞赛入门经典[紫书]习题笔记(第三章)

紫书第三章习题代码及笔记。主要是想练习下c++的使用,有错误欢迎指出,有可以改进的地方请不吝赐教,多加交流。

练习题
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <stdio.h>
#include <iostream>
#include <string.h>
#define maxn 105
#include <math.h>


//题目1--统计个数[不用数组]

int main(){
int count=0; // count用于计数
float num;
while (scanf("%f", &num) == 1) {
count++;
}
printf("Nums: %d\n", count);
return 0;

}


//题目1--求最大值,最小值,均值[不用数组]
/*
int main(){
int count = 0;
float num, sum=0, min_x, max_x;
while ( scanf("%f", &num) == 1){
if(count == 0){min_x = max_x = num;}
if(num > max_x) max_x = num;
if(num < min_x) min_x = num;
sum += num;
count++;
}
printf("Max:%f Min:%f Ave:%f\n", max_x, min_x, sum/count);
return 0;
}
*/

// 题目1--哪两个数最接近[数组]
/*
int nums[maxn];
int main(){
int num, n = 0;
while (scanf("%d", &num) == 1) {
nums[n] = num;
n++;
}
int min_d = std::abs(nums[0]-nums[1]);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++){
if(j != i){
if(std::abs(nums[i]-nums[j]) < min_d) min_d = std::abs(nums[i]-nums[j]);
}
}
printf("%d\n", min_d);
return 0;
}
*/


// 题目1--第二大的数[数组]
//思路一:先获取数组最大值,在获取去除最大值后的数组,在求最大值
// 获取数组的最大值
/*
float getmax(float arr[], int n);

int main(){
float num, nums[maxn];
int n=0;
// 将输入的数字存入数组nums
while (scanf("%f", &num) == 1){
nums[n] = num;
n++;
}
float max_x = getmax(nums, n);

float newnums[maxn];
int newn = 0;
for(int i=0;i<n;i++){
if(nums[i] != max_x) {
newnums[newn] = nums[i];
newn++;
}
}
float sec_max_x = getmax(newnums, newn);
printf("%f\n", sec_max_x);
}

float getmax(float arr[], int n){
float max_x_arr = arr[0];
for(int i=1;i<n;i++){
if(arr[i] > max_x_arr) max_x_arr = arr[i];
}
return max_x_arr;
}
*/


// 题目1--第二大的数[数组]
// 思路二:冒泡排序
/*
void bubblesort(float A[], int n){
bool sorted = false; // 整体排序标志,首先假定尚未进行排序
while(!sorted){ //在尚未确认已经全局排序之前,逐趟进行扫描交换
sorted = true; // 假定已经排序
for (int i =1; i < n; i++ ){
if (A[i - 1] > A[i]){ // 一旦A[i-1]与A[i]逆序,则
std::swap( A[i-1], A[i]); // 交换之
sorted = false;// 因整体排序不能保证,需要清除排序标志
}
}
n--; // 至此末位元素必然就位, 故可以缩短排序序列的有效长度。
}

}// 借助布尔值标志位sorted, 可以及时提前退出,而不至于总是忙里地做n-1次扫描


int main() {
float num, nums[maxn];
int n = 0;
// 将输入的数字存入数组nums
while (scanf("%f", &num) == 1) {
nums[n] = num;
n++;
}
bubblesort(nums, n);
printf("%f\n", nums[n-2]);
}
*/


// 题目1--方差[数组]

//计算数组方差
/*
float getvar(float arr[], int n);

int main() {
float num, nums[maxn];
int n = 0;
// 将输入的数字存入数组nums
while (scanf("%f", &num) == 1) {
nums[n] = num;
n++;
}
float var = getvar(nums, n);
printf("%f\n", var);
}


float getvar(float arr[], int n){
float sum = 0;
for(int i=0;i<n;i++)
sum += arr[i];
float ave = sum/n;
float p_var;
for (int i = 0; i < n; i++) {
p_var += (arr[i]-ave)*(arr[i]-ave);
}
float var = p_var/(n-1);
return var;
}
*/


// 题目1--不超过平均数的数字个数[数组]
/*
int main() {
float num, nums[maxn], sum=0;
int n = 0;
// 将输入的数字存入数组nums
while (scanf("%f", &num) == 1) {
sum += num;
nums[n] = num;
n++;
}
float ave = sum/n;
int nx = 0;
for(int i=0;i<n;i++){
if(nums[i] <= ave) nx += 1;
}
printf("%d\n", nx);
}
*/

OJ练习
  • [ ] UVa 1585
    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
    #include <stdio.h>
    #include <cstring>
    #include <iostream>
    #include <math.h>
    #include <curses.h>
    #define maxn 85

    char s[maxn];

    int main(){
    int n;
    scanf("%d", &n);
    for(int i=0; i<n;i++){
    scanf("%s", s);
    int n = strlen(s);
    int sum = 0;
    for(int i=0; i<n; i++){
    int count = 0;
    if(s[i] == 'O'){
    count += 1;
    for(int j=(i-1);j>=0;j--){
    if(s[j] == 'X') break;
    count += 1;
    }
    }
    sum += count;
    }
    printf("%d\n", sum);
    }

    return 0;
    }
  • [ ] UVa 1586
    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
    #include <stdio.h>
    #include <cstring>
    #include <iostream>
    #include <math.h>
    #include <curses.h>
    #define maxn 85
    int main(){
    int n;
    scanf("%d", &n);

    char const_s[] = "CHON";
    float const_num[4] = {12.01, 1.008, 16.00, 14.01};

    for (int i = 0; i < n; i++) {
    float sum = 0;
    char s[maxn];
    scanf("%s", s);
    int len = strlen(s);
    for (int j = 0; j < len; j++) {
    if(!isalpha(s[j])) continue;
    for(int m=0; m<4; m++)
    if(s[j] == const_s[m]){
    sum += const_num[m];
    if((j+1)< len && !isalpha(s[j+1])){
    if((j+2)< len && !isalpha(s[j+2])) sum += const_num[m]*((int(s[j+1])-48)*10+int(s[j+2])-48-1);
    else sum += const_num[m]*(int(s[j+1])-48-1);
    }
    }
    }
    printf("%.3f\n", sum);
    }

    return 0;
    }

  • [ ] UVa 1225
    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

    #include <stdio.h>
    #include <cstring>
    #include <iostream>
    #include <math.h>
    #include <curses.h>

    // sprintf is the key to solve the problem.
    /*
    # define maxn 10005
    int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
    int nums[10], nx;

    memset(nums, 0, sizeof(nums));
    scanf("%d", &nx);
    char strnum[maxn];
    for (int j = 1; j <=nx; j++) {
    sprintf(strnum, "%d", j);
    for (int k = 0; k < strlen(strnum); k++) {
    for (int l = 0; l <= 9; l++) {
    if((int(strnum[k])-48) == l) nums[l] += 1;
    }
    }
    }

    for (int m = 0; m < 9; m++) {
    printf("%d ", nums[m]);
    }
    printf("%d\n", nums[9]);
    }
    return 0;
    }

  • [ ] UVa 455
    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
    #include <stdio.h>
    #include <cstring>
    #include <iostream>
    #include <math.h>
    #include <curses.h>
    #define maxn 85
    int main(){
    int times;
    scanf("%d", &times);
    while (times--){
    char s[maxn];
    scanf("%s", s);
    int length = strlen(s);
    for (int T = 1; T < length+1; T++) { // 这里最大周期可以是它本身的!!
    int isans = 1;
    int T_nums;
    if(length%T == 0) {
    T_nums = length/T;
    for (int i = 0; i < T; i++)
    {
    for (int j = 0; j < T_nums; j++) {
    if(s[i] != s[(i+T*j)]){isans = 0;break;}
    }
    }
    }
    else isans=0;
    if(isans)
    {
    printf("%d\n", T);
    break;
    }
    }
    if(times)printf("\n");
    }
    return 0;
    }
击蒙御寇