Intro
从入门到入土系列之 PAT 甲级 题库快乐🤣启动。
长期更新ing~
1001 A+B Format
Analysis
题目意思比较简单，给俩数，相加算结果，然后输出的时候每三位一个,隔开，并且负数得在开头输出-。
按照题目给出的数字范围：$-10^6 \le a,\ b \le 10^6$，所以可以直接使用int型变量进行相加，然后在输出之前在做数位拆分即可。
Code
1 |
|
贴个 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
using namespace std;
int main() {
int a, b, c;
cin >> a >> b;
c = a + b;
if(c < 0) {
cout << '-';
c = -c;
}
string str = to_string(c), tmp;
int cnt = 0;
for(int i = str.length() - 1; i >= 0; i--) {
tmp.push_back(str[i]);
cnt++;
if(cnt == 3) {
if(i != 0) tmp += ',';
cnt = 0;
}
}
reverse(tmp.begin(), tmp.end());
cout << tmp;
return 0;
}
不过换个思路，这个题还能更简单：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
int main() {
int a, b, c;
cin >> a >> b;
c = a + b;
if(c < 0) {
cout << '-';
c = -c;
}
if(c >= 1000000) printf("%d,%03d,%03d", c / 1000000, c % 1000000 / 1000, c % 1000);
else if(c >= 1000) printf("%d,%03d", c / 1000, c % 1000);
else printf("%d", c);
return 0;
}
1002 A+B for Polynomials
Analysis
此题是 ZJU 数据结构课程里面的例题了，而且还只是一半的内容，算法思想不难（毕竟只是初中数学的水平，我丢😅），先按照链表来做吧，后面在看看能不能尝试其他方法。一开始偷懒没有将结果构造成一个新的链表，发现测试点5无法通过，改了一会，还是不选择偷懒了...
Code
method 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
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/*
test point 5, like this:
2 1 2.4 0 3.2
3 2 2.4 1 2.4 0 -3.2
*/
typedef struct Polynode* Polynomial;
struct Polynode {
int expo;
double coef;
Polynomial link;
};
Polynomial ReadPoly();
Polynomial Add(Polynomial P1, Polynomial P2);
void Print(Polynomial PP);
int GetNum(Polynomial P);
void Attach(double c, int e, Polynomial *pRear);
int main(int argc, char const *argv[]) {
Polynomial P1 = ReadPoly();
Polynomial P2 = ReadPoly();
Polynomial PP = Add(P1, P2);
int number = GetNum(PP);
if(number) {
printf("%d ", number);
Print(PP);
} else {
printf("%d\n", number);
}
return 0;
}
Polynomial ReadPoly() {
int K;
scanf("%d", &K);
Polynomial P, rear;
P = (Polynomial)malloc(sizeof(struct Polynode));
P->link = NULL;
rear = P;
int e;
double c;
while(K--) {
scanf("%d %lf", &e, &c);
Attach(c, e, &rear);
}
return P;
}
Polynomial Add(Polynomial P1, Polynomial P2) {
Polynomial p1 = P1->link, p2 = P2->link, p, rear;
p = (Polynomial)malloc(sizeof(struct Polynode));
p->link = NULL;
rear = p;
double sum;
while(p1 && p2) {
int temp = p1->expo - p2->expo;
if(temp > 0) {
Attach(p1->coef, p1->expo, &rear);
p1 = p1->link;
} else if(temp == 0) {
sum = p1->coef + p2->coef;
if(sum) {
Attach(sum, p1->expo, &rear);
}
p1 = p1->link;
p2 = p2->link;
} else {
Attach(p2->coef, p2->expo, &rear);
p2 = p2->link;
}
}
if(p1) {
rear->link = p1;
}
if(p2) {
rear->link = p2;
}
return p;
}
void Print(Polynomial PP) {
Polynomial P = PP->link;
while(P) {
if(P->link == NULL) {
printf("%d %.1lf\n", P->expo, P->coef);
} else {
printf("%d %.1lf ", P->expo, P->coef);
}
P = P->link;
}
}
int GetNum(Polynomial P) {
Polynomial p = P->link;
int ret = 0;
while(p) {
ret++;
p = p->link;
}
return ret;
}
void Attach(double c, int e, Polynomial *pRear) {
Polynomial P;
P = (Polynomial)malloc(sizeof(struct Polynode));
P->coef = c;
P->expo = e;
P->link = NULL;
(*pRear)->link = P;
*pRear = P;
}
用 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
using namespace std;
typedef struct Node* List;
typedef struct Node* PtrtoNode;
struct Node {
int exp;
double coe;
PtrtoNode next;
Node() { next = nullptr; }
Node(int _exp, double _coe) {
exp = _exp;
coe = _coe;
next = nullptr;
}
};
List createlist(int node_num) {
int exp;
double coe;
List head = new Node;
List L = head;
while(node_num--) {
scanf("%d %lf", &exp, &coe);
head->next = new Node(exp, coe);
head = head->next;
}
head = L;
L = L->next;
delete(head);
return L;
}
int main() {
int k, exp;
double coe;
scanf("%d", &k);
List L, L1, L2;
L1 = createlist(k);
scanf("%d", &k);
L2 = createlist(k);
L = new Node;
List tmp = L;
while(L1 && L2) {
if(L1->exp == L2->exp) {
if(L1->coe + L2->coe != 0) {
L->next = new Node(L1->exp, L1->coe + L2->coe);
L = L->next;
}
L1 = L1->next;
L2 = L2->next;
} else if(L1->exp > L2->exp) {
L->next = L1;
L1 = L1->next;
L = L->next;
} else {
L->next = L2;
L2 = L2->next;
L = L->next;
}
}
if(L1) L->next = L1;
if(L2) L->next = L2;
L = tmp->next;
delete(tmp);
tmp = L;
int cnt = 0;
while(tmp) {
if(tmp->coe != 0) cnt++;
tmp = tmp->next;
}
printf("%d", cnt);
if(cnt) {
while(L) {
printf(" %d %.1lf", L->exp, L->coe);
L = L->next;
}
}
return 0;
}
method 2
实际上，这个题拿数组做，简单了不止一点半点😂。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
void readp(int nums, double *poly) {
int exp;
double coe;
for(int i = 0; i < nums; i++) {
scanf("%d %lf", &exp, &coe);
poly[exp] = coe;
}
}
int main() {
double L1[1005] = {0}, L2[1005] = {0}, L[1005] = {0};
int k1, k2, exp;
double coe;
scanf("%d", &k1);
readp(k1, L1);
scanf("%d", &k2);
readp(k2, L2);
int cnt = 0;
for(int i = 0; i < 1005; i++) {
L[i] = L1[i] + L2[i];
if(L[i] != 0) cnt++;
}
printf("%d", cnt);
if(cnt) {
for(int i = 1000; i >= 0; i--) {
if(L[i] != 0) printf(" %d %.1lf", i, L[i]);
}
}
return 0;
}
1003 Emergency
Analysis
题目大意是给定几个城市之间的地图，城市之间的路有相应的权值，然后给定起始城市和终点城市，问从起始城市到达终点城市的路径有几条，并且这些路径上点权之和最大是多少。
由于题目的实际意义，构造好的图一定是一个无向图，借助 Dijkstra 算法或 Bellman-Ford 算法可以解决这两个问题。
路径条数和点权和的最大值，分别使用一个数组来统计即可。
Code
Dijkstra
1 |
|
Bellman-Ford
1 |
|
1004 Counting Leaves
Analysis
Code
1 |
|
1005 Spell It Right
Analysis
题目意思很简单，给一个数字，计算出这个数字每一位上的数字之和，然后用英文的方式分别输出这个和的每一位数字（好吧，有点绕😅）。
与乙级题库的1002很类似，考察数位拆分吧，比较简单。
Code
1 |
|
贴个 C++ 版：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
using namespace std;
unordered_map<int, string> num2english = {{0, "zero"}, {1, "one"}, {2, "two"}, {3, "three"},
{4, "four"}, {5, "five"}, {6, "six"}, {7, "seven"}, {8, "eight"}, {9, "nine"}};
int main() {
string str;
cin >> str;
int sum = 0;
for(int i = 0; i < str.length(); i++) {
sum += str[i] - '0';
}
str = to_string(sum);
for(int i = 0; i < str.length(); i++) {
cout << num2english[str[i] - '0'];
if(i != str.length() - 1) cout << ' ';
}
return 0;
}
再补个用 dfs 输出的办法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
using namespace std;
unordered_map<int, string> num2english = {{0, "zero"}, {1, "one"}, {2, "two"}, {3, "three"},
{4, "four"}, {5, "five"}, {6, "six"}, {7, "seven"}, {8, "eight"}, {9, "nine"}};
void dfs(int n) {
if(n / 10 == 0) {
cout << num2english[n % 10];
return;
}
dfs(n / 10);
cout << ' ' << num2english[n % 10];
}
int main() {
string str;
cin >> str;
int sum = 0;
for(int i = 0; i < str.length(); i++) {
sum += str[i] - '0';
}
dfs(sum);
return 0;
}
1006 Sign in and Sign Out
Analysis
题目意思很简单，最先去机房的人开门，最晚出机房的人关门，用学号代替人名，输出最早来和最晚走的人的学号即可。
分析输入数据，1个字符串，6个整型数字，每3个数字为一个时间点，分别代表到来和离开的时间点，既然要找的只是最早和最晚的两个时间点，那么每次寻找时，只要去比较一个时间点即可。
最早来的时间初始化为一天中最后晚的时间（23:59:59），最晚走的时间初始化为一天中最早的时间（00:00:00），注意要分开比较，不能用if-else哦。
Code
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
using namespace std;
int main() {
int m;
cin >> m;
string early, late, earliest, latest, tmp, come, leave;
cin >> early >> earliest >> latest;
late = early;
m--;
while(m--) {
cin >> tmp >> come >> leave;
if(come < earliest) {
early = tmp;
earliest = come;
}
if(leave > latest) {
late = tmp;
latest = leave;
}
}
cout << early << ' ' << late;
return 0;
}
1007 Maximum Subsequence Sum
Analysis
Code
DP
1 |
|
Online-Processing
1 |
|
1008 Elevator
Analysis
题目大意是给定电梯移动和等待的时长，再按照题目给定的停留顺序，计算出电梯在这个过程中需要的总时间。
以样例为例：
- 初始为0层，到2层，时长为：$2 \times 6 = 12\ s$，再加上等待的$5s$，总计$17s$
- 从2层到3层，时长为：$1 \times 6 = 6\ s$，再加上等待的$5s$，总计$11s$
- 从3层到1层，时长为：$2 \times 4 = 8\ s$，再加上等待的$5s$，总计$13s$
- 合计为：$17 + 11 + 13 = 41\ s$
Code
1 |
|
1009 Product of Polynomials
Analysis
此题也是 ZJU 数据结构课程里面的例题，算是另一半了，与 1002 是类似的，只不过 1002 是加法，这个是乘法，还是先用链表做吧。
Code
method 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
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
typedef struct PolyNode *Polynomial;
struct PolyNode {
double coef;
int expon;
Polynomial link;
};
void Attach(double c, int e, Polynomial *pRear);
Polynomial ReadPoly();
Polynomial Mult(Polynomial P1, Polynomial P2);
void PrintPoly(Polynomial P);
int Compare(int a, int b);
int GetNum(Polynomial P);
int main(int argc, char const *argv[]){
Polynomial P1, P2, PP, PS;
P1 = ReadPoly();
P2 = ReadPoly();
PP = Mult(P1, P2);
int numbers = GetNum(PP);
if(numbers) {
printf("%d ", numbers);
PrintPoly(PP);
} else {
printf("%d\n");
}
return 0;
}
void Attach(double c, int e, Polynomial *pRear) {
Polynomial P;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->coef = c;
P->expon = e;
P->link = NULL;
(*pRear)->link = P;
*pRear = P;
}
Polynomial ReadPoly() {
Polynomial P, Rear, t;
int e, K;
double c;
scanf("%d", &K);
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
Rear = P;
while(K--) {
scanf("%d %lf", &e, &c);
Attach(c, e, &Rear);
}
t = P;
P = P->link;
free(t);
return P;
}
Polynomial Mult(Polynomial P1, Polynomial P2) {
Polynomial P, Rear, t1, t2, t;
int e;
double c;
if(!P1 || !P2) return NULL;
t1 = P1;
t2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
Rear = P;
while(t1) {
t2 = P2;
Rear = P;
while(t2) {
e = t1->expon + t2->expon;
c = t1->coef * t2->coef;
while(Rear->link && Rear->link->expon > e) {
Rear = Rear->link;
}
if(Rear->link && Rear->link->expon == e) {
if(Rear->link->coef + c) {
Rear->link->coef += c;
} else {
t = Rear->link;
Rear->link = t->link;
free(t);
}
} else {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = c;
t->expon = e;
t->link = Rear->link;
Rear->link = t;
Rear = Rear->link;
}
t2 = t2->link;
}
t1 = t1->link;
}
t2 = P;
P = P->link;
free(t2);
return P;
}
void PrintPoly(Polynomial P) {
int flag = 0;
while(P) {
if(!flag){
flag = 1;
} else {
printf(" ");
}
printf("%d %.1lf", P->expon, P->coef);
P = P->link;
}
printf("\n");
}
int Compare(int a, int b) {
return a > b ? 1 : a == b ? 0 : -1;
}
int GetNum(Polynomial P) {
Polynomial p = P;
int ret = 0;
while(p) {
ret++;
p = p->link;
}
return ret;
}
用 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
using namespace std;
typedef struct Node* List;
typedef struct Node* PtrtoNode;
struct Node {
int exp;
double coe;
PtrtoNode next;
Node() { next = nullptr; }
Node(int _exp, double _coe) {
exp = _exp;
coe = _coe;
next = nullptr;
}
};
List createlist(int node_num) {
int exp;
double coe;
List head = new Node;
List L = head;
while(node_num--) {
scanf("%d %lf", &exp, &coe);
head->next = new Node(exp, coe);
head = head->next;
}
head = L;
L = L->next;
delete(head);
return L;
}
int main() {
int k;
scanf("%d", &k);
List L1 = createlist(k);
scanf("%d", &k);
List L2 = createlist(k);
List L = new Node, rear, t1 = L1, t2 = L2, t;
rear = L;
int exp_tmp;
double coe_tmp;
while(t1) {
t2 = L2;
rear = L;
while(t2) {
exp_tmp = t1->exp + t2->exp;
coe_tmp = t1->coe * t2->coe;
while(rear->next && rear->next->exp > exp_tmp) {
rear = rear->next;
}
if(rear->next && rear->next->exp == exp_tmp) {
if(rear->next->coe + coe_tmp) rear->next->coe += coe_tmp;
else {
t = rear->next;
rear->next = t->next;
delete(t);
}
} else {
t = new Node(exp_tmp, coe_tmp);
t->next = rear->next;
rear->next = t;
rear = rear->next;
}
t2 = t2->next;
}
t1 = t1->next;
}
t = L;
L = L->next;
delete(t);
int cnt = 0;
t = L;
while(t) {
cnt++;
t = t->next;
}
printf("%d", cnt);
if(cnt) {
t = L;
while(t) {
printf(" %d %.1lf", t->exp, t->coe);
t = t->next;
}
}
return 0;
}
method 2
数组做法：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
void readp(int nums, double *poly) {
int exp;
double coe;
for(int i = 0; i < nums; i++) {
scanf("%d %lf", &exp, &coe);
poly[exp] = coe;
}
}
int main() {
double L1[1005] = {0}, L2[1005] = {0}, L[2010] = {0};
int k1, k2, exp;
double coe;
scanf("%d", &k1);
readp(k1, L1);
scanf("%d", &k2);
readp(k2, L2);
for(int i = 0; i < 1001; i++) {
for(int j = 0; j < 1001; j++) {
exp = i + j;
coe = L1[i] * L2[j];
L[exp] += coe;
}
}
int cnt = 0;
for(int i = 0; i <= 2000; i++) {
if(L[i] != 0) cnt++;
}
printf("%d", cnt);
for(int i = 2000; i >= 0; i--) {
if(L[i] != 0) printf(" %d %.1lf", i, L[i]);
}
return 0;
}
1010 Radix
Analysis
这个题的题意说的比较模糊，所以不太好寻找思路。
先分析一下题目意思，给定N1，N2，tag和radix四个数字；若当tag为1时，radix的值就是N1的进制数，tag为2时，radix的值就是N2的进制数（一般针对这种情况，最好交换下N1和N2的值，再统一处理）。
紧接着，题目要求判断N1和N2是否相等，由于题目给定的两个数字的进制不相同，所以还必须要转换后进行判断。与其这样，不如直接将能确定进制的那个数转化为十进制数，然后与另一个数的每一个不同的进制单位下转换为十进制数后值进行比较，若相等，则这两个数相等（只要在一种进制单位下，两个数相等，那么在其他任意进制单位下，这两个数不管如何变化都是相等的）。
明白题意后，就得开始打码了。由于题目给定的radix没有限制范围，所以转换后的十进制数是有可能溢出的（long long也会），所以使用字符串来存储数字。
紧接着，按照前面的思路，先构造字符0 - 9和a - z的十进制数对应表，方便调用。另外，不管tag的值如何，对N1和N2进行处理，默认N1是进制确定的数。在开始对N2进行进制转换之前，要先确定其可能的进制范围，这个结果就是：以其字符最大值为下界，N1的十进制数值为上界。在这个进制范围内，一个一个去枚举显然是很慢的，所以使用二分法是一个很不错的选择。
注意：
- 使用二分法时，只需要找到满足条件：与
N1的十进制数相等的数即可，此时得返回进制数。 - 针对数据的溢出情况，一旦结果为负，就可以判断为溢出，此时
N2在这个进制下的转换出来的十进制数肯定是大于N1的十进制数的。
Code
1 |
|
1011 World Cup Betting
Analysis
题目意思很明确，三局比赛，给出每局的赔率，默认每次都赌对，问怎样买收益最多。
很简单，每次买赔率最大的就好啦~然后还有一个麻烦的地方，就是要输出每局赔率最大的是哪一种局，即：获胜（Win）、平局（Tie）和失败（Lose），先保存每次的下标，然后写个函数转换一下就好了。至于收益的计算方法，按照题目给定的公式算就好了。
Code
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
int main() {
double turns[3][3], max, maxproduct = 1.0;
char ans[3];
for(int i = 0; i < 3; i++) {
max = -1000;
for(int j = 0; j < 3; j++) {
scanf("%lf", &turns[i][j]);
if(max < turns[i][j]) {
max = turns[i][j];
if(j == 1) ans[i] = 'T';
else if(j == 2) ans[i] = 'L';
else ans[i] = 'W';
}
}
maxproduct *= max;
}
double maxprofit = 0.0;
maxprofit = (maxproduct * 0.65 - 1) * 2;
for(int i = 0; i < 3; i++) {
printf("%c ", ans[i]);
}
printf("%.2lf", maxprofit);
return 0;
}
1012 The Best Rank
Analysis
给出每个学生的各科成绩，计算其平均分，并根据他们的成绩进行排序；然后查找指定学号的学生的成绩，输出其排名最优的成绩和科目名称。
Code
1 |
|
重新写了一下，求每个学生的各科排名时，不再开那么大的数组了，但是会有额外的查找时间开销（也能 AC）：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
using namespace std;
struct student {
string id;
int grade[4];
int rank[4];
} stu[2005];
char species[5] = "ACME";
int now;
int main() {
int N, M, c, m, e;
cin >> N >> M;
string str;
for(int i = 0; i < N; i++) {
cin >> str >> c >> m >> e;
stu[i].id = str;
stu[i].grade[1] = c, stu[i].grade[2] = m, stu[i].grade[3] = e;
stu[i].grade[0] = (c + m + e) / 3;
}
for(now = 0; now < 4; now++) {
sort(stu, stu + N, [](student a, student b){
return a.grade[now] > b.grade[now];
});
stu[0].rank[now] = 1;
for(int j = 1; j < N; j++) {
if(stu[j].grade[now] == stu[j - 1].grade[now]) stu[j].rank[now] = stu[j - 1].rank[now];
else stu[j].rank[now] = j + 1;
}
}
for(int i = 0; i < M; i++) {
cin >> str;
int index = -1;
for(int i = 0; i < N; i++) {
if(stu[i].id == str) {
index = i;
break;
}
}
if(index == -1) cout << "N/A" << endl;
else {
int k = 0;
for(int i = 1; i < 4; i++) {
if(stu[index].rank[i] < stu[index].rank[k]) k = i;
}
cout << stu[index].rank[k] << ' ' << species[k] << endl;
}
}
return 0;
}
1013 Battle Over Cities
Analysis
Code
1 | /* method 1: use union-find set |
1015 Reversible Primes
Analysis
题目大意是给定两个整数N、D，N是十进制下的整数，D是进制数，判断N和将N转换为D进制下的数是否都是素数。若是，输出Yes，反之输出No。
考察进制转换和素数的判断。
Code
1 |
|
贴个 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
using namespace std;
bool isprime(int n) {
if(n <= 1) return false;
else {
for(int i = 2; i <= sqrt(n); i++) {
if(n % i == 0) return false;
}
return true;
}
}
int main() {
int n, d;
while(true) {
cin >> n;
if(n < 0) break;
cin >> d;
if(!isprime(n)) cout << "No" << endl;
else {
vector<int> digits;
int tmp = n;
while(tmp) {
int r = tmp % d;
digits.push_back(r);
tmp /= d;
}
tmp = 0;
for(int i = 0; i < digits.size(); i++) {
tmp = tmp * d + digits[i];
}
if(isprime(tmp)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}
return 0;
}
1016 Phone Bills
Analysis
先分析一下输入，包含名称、时间和状态，其中名称和状态是以字符串的形式输入的，而时间则是十进制数字。这里要立刻反应过来，不能用题目字符串来表示状态，应该换成数字来表示。至于，最开始输入的费率表，使用一个整型数组来存储，使用的时候进行调用就好。
接下来，需要对输入的数据进行排序，优先级最大的排序依据就是名称，按照字典序来排列，注意字符串需要用strcmp函数来进行比较；其次，相同名称的元素按照时间的先后进行排列就好了。
接着再来看输出，首先要输出的是客户的名称和其话费账单所处的月份；第二行开始输出客户的话费账单的开始时间和结束时间，然后输出当前账单的总时长和费用，注意费用为浮点型；所有账单都输出完毕后，最后一行输出客户总话费。
大致清楚之后，如何去计算话费呢？根据题目，输入的每一项必须是配对的on-line和off-line才能组成一个合法的账单，并且必须要是连续、相邻的才能是一对（这个条件很重要）。读懂这个条件后，计算时间就比较简单了，让开始时间一直增加到结束时间，统计好分钟数既可得到经历的时间，然后计算总费用。注意，给定的费率是cents/minute，最后得转化为dollar，除以100即可。
Code
1 |
|
1018 Public Bike Management
Analysis
题目背景类似现在的共享单车，这种公共设施服务有一个管理中心，本题叫做 Public Bike Management Center，简称 PMBC，而这个 PMBC 会调整每个停靠站点的自行车数目从而达到“完美”状态，这种“完美”状态是指停靠数量为该站点最大容量的一半。
题目给定各个站点距离 PMBC 的距离、每个停靠站点当前的停靠数量和需要投放自行车的站点，要求输出完成投放工作需要携带的最小自行车数目、完成投放工作的最短路径和剩余带回的车数，注意路径中的站点如果不是完美状态，也需要调整为完美状态。
题目的第一要求是最短路径，借助 Dijkstra 算法可以解决这个问题，再利用动态数组保存好每一条最短路径，然后借助 DFS 来计算题目要求的所携带的最小自行车数目及剩余带回的车数。
Code
1 |
|
1019 General Palindromic Number
Analysis
此题属于结合了进制转换和回文序列判断的混合题目。
Code
1 |
|
贴个 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
using namespace std;
int main() {
int n, k;
cin >> n >> k;
if(n == 0) {
cout << "Yes\n" << 0;
} else {
vector<int> digits;
while(n) {
digits.push_back(n % k);
n /= k;
}
int size = digits.size();
bool flag = true;
for(int i = 0; i < size / 2; i++) {
if(digits[i] != digits[size - i - 1]) {
flag = false;
break;
}
}
if(flag) cout << "Yes\n";
else cout << "No\n";
for(int i = size - 1; i >= 0; i--) {
cout << digits[i];
if(i > 0) cout << ' ';
}
}
return 0;
}
1020 Tree Traversals
Analysis
题目大意，给定两个树的中序遍历和后序遍历，求其层次遍历。
此题属于树的常规题型，思路是利用中序遍历和后序遍历建树，然后再借助 BFS 进行层次遍历，并输出层次遍历序列。
Code
1 |
|
1022 Digital Library
Analysis
题目背景是数字图书馆的检索功能，要求大致模拟一下这个功能。
按照题目的要求，输出书名时，需要按序输出，比起构造新的数据结构后使用sort函数来完成这项操作，不如直接借助set。而在查询时，是通过字符串来进行的查询，使用map建立映射后，就可以类似散列一样进行查询。
综合上述的两种需求后，好在map是支持string向set的映射的，所以直接使用即可。
由于关键字key是一个一个给出的，所以需要一个一个输入并统计，依据cin或scanf输入字符串的特性，可以很方便的单个读入，并使用getchar读取回车符结束循环。
Code
1 |
|
查询函数可以写的简单点：1
2
3
4
5
6
7
8void query(map<string, set<int>>& mp, string &tmp) {
if(!mp.count(tmp)) printf("Not Found\n");
else {
for(auto &i: mp[tmp]) {
printf("%07d\n", i);
}
}
}
这个题的难点不在算法的设计上，而是在对数据的处理上。为了能更简单的完成这个事情，就需要对 STL 容器、输入输出函数及其他 API 的用法很熟悉。
1023 Have Fun with Numbers
Analysis
题目大意是给一个不超过20位的整数，将这个整数翻倍后，判断组成这个新整数的所有数字是否与原来的数字相同。若是，输出Yes；反之，输出No。注意，无论是否符合都需要输出翻倍后的新数字。
由于题目明确说了给定的数字位数不超过20位，但是long long只能到19位，所以直接使用数组来存储数字，然后利用数组来模拟乘以2。
然后判断两个数字的所有位数字的出现次数是否一致即可（利用散列的思想会比较方便）。
Code
1 |
|
贴个 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
using namespace std;
int main() {
string num;
cin >> num;
vector<int> n, dn;
for(int i = num.size() - 1; i >= 0; i--) {
n.push_back(num[i] - '0');
}
int carry = 0;
for(int i = 0; i < n.size(); i++) {
dn.push_back((2 * n[i] + carry) % 10);
carry = 2 * n[i] / 10;
}
if(carry > 0) dn.push_back(carry);
string ans;
for(int i = dn.size() - 1; i >= 0; i--) {
ans.push_back(dn[i] + '0');
}
sort(n.begin(), n.end());
sort(dn.begin(), dn.end());
if(n == dn) cout << "Yes" << endl;
else cout << "No" << endl;
cout << ans;
return 0;
}
本来还想更偷懒用long double直接算的，但是在存 20 位数时，long double这个数据类型已经开始有误差了，所以最后一个测试点过不去，可惜了。按理说，long double能存相当大的数了，不应该才 20 位就开始出现误差啊？
1024 Palindromic Number
Analysis
题目大意是给定一个数字，判断是否为回文数字，并进行一系列操作。另外，给定一个上限次数，当给定的数不是回文数字时，令其加上将其逆置后的数字，在进行判断是否为会问数字，若是，则输出这个数字和变换次数，反之，则继续直至超过上限次数。注意，即便超过了上限次数，依然要变换过程中最后的数字。
解决此题需要解决下面3个子问题：
- 回文数字的判定
- 数字逆置
- 数字相加
题目要求数字的范围不超过$10^{10}$，可以使用另外这样还有一个好处，就是在判断是否是回文数字时，可以直接对数组进行判断。long long，但这会使得将数字逆置的这个步骤非常麻烦，所以直接使用数组来存储数字，并模拟数字之间的加法。
使用long long会溢出，直接用字符串就好，别想着偷鸡了。
Code
1 |
|
贴个 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
using namespace std;
bool ispalindromic(string &num) {
int left = 0, right = num.length() - 1;
while(left < right) {
if(num[left] != num[right]) return false;
left++, right--;
}
return true;
}
int main() {
int k;
string num, tmp;
cin >> num >> k;
int i;
reverse(num.begin(), num.end());
for(i = 0; i < k; i++) {
if(ispalindromic(num)) break;
tmp = num;
reverse(tmp.begin(), tmp.end());
int carry = 0;
for(int i = 0; i < num.length(); i++) {
int t = (num[i] + tmp[i] + carry - 2 * '0');
num[i] = t % 10 + '0';
carry = t / 10;
}
if(carry) num.push_back(carry + '0');
}
reverse(num.begin(), num.end());
cout << num << endl;
cout << (i == k ? k : i);
return 0;
}
1025 PTA Ranking
Analysis
此题考察排序，直接调用库里的排序函数来帮助完成排序就好了。注意：
- 一个地点内的所有数据输入完了之后，本地排名就可以完成了
- 每个数据在在输入的时候就可以顺便对其进行地点编号
- 最终排名必须要在本地排名之后才能进行
Code
1 |
|
1027 Colors in Mars
Analysis
考察进制转换的题目，10进制转换为13进制，与转换10进制转换为16进制是类似的，代码可能写的不太好看，嘿嘿~
Code
1 |
|
贴个 C++ 直接用 map 打表的方法：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
using namespace std;
map<int, string> marscolors;
char num2char(int num) {
char ret = '0';
if(0 <= num && num <= 9) ret += num;
else ret = 'A' + num - 10;
return ret;
}
int main() {
marscolors[0] = "00";
for(int i = 1; i < 169; i++) {
int tmp = i;
string s;
while(tmp) {
s += num2char(tmp % 13);
tmp /= 13;
}
if(i < 13) s += "0";
reverse(s.begin(), s.end());
marscolors[i] = s;
}
int red, green, blue;
cin >> red >> green >> blue;
cout << "#" << marscolors[red] << marscolors[green] << marscolors[blue];
return 0;
}
1028 List Sorting
Analysis
考察排序，用输入的数字表示以元素的某一项进行排序，直接把类别数字用全局变量代替，然后在cmp函数中直接使用即可，注意字符串需要用strcmp函数进行比较。
Code
1 |
|
贴个 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
using namespace std;
const int maxn = 100000 + 5;
struct student {
string id, name;
int grade;
} stu[maxn];
bool cmp1(student a, student b) {
if(a.name != b.name) return a.name < b.name;
else return a.id < b.id;
}
int n, c;
bool cmp(student a, student b) {
if(c == 1) return a.id < b.id;
else if(c ==2) {
if(a.name != b.name) return a.name < b.name;
else return a.id < b.id;
} else {
if(a.grade != b.grade) return a.grade < b.grade;
else return a.id < b.id;
}
}
int main() {
cin >> n >> c;
for(int i = 0; i < n; i++) {
cin >> stu[i].id >> stu[i].name >> stu[i].grade;
}
sort(stu, stu + n, cmp);
for(int i = 0; i < n; i++) {
cout << stu[i].id << ' ' << stu[i].name << ' ' << stu[i].grade << endl;
}
return 0;
}
1029 Median
Analysis
题目大意是给定两个递增序列，求这两个序列合并后的中位数。
明确了什么是中位数之后，解决这个问题的方法就有很多了。超级无脑的做法就是直接把其中一个序列拼接在另外一个序列后面，排个序，然后直接输出其中位数就好了。但是注意到题目的Memory Limit: 1.5 MB，说明题目对内存有要求，简单直接的做法可能导致Memory Limit Exceeded的错误。
那么就需要想办法优化空间了，题目给定的两个序列，按照上述的思路，就需要三个数组（两个存给定的，一个存合并后的），能不能少用一个或两个呢？答案是肯定的，其实可以不用完全合并，而只需要模拟这个合并操作的过程，并在这个过程中，按照顺序来统计是否枚举到了那个中位数（根据数组下标的初始值，中位数的位置是可以直接算出来的）即可。
不过，很可惜，道高一尺魔高一丈，这个题更新（2018年3月之后？）了测试样例，最后一个测试用例还是无法通过，并且还是MLE的错误。
这就得靠在线处理了，在读入第二个序列时，将每次读入的数字存在一个变量内，每次需要统计第一个序列中有多少数字小于它，然后根据这一点来计算出这个数字在合并后的序列中所处的位置，并与中位数的位置进行比较，然后来决定是否输出。在读入第二个序列的过程中存在两种情况：
- 数字存在第一个序列内，并且此时可以确定中位数必定比当前读入的数字小
- 数字存在第二个序列内，就是当前读入的数字
针对上述两种情况，统计到中位数后直接输出即可，但是要注意，若是第二个序列的数字比第一个序列少很多（或者小很多等极端情况），那么中位数依然还是在第一个序列内，所以还是得在第一个序列内找。
Code
1 |
|
现在这个题的内存限制已经改成64 MB了，可以直接排序了😂：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
using namespace std;
int main() {
vector<int> arr;
int n, tmp;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> tmp;
arr.push_back(tmp);
}
cin >> n;
for(int i = 0; i < n; i++) {
cin >> tmp;
arr.push_back(tmp);
}
sort(arr.begin(), arr.end());
int pos = arr.size() % 2 == 1 ? arr.size() / 2 : arr.size() / 2 - 1;
cout << arr[pos];
return 0;
}
1030 Travel Plan
Analysis
题目大意是给定一个旅游地图，每个结点之间的边，包含两个属性值：距离和花销。然后，给定起点和终点，要求输出二者之间的最短路径的总距离和对应的花销，若存在相同总距离的最短路径，此时需输出最小的花销值。
由于题目已经说明输入数据不存在负数，且只有一个起点，问题就变成了不存在负环的图的单源最短路径问题。所以可以直接使用 Dijkstra 算法进行求解。由于需要输出对应的最短路径，所以可以在 Dijkstra 算法求解最短路径的过程中，顺便利用一个数组来保存最优路径，之后再利用 DFS 来正序输出路径；当然，也可以利用动态数组保存所有的路径，之后再利用 DFS 遍历每条路径，来求解花销值最小的路径。
Code
Dijkstra
1 |
|
Dijkstra + DFS
1 |
|
1031 Hello World For U
Analysis
这道题属于打印图形类的题目，题眼大概就是找到图形输出的规律了，所以读题得仔细一点。
不过，很巧地是，这道题目，用来找规律的那个条件不是很明显，可能还不太容易看懂（可能我英语渣~），就是这个条件$n_1 = n_3 = max \lbrace{k | k \le n_2\ for\ all\ 3 \le n_2 \le N}\rbrace \ with \ n_1 + n_2 + n3 - 2 = N$了。意思大致是：$n_1 = n_3 \le k$，而$k$这个数是得严格小于等于$n_2$，而$n_2$的取值范围为：$[3, N]$，另外还有一个条件$n_1 + n_2 + n_3 - 2 = N$。
另外，$n_1$是指最左边一列“字符串”的长度，$n_2$是指底部“字符串”的长度，$n_3$是指最右边一列“字符串”的长度，$N$就是严格意义上的字符串长度了。
事实上，$n_1 = n_3 = (N + 2) / 3$，然后求得$n_2$即可开始打印输出了😒。
可以直接打印输出，不过还要找些小规律（折磨你😆），如第一行输出的是字符串第一个字符和最后一个字符；先输出第一个字符，然后输出空格，接着在输出最后一个字符即可。也可以先把每一个字符放到二维数组内，利用空格初始化二维数组，然后在指定位置放入字符，最后输出即可。
Code
1 |
|
贴个 C++ 版，没有用公式求 n1, n2, n3：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
using namespace std;
int main() {
string str;
cin >> str;
int n1, n2 = 3, n3, len = str.length();
while(true) {
int diff = len - n2;
if(diff % 2 == 0) {
n1 = n3 = diff / 2;
if(n2 > n1) break;
}
n2++;
}
int i, j;
for(i = 0, j = len - 1; i < n1 && j > len - n3 - 1; i++, j--) {
cout << str[i];
for(int k = 0; k < n2 - 2; k++) cout << ' ';
cout << str[j] << endl;
}
while(i <= j) cout << str[i++];
return 0;
}
1032 Sharing
Analysis
题目大意是使用链表存储英文字符时，因为英文字符存在相同的后缀，所以公共后缀只存储一次，然后让不同且具有这个公共后缀单词的最后一个不属于这个后缀的字母的next指向公共后缀的第一个字母即可，这样就可以节约一定的存储空间了。
按照题目背景，题目要求找出具有两个单词的公共后缀的第一个字母的地址并输出，若不存在，则输出-1。直观的做法是，遍历第一个链表，同时遍历第二个链表，找到二者中具有相同address的元素，输出即可，此时的时间复杂度为：$O(n^2)$。
按照题目给定的形式，使用静态链表来处理问题，接着上面的思考，若在遍历第一个链表时，给其每一个结点都加上一个标志位；接着在遍历第二个链表时，就可以直接判断第二个链表的结点的标志位是否与第一个链表结点的标志位相同，若相同，则这个结点就是二者公共后缀的第一个字母了，就可以输出了，这样时间复杂度就降为：$O(n)$了。
Code
1 |
|
1033 To Fill or Not to Fill
Analysis
此题考察贪心算法，如何进行“贪心”得从结果和题意上去分析。
依据结果，每次经过一个加油站时，需要将当前加油站与小车从当前加油站能到达的每个加油站的油价进行比较，若存在油价更低的加油站，那么就加刚好能到达那个加油站的油量，否则就加满。所以需要将加油站按照离杭州的距离从小到大进行排列，并假设目的地离杭州的距离为输入距离，油价为0（这样做的目的是为了方便比较，不用处理特殊情况）。然后，开始模拟小车从起点出发。
当第一个加油站离杭州的距离不为0时，说明小车无法出城，直接输出The maximum travel distance = 0.00即可。
Code
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
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
using namespace std;
const int maxn = 500 + 5;
struct station {
double price, dis;
} sta[maxn];
int main() {
double cmax, d, davg;
int n;
scanf("%lf %lf %lf %d", &cmax, &d, &davg, &n);
for(int i = 0; i < n; i++) {
scanf("%lf %lf", &sta[i].price, &sta[i].dis);
}
sta[n].dis = d, sta[n].price = 0;
sort(sta, sta + n, [&](station a, station b) { return a.dis < b.dis; });
if(sta[0].dis != 0) {
printf("The maximum travel distance = 0.00\n");
} else {
int now = 0;
double ans = 0, tank = 0, max = cmax * davg;
while(now < n) {
int k = -1;
double minprice = DBL_MAX;
for(int i = now + 1; i <= n && sta[i].dis - sta[now].dis <= max; i++) {
if(sta[i].price < minprice) {
minprice = sta[i].price;
k = i;
if(minprice < sta[now].price) break;
}
}
if(k == -1) break;
double need = (sta[k].dis - sta[now].dis) / davg;
if(minprice < sta[now].price) {
if(tank < need) {
ans += (need - tank) * sta[now].price;
tank = 0;
} else tank -= need;
} else {
ans += (cmax - tank) * sta[now].price;
tank = cmax - need;
}
now = k;
}
if(now == n) printf("%.2lf\n", ans);
else printf("The maximum travel distance = %.2lf\n", sta[now].dis + max);
}
return 0;
}
1034 Head of a Gang
Analysis
Code
1 |
|
1035 Password
Analysis
题目看着臭长臭长的，其实比较简单，就是有些小小的细节...
先分析输入格式，给个N代表N组数据，然后每一组数组按照name password的格式来给出，都是字符串，由于输出时后要同等输出，所以方便起见定义一个结构体来保存这些数据；再者，由于最后得先输出被修改的数量，所以得先把数据都存储下来，才能在输出数量后，在输出修改的信息。
再看输出格式，若有修改，就输出修改的数量，然后每行紧接着每个结构体内的信息；若没有修改，就输出There are N accounts and no account is modified，注意这里的细节，当N为1时，得输出There is 1 account and no account is modified，这两句英文在N为1和其他数时使用的Be动词不一样（老师出题很严谨的，🤣英语要学好，哈哈~）。
其他就没什么了。
Code
1 |
|
贴个 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
using namespace std;
int main() {
int m, cnt = 0;
cin >> m;
string account, password;
vector<vector<string>> ans;
for(int i = 0; i < m; i++) {
cin >> account >> password;
bool flag = false;
for(int j = 0; j < password.length(); j++) {
switch(password[j]) {
case '1': password[j] = '@'; flag = true; break;
case '0': password[j] = '%'; flag = true; break;
case 'l': password[j] = 'L'; flag = true; break;
case 'O': password[j] = 'o'; flag = true; break;
default: break;
}
}
if(flag) {
ans.push_back({account, password});
cnt++;
}
}
if(!cnt) {
if(m <= 1) cout << "There is " << m << " account";
else cout << "There are " << m << " accounts";
cout << " and no account is modified";
} else {
cout << cnt << endl;
for(int i = 0; i < ans.size(); i++) {
cout << ans[i][0] << ' ' << ans[i][1] << endl;
}
}
return 0;
}
太麻烦了，这个题...
1036 Boys vs Girls
Analysis
题目意思很简单，找出女生中分最高的，男生中分最低的，分别输出他们的姓名、学号和分数之差即可，由于最后需要的两个结果可能没有出现，利用两个标记来记录状态，然后根据4种不同的状态，分别对应输出即可。
Code
1 |
|
贴个 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
using namespace std;
int main() {
int n;
cin >> n;
string malename, femalename, maleid, femaleid, name, clas, maleclass, femaleclass;
char gender;
int grade, highest = -1, lowest = 101;
while(n--) {
cin >> name >> gender >> clas >> grade;
if(gender == 'M') {
if(grade < lowest) {
lowest = grade;
malename = name;
maleclass = clas;
}
}
if(gender == 'F') {
if(grade > highest) {
highest = grade;
femalename = name;
femaleclass = clas;
}
}
}
if(highest < 0) cout << "Absent\n";
else cout << femalename << ' ' << femaleclass << endl;
if(lowest > 100) cout << "Absent\n";
else cout << malename << ' ' << maleclass << endl;
if(lowest > 100 || highest < 0) cout << "NA\n";
else cout << highest - lowest;
return 0;
}
1037 Magic Coupon
Analysis
这道题考察贪心算法，题目要求输出可以得到的最大钱数。注意这段话：print in a line the maximum amount of money you can get back的表述，所以只需要得到能得到的最大值就可以了，不需要统计负数的情况所以只需要统计收钱的情况，付钱的情况不用统计了。
若只统计一张券乘以一件商品价格的结果为正数的情况，就分为两种：
- 券值为正，商品价格为正，面值最大的券需要乘以价格最高的商品，就能得到最大的结果。
- 券值为负，商品价格为负，面值最小（负数）的券需要乘以价格最低（负数）的商品，就能得到最大的结果。
利用两个数组来分别存储券值和商品价格，按照大小排序后，开始相乘，计算最终结果。注意，升序和降序不影响结果，但需要两种情况需要分开处理。
Code
1 |
|
贴个 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
using namespace std;
priority_queue<int, vector<int>, greater<int>> c1, p1;
priority_queue<int, vector<int>, less<int>> c2, p2;
int main() {
int nc, np, tmp;
cin >> nc;
for(int i = 0; i < nc; i++) {
cin >> tmp;
if(tmp < 0) c1.push(tmp);
if(tmp > 0) c2.push(tmp);
}
cin >> np;
for(int i = 0; i < np; i++) {
cin >> tmp;
if(tmp < 0) p1.push(tmp);
if(tmp > 0) p2.push(tmp);
}
long long ans = 0;
while(!c1.empty() && !p1.empty()) {
int ctmp = c1.top(); c1.pop();
int ptmp = p1.top(); p1.pop();
ans += ctmp * ptmp;
}
while(!c2.empty() && !p2.empty()) {
int ctmp = c2.top(); c2.pop();
int ptmp = p2.top(); p2.pop();
ans += ctmp * ptmp;
}
cout << ans;
return 0;
}
粗略分析一下，堆的时间复杂度应该优于排序，同样需要 $O(n)$ 的存储空间，不过极端情况下，二者应该差不多。另外，其实可以在最后的结果ans这里挖坑，故意弄成溢出的情况，因为题目只说了保证给的数组不超过 $2^{30}$。
1038 Recover the Smallest Number
Analysis
题目会给一些数字，要求将给定的所有数字“拼接”起来，最终得到一个组合数，这个数字要比按照其他方式组合得到的结果小。
由于不能打乱给定的每个数字的数位顺序，所以一般会想到直接按照字典序比较每个数字的大小，然后让小的的在前面，大的在后面。但要注意，如果数字32, 321，按字典序大小排列后的组合数是32321，此时存在更小的结果32132，所以不能单纯的按照这种思路进行。
对于32, 321这两个数字而言，按照上面的结果：32132 < 32321，从字符串的角度出发，假设a = 32, b = 321，则有ba < ab，这样就可以在两个数中找出“拼接”出的最小数了。按照这种思路，对每一个数字（以字符串形式存储）都这样排序，最后逐个输出的结果就是题目要求的最小数字了。
确定要用字符串了后，直接使用STL内的string类可以很方便的对字符串进行操作。
注意，当输入的全部为0时，需要特判输出0。
Code
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
26
27
28
using namespace std;
int main() {
vector<string> strs;
int n;
cin >> n;
for(int i = 0; i < n ; i++) {
string tmp;
cin >> tmp;
strs.push_back(tmp);
}
sort(strs.begin(), strs.end(), [](string &a, string &b) {
return a + b < b + a;
});
string ans;
for(int i = 0; i < n; i++) {
ans += strs[i];
}
while(ans.length() != 0 && *ans.begin() == '0') {
ans.erase(ans.begin());
}
if(ans.length() == 0) cout << "0";
else cout << ans;
return 0;
}
这个题的贪心策略就是局部最优，然后达到的全局最优。
1039 Course List for Student
Analysis
题目大意是给定课程数目和每门课程参加的学生姓名，当用学生姓名查找时，输出该名学生所有的课程。
根据题目要求，需要保存每名学生的选课信息，课程都是用数字代替的，所以使用数组就可以满足需求。由于需要按序输出每名学生的课程编号，所以需要对每名学生的课程编号进行排序；并且，还需要先输出该名学生选课的总数。综合考虑后，使用vector来保存数据比较合适。另外为了便于查找，采用散列的思想，将学生的姓名转换为数字，作为下标来保存数据。
Code
1 |
|
现在时间限制放宽到了600ms，所以可以放心大胆的用 map、cin 和 cout 了：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
using namespace std;
unordered_map<string, vector<int>> stu;
int main() {
int n, k;
cin >> n >> k;
string name;
while(k--) {
int cid, amount;
cin >> cid >> amount;
for(int i = 0; i < amount; i++) {
cin >> name;
stu[name].push_back(cid);
}
}
while(n--) {
cin >> name;
cout << name << ' ' << stu[name].size();
sort(stu[name].begin(), stu[name].end());
for(int &i: stu[name]) {
cout << ' ' << i;
}
cout << endl;
}
return 0;
}
1040 Longest Symmetric String
Analysis
题目大意是给定一个字符串，找出其中的最长回文子串。
此题并没有设置超时测试点，直接使用暴力解法可以过。不过，这类最长公共子串（Longest Palindromic Substring）的题目，还有另外一种思路——动态规划。
Code
Violent Solution
1 |
|
DP
1 |
|
1041 Be Unique
Analysis
根据题目要求，最先猜到只出现一次的数字就赢了，所以得先按照顺序读入每个数，同时统计每个数字的出现次数。然后再按照输入顺序，检查每个数字的出现次数，若出现一次即为赢的那个数字。
Code
1 |
|
1042 Shuffling Machine
Analysis
根据题目的例子，读懂题目，注意仅在一个数组内交换元素会 WA ，要用两个数组进行倒换才能得到正确的结果。当然，也可以在每次倒换完成之后，将得到的序列直接放到结果数组中，这样就不用在判断了。
需要输出的字符串可以先写个循环输出，然后从黑框框中复制粘贴要初始化的二维数组中。如果不想这么干也可以只保存符号信息，也就是1
char cards[6] = "SHCDJ";
这样，数组中数字跟卡片类型下标的对应关系就是index = (arr[i] - 1) % 13，那序号呢？实际上也是差不多的，也就是(arr[i] - 1) % 13 + 1，所以就可以得到第二个版本的代码。
Code
version 1
1 |
|
version 2
1 |
|
1043 Is It a Binary Search Tree
Analysis
Code
1 |
|
1044 Shopping in Mars
Analysis
先分析题目输入，第一行给定两个数字，第一个数字代表一条“链”上钻石的数量，第二个数字则代表需要支付的钱；第二行依次给出“链”上每颗钻石的对应的价值（用于支付）。
然后，题目要求从这条“链”中找出能刚好用于支付（钻石的价值和与待支付的钱相等）的“钻石序列”，当然，若是没有完全相等的情况，找出刚好大于待支付的钱的钻石序列，也是可以的。
将本体的题意抽象出来就是，给定一个序列，找出这个序列中连续子序列和刚好大于或等于给定数字的所有子序列（如果有相等的情况，就不需要再找大于的情况）。
按照这样的思路，可以使用一个sum数组来保存连续的子序列和（每次累加即可），这样在i和j之间的子序列和就是sum[j] - sum[i - 1]，这个思想与 1046 是一致的。这样，要做的事情就是从sum这个数组中找出满足条件的序列了。同时注意到，由于sum数组是累加得出的，所以一定是严格递增的，也就可以使用二分查找来找这个值。
注意题目的条件：It is guaranteed that the total value of diamonds is sufficient to pay the given amount.，说明肯定会有解，那么对应的也就只有两种情况：
- 能找到相等的序列，此时由于序列本身就是严格递增的
- 只能找到刚好大于给定值的序列，此时需要用一个变量
nearS来保存刚好大于给定值的连续子序列和
找到合理的值后，按照这个值输出即可。
Code
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
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
using namespace std;
vector<pair<int, int>> ans1, ans2;
const int maxn = 100000 + 5;
int arr[maxn];
long long prefixsum[maxn];
int main() {
int n, m;
cin >> n >> m;
prefixsum[1] = 0;
for(int i = 1; i <= n; i++) {
cin >> arr[i];
prefixsum[i + 1] = prefixsum[i] + arr[i];
}
int left = 1, right = 2, minimum = 1000;
while(left <= n) {
while(right <= n + 1) {
if(prefixsum[right] - prefixsum[left] < m) right++;
else if(prefixsum[right] - prefixsum[left] == m) {
if(right > left) ans1.push_back({left, right - 1});
else if(right == left) ans1.push_back({left - 1, right - 1});
break;
} else if(prefixsum[right] - prefixsum[left] > m) {
int tmp = prefixsum[right] - prefixsum[left] - m;
if(tmp < minimum) {
ans2.clear();
minimum = tmp;
if(right > left) ans2.push_back({left, right - 1});
else if(right == left) ans2.push_back({left - 1, right - 1});
} else if(tmp == minimum) {
if(right > left) ans2.push_back({left, right - 1});
else if(right == left) ans2.push_back({left - 1, right - 1});
}
break;
}
}
left++;
}
if(ans1.size() != 0) {
sort(ans1.begin(), ans1.end());
for(auto p: ans1) {
cout << p.first << '-' << p.second << endl;
}
} else {
sort(ans2.begin(), ans2.end());
for(auto p: ans2) {
cout << p.first << '-' << p.second << endl;
}
}
return 0;
}
这个题的测试用例中没有 0 的存在...弱了不少
1045 Favorite Color Stripe
Analysis
题目大意：用不同的数字表示不同的颜色，一共有 220 种颜色，给定一串数字序列，作为 Eva 喜欢的颜色种类（越靠后越喜欢），然后在给定一串数字序列。现在从中挑出 Eva 喜欢的所有数字，并且要求按照给定的顺序进行排列，求出这个最大的长度。
如果直接使用暴力解法，定会超时，要想完美解决这个问题，思考的方向有两个，但都包含了动态规划（Dynamic Programming）的思想：
- 从最长非递减序列的角度思考
- 从最长公共子串的角度思考
Code
LIS
1 |
|
LCS
1 |
|
1046 Shortest Distance
Analysis
题目意思很明确，给你一个“环”形地图，问你从这里到那里怎么走最近。根据题目意思，一般都有两种走法，一种顺着环走，一种逆着环走，找出二者的最小值即可。
一般而言，我们分别找出其中两次的值，进行比较后输出最小值即可。不过由于地名是按照数字给出的，可能会出现起始点的数字大于终点的情况，此时最好交换二者的值，或者分情况讨论。
另外，还可以发现，如果求出了一种走法，那么按照环形地图的特点，利用总距离减去求得的不就得到另一种走法的距离了吗？
把握住上面的点后，可以通过 0 和 1 两个测试点了，第三个测试点会因为超时无法通过。
在仔细分析一下，如果一开始用一个数组Dis[MAXN]，按照顺序表示1号地点到达其他地点的距离，那么对于每一次查询的start和end，其距离就是Dis[end - 1] - Dis[start - 1]。以样例为例，可以得到数组（下标从1开始）Dis[6] = {0, 1, 3, 7, 21, 30}，此时如果要计算5到2的距离，根据思路就是：Dis[5 - 1] - Dist[2 - 1] = 21 - 1 = 20，这就是按顺序方向从2到5的距离。
此法恐怖之极在于原本时间复杂度为 $O(n)$ 的查找一下子就变为 $O(1)$ 了。
Code
1 |
|
1047 Student List for Course
Analysis
此题与1039的题目背景完全一样，输入与输出正好相反，思路也是类似的。只是本题，不需要在利用散列了。
这个题也可以用string来做，但是耗费的时间会长一些，用数字来代替字符串的比较会方便快捷很多。不过这个题，用string也可以过。
Code
use number
1 |
|
use string
1 |
|
1048 Find Coins
Analysis
给定硬币种类和面值，按照题目要求输出和与题目相等两枚硬币，要求V1的面值小于等于V2。在输入时，利用散列的思路，先将每一枚硬币的个数统计下来。然后，利用sort将面值按升序排序，这样方便查找。输出时注意以下几点：
V1和V2相等时，要判断这枚硬币时候是否有两枚- 当
V1和V2相等时，就已经是题目要求的最后一种情况了，若这种情况都不合条件，就没必要再继续查找下去了，所以使用一个标识flag来协助输出 - 注意所使用数组的下标，以免调用
sort时出错 - 只要
V1最小的那一组就行了，所以要在循环内调用break
Code
1 |
|
有了 C++ 的 map 就不需要在排序了：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
using namespace std;
int main() {
int n, m, tmp;
cin >> n >> m;
map<int, int> ht;
for(int i = 0; i < n; i++) {
cin >> tmp;
ht[tmp]++;
}
bool flag = false;
for(auto it = ht.begin(); it != ht.end(); it++) {
int diff = m - it->first;
if(diff == it->first) {
if(it->second >= 2) {
cout << it->first << ' ' << it->first;
flag = true;
break;
}
} else {
if(ht.count(diff)) {
cout << it->first << ' ' << diff;
flag = true;
break;
}
}
}
if(!flag) cout << "No Solution";
return 0;
}
再贴个二分的思路：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
using namespace std;
int main() {
int n, m;
cin >> n >> m;
vector<int> arr(n);
for(int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr.begin(), arr.end());
bool flag = false;;
for(auto v1 = arr.begin(); v1 != arr.end(); v1++) {
auto v2 = lower_bound(arr.begin(), arr.end(), m - *v1);
if(v1 != v2 && *v1 + *v2 == m) {
cout << *v1 << ' ' << *v2;
flag = true;
break;
}
}
if(!flag) cout << "No Solution";
return 0;
}
1049 Counting Ones
Analysis
题意很简单，给定一个数字 n，算出从 1 到 n 所有的数字中 1 的个数和。
Code
这个题原来的时间限制是 10 ms，现在改成了 400 ms，所以直接暴力也能有 22 分。不过要想拿到满分，需要从数学的角度来分类讨论一下。
对于一个数的每一位数字 $mid$ 而言：
- 若 $mid$ 为 0，要使 $mid$ 一定能取到 1，那么其左边的数字只能取 $[0, n / 10 ^ {k+1} - 1]$，其中 k 是右边数字的位数，而其右边的数则可以取到 $[0, 10^k - 1]$，那么总共能取到的数字就是 $n / 10 ^ {k+1} \times 10^k$。
- 若 $mid$ 为 1，其左边的数字只能取 $[0, n / 10 ^ {k+1}]$，其中 $k$ 是右边数字的位数。此时，当左边数字取 $[0, n / 10 ^ {k+1} - 1]$ 时，右边数字可以取 $[0, 10 ^ k - 1]$；当左边数字取 $n / 10 ^ {k+1}$ 时，右边数字只能取 $[0, n \% 10^{k}]$。那么总共能取到的数字就是 $n / 10 ^ {k+1} \times 10^k + n % 10^{k} + 1$。
- 若 $mid$ 大于 1，左边能取到的数字就是 $[0, n / 10 ^ {k+1}]$，右边能取到的数字就是 $[0, 10 ^ k - 1]$，那么总共能取到的数字就是 $(n / 10 ^ {k+1} + 1) \times 10^k$。
所有数字中 1 的个数就是依次拆分数位分类讨论后的总和。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
using namespace std;
int main() {
int n, ans = 0;
cin >> n;
int mask = 1, left, mid, right;
while(n / mask != 0) {
left = n / (mask * 10);
mid = n / mask % 10;
right = n % mask;
if(mid == 0) ans += left * mask;
else if(mid == 1) ans += left * mask + right + 1;
else ans += (left + 1) * mask;
mask *= 10;
}
cout << ans;
return 0;
}
这个题思路不是那么好想。
1050 String Subtraction
Analysis
利用散列的思想来处理，先遍历第一个字符串统计其中所有字符的出现次数（也可以只用true或false来区分），然后遍历第二个字符串，将同时出现在两个字符串内的字符的次数标记为0，然后按照第一个字符串的顺序，输出标记不是0的字符即可。
Code
1 |
|
1051 Pop Sequence
Analysis
题目大意是给定一个栈的容量、出战序列长度和可能的出栈序列，判断在当前栈的长度下，出栈序列是否合法，若是，输出YES，反之，输出NO。
按照题目的要求模拟栈的操作即可，使用 C++ 的stack容器可以很方便的完成这个需求。
注意每次判断要让栈清空，不然会影响判断。不过与其反复清空栈，不如直接新建一个。
Code
1 |
|
1052 Linked List Sorting
Analysis
题目背景是属于链表的应用，实际是模拟链表的操作，使用静态链表模拟较为方便。
静态链表需要借助散列的概念，借助结构数组，使用题目给定的地址对应数组的下标，可以较为方便的存储结点值和下一个元素的地址。
题目要求的排序可以使用sort函数来完成，此时要注意由于题目可能会输入无效结点，所以需要增加一个flag来判断是否属于无效结点，这样sort函数才能将有效结点按序排好，并将无效结点排在最后一个有效结点的后面。
Code
1 |
|
1053 Path of Equal Weight
Analysis
Code
1 |
|
1054 The Dominant Color
Analysis
题目大意是给定一个矩阵，找出其中超过矩阵一半元素个数的值。题目保证测试样例中会有答案，也就是说，有一半的矩阵元素都是同一个数字，那么毫无疑问，这个元素的出现次数一定是这个矩阵所有元素出现次数的最大值，所以直接查找最大值即可。
由于像素点是由0-24位数字字符组成，所以需要将矩阵内元素当作字符串对待，同时需要建立与次数的唯一映射，使用 C++ 的map容器可以很方便的完成这个操作。
Code
1 |
|
用 C++11 标准写简单一点：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
map<int, int> ht;
int main() {
int m, n, tmp;
cin >> m >> n;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
cin >> tmp;
ht[tmp]++;
}
}
int ans, condition = (m * n) / 2;
for(auto &p: ht) {
if(p.second > condition) ans = p.first;
}
cout << ans;
return 0;
}
1055 The World’s Richest
Analysis
先按照题目要求排好序，然后按照题目给定的年龄区间进行输出，注意没有符合的输出时，需要输出None。
此时，考虑到题目给的条件$M (\le 100)$，说明对于同一个年龄的数据，最多只输出100项。所以可以新建一个数组，然后按照排好序的序列，顺序保存每个年龄的数据，但只保存100个，这样在查找的时候能极大的节约时间。
尽管这道题在甲级题库内的时间限制是500ms，考试的时候说不定就是200ms了，要注意用最优解法。
Code
1 |
|
贴个 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
using namespace std;
const int maxn = 100000 + 5;
struct people {
string name;
int age, worth;
} peo[maxn], output[maxn];
int Age[maxn] = {0};
bool cmp(people a, people b) {
if(a.worth != b.worth) return a.worth > b.worth;
else if(a.age != b.age) return a.age < b.age;
else return a.name < b.name;
}
int main() {
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++) {
cin >> peo[i].name >> peo[i].age >> peo[i].worth;
}
sort(peo, peo + n, cmp);
int index = 0;
for(int i = 0; i < n; i++) {
if(Age[peo[i].age] < 100) {
Age[peo[i].age]++;
output[index++] = peo[i];
}
}
int M, amin, amax;
for(int i = 1; i <= k; i++) {
cout << "Case #" << i << ":" << endl;
cin >> M >> amin >> amax;
int cnt = M;
for(int i = 0; i < index; i++) {
if(amin <= output[i].age && output[i].age <= amax) {
cout << output[i].name << ' ' << output[i].age << ' ' << output[i].worth << endl;
if(--cnt == 0) break;
}
}
if(cnt == M) cout << "None" << endl;
}
return 0;
}
cin 和 cout 确实比 scanf 和 printf 慢了许多...
1056 Mice and Rice
Analysis
题目背景是一个叫做 Mice and Rice 的游戏，根据题目的描述可以知道，体重数字最大的老鼠就是胜利的老鼠，并且在本题中，老鼠之间的比赛需要分组进行，分组大小会给出。注意all the mice left will be put into the last group是指，由于可能存在最后一组老鼠少于分组大小的情况，默认将剩余的老鼠全部加入到下一轮比赛中。依次进行每一轮比赛，直至最后得到冠军老鼠，并输出所有老鼠的排名。
按照题目的意思，题目一开始会给定老鼠总数和分组大小，所以可以直接得到这一轮的分组数；同理，每一轮的分组数都可以这样得到。
Code
1 |
|
1058 A+B in Hogwarts
Analysis
题目意思很简单，给你两个在霍格沃茨本地使用的货币数量，加起来就好。就跟生活中$100 + 150 = 250$块一样哈。
Code
1 |
|
贴个简单版：
k1 和 k2 的和可能会超过 int 的范围，所以要使用 long long。1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main() {
long long g1, s1, k1, g2, s2, k2;
scanf("%lld.%lld.%lld %lld.%lld.%lld", &g1, &s1, &k1, &g2, &s2, &k2);
k1 += s1 * 29 + g1 * 29 * 17;
k2 += s2 * 29 + g2 * 29 * 17;
k1 += k2;
g1 = k1 / 29 / 17;
s1 = k1 / 29 % 17;
k1 = k1 % 29;
printf("%lld.%lld.%lld\n", g1, s1, k1);
return 0;
}
1059 Prime Factors
Analysis
题目大意是给定一个正整数，用质数对其进行分解，也即质因子分解。
既然需要用到质数，与其一个一个的判断，不如一开始先将素数表打印好，此题给定的数为long int，则素数表为$10^5$即可。
接着定义一个结构体数组，保存质因子和其个数。对于long int型的数而言，2 * 3 * 5 * 7 * 11 * 13 * 17 * 19 * 23 * 29就已经溢出了，所以结构体数组的大小取10以上即可。
从小到大枚举质因子，如果能整除给定的数，就进入循环，让这个数不断的整除它，从而计算这个质因子的数目。注意，n = 1时，需要特判输出1=1。
Code
1 |
|
贴个 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
using namespace std;
map<long long, int> factors;
bool isprime(long long n) {
if(n <= 1) return false;
else {
for(long long i = 2; i <= sqrt(n); i++) {
if(n % i == 0) return false;
}
return true;
}
}
int main() {
long long n, tmp, sqr;
scanf("%lld", &n);
printf("%lld=", n);
if(n == 1) printf("%lld", n);
else {
tmp = n;
sqr = sqrt(n);
for(long long fa = 2; fa <= sqr; fa++) {
if(tmp == 1) break;
if(isprime(fa)) {
while(tmp % fa == 0) {
factors[fa]++;
tmp /= fa;
}
}
}
if(factors.size() == 0) printf("%lld", n);
else {
auto it = factors.begin();
while(it != factors.end()) {
printf("%lld", it->first);
if(it->second != 1) printf("^%d", it->second);
it++;
if(it != factors.end()) printf("*");
}
}
}
return 0;
}
同样，一个数的最大因子不会超过它的算术平方根，所以循环边界直接用就好了。有了 map 之后，就可以很方便的统计质因子和对应的个数。
1060 Are They Equal
Analysis
这道题考察字符串处理，使用STL内的string容器，并调用其中的一些方法，会十分方便。
Code
1 |
|
1061 Dating
Analysis
这道题与乙级题库的1014是一样的，不难，就是有些地方好像说的不太明确，比如，星期这个信息必须得是属于 $[A, G]$ 的大写字母才能可以进行判断...
Code
1 |
|
1062 Talent and Virtue
Analysis
此题与乙级题库 1015 一样。
Code
1 |
|
1063 Set Similarity
Analysis
题目大意是给定若干个集合，给出两个集合的“相似程度”。这里的“相似程度”是指两个集合交集的元素个数除以两个集合并集的元素个数的百分比，且没有重复元素。
按照题目背景，使用 STL 的set来处理这个问题比较方便，优点如下：
set在存储数据时，会自动去除重复数据set内元素的个数，可以直接使用set.size()得到- 查找
set内元素时，直接使用set.find(elements)即可
使用set读入所有输入数据后，开始查询。每次查询需要得到一个百分比，所以就需要求两个集合交集的元素个数和并集的元素个数。
具体方法是：遍历其中一个集合，令totalNum为另一个集合的元素个数，sameNum为相同元素的个数（初始化为0）。此时在另一个集合中查找当前遍历的集合中的元素，若存在，则sameNum++，反之则totalNum++，遍历结束后，需要的数字就算好了，接着相除得到百分比即可输出。
Code
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
26
27
28
29
30
using namespace std;
const int maxn = 50 + 5;
set<int> st[maxn];
int main() {
int n, m, k;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> m;
for(int j = 0; j < m; j++) {
int tmp;
cin >> tmp;
st[i].insert(tmp);
}
}
cin >> k;
while(k--) {
int set1, set2, nc = 0, nt;
cin >> set1 >> set2;
nt = st[set2].size();
for(auto &tmp: st[set1]) {
if(st[set2].count(tmp)) nc++;
else nt++;
}
printf("%.1lf%%\n", nc * 100.0 / nt);
}
return 0;
}
1064 Complete Binary Search Tree
Analysis
题目大意是给定结点个数和结点值，建立一颗完全二叉排序树（CBT），根据名称，可以知道这类树既有完全二叉树的性质，又有二叉排序树的性质。
经过上面的分析，使用结构数组建树就十分方便，对完全二叉树而言，数组的下标即代表结点之间的关系，所以直接使用整型数组即可，并且在数组的顺序就是层次遍历的序列。接着要解决的问题就是将结点值赋给结点，根据二叉排序树的性质，利用中序遍历即可完成这个需求。
Code
1 |
|
1065 A+B and C (64bit)
Analysis
这道题算是乙级题目1011 A+B 和 C的加强版了，题目给定的数据范围是$(-2^{63}, 2^{63})$，正好是64位带符号整型的数据范围，下面来分析可能出现的各种情况（只用对A和B之和分析就好）：
A和B之和仍然在$(-2^{63}, 2^{63})$之内，可以直接与C进行判断A和B之和大于$2^{63}$，此时会发生正溢出，且其值的范围为：$[-2^{63}, -2]$（溢出进位，符号为从0变为1，所以为负，剩下63位构成的数字就在这个范围内了）。A和B之和小于$-2^{63}$，此时会发生负溢出，其值范围为：$[0, 2^{63})$（原理类似）
对应上述三种情况，按照实际规则进行比大小即可。
Code
1 |
|
以上是原来未更新测试数据之前的 AC 代码，现在只能拿到 16 分了，最后一个测试点无法通过。
究其原因，其实是这个题目又开始玩文字游戏了，C 的范围是 $(2^{-63}, 2^{63})$，但 A 和 B 不是的，也就是说 A 和 B 的位数可能要超过 9223372036854775807。
从这里开始，这个题考察的内容就不再是对数据溢出的判断了，那考察什么？考察的是cin和scanf 从输入流获取输入的差别，也不知道这样改是为了什么😓。
至于cin和scanf有什么区别，得单独写文章总结，现在贴出 AC 的代码（其实就只是换掉了cin而已）：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
using namespace std;
int main() {
long long t, a, b, c;
cin >> t;
for(int i = 1; i <= t; i++) {
scanf("%lld %lld %lld", &a, &b, &c);
cout << "Case #" << i << ": ";
if(a + b < 0 && a > 0 && b > 0) cout << "true"; // positive overflow
else if(a + b >= 0 && a < 0 && b < 0) cout << "false"; // negative overflow
else if(a + b > c) cout << "true"; // normal
else cout << "false";
cout << endl;
}
return 0;
}
看到这里，一上来就用cin的人，估计要被气吐血了。按照出题人的意图和这道题的分值而言，考察了溢出的相关知识就可以了。这样改了之后，还需要对库函数有一定的了解。当然，直接上来就用scanf的，当我没说。
但针对这道题而言，还有一种做法，那就是选用更高精度的数据类型 long double，如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
using namespace std;
int main() {
int t;
cin >> t;
for(int i = 1; i <= t; i++) {
long double a, b, c;
cin >> a >> b >> c;
cout << "Case #" << i << ": ";
if(a + b < 0 && a > 0 && b > 0) cout << "true"; // positive overflow
else if(a + b >= 0 && a < 0 && b < 0) cout << "false"; // negative overflow
else if(a + b > c) cout << "true"; // normal
else cout << "false";
cout << endl;
}
return 0;
}
在 C++11 标准中测试，long double的数据类型占了 16 个字节，能表示相当大的数了。
1066 Root of AVL Tree
Analysis
题目大意给定一棵树的结点个数，再给定各个结点的值，建立一颗平衡二叉树（AVL），然后输出结点的值即可。
由于题目需要建立 AVL 树，依据 AVL 树的性质，每个结点的平衡因子绝对值不能大于1，所以在插入每个结点时，需要对树进行调整，使其满足 AVL 树的性质。
AVL 树失衡的情况总共有4种：LL、LR、RR 和 RL 四种，会根据每种情况做对应的旋转即可。注意每次插入结点时都需要检查树是否失衡，这样能够及时调整。
Code
1 |
|
1067 Sort with Swap
Analysis
这道题考察贪心，参杂了一些模拟。
对待贪心类的题目，必须得找准贪心的策略，不然就没法解题了，得仔细观察样例。假设数字都存储在数组中，按照题目的说明，可以发现：0值每次交换的对象都是下标值与其本身值不一样的数字。所以，每次将0值与具有上述特点的值交换即可；但要注意，若0的下标为0时，算法就无法继续进行了，此时需要特别处理下，将0与当前值最小且具有上述特点的数字直接进行交换。
这时可以发现，如果从数组头部开始向后查找这样的数字，就会有很多已经排好的数被遍历到。为了避免这样的情况，需要将当前值最小且具有上述特点的数字保存在一个变量内，这样下次查找时直接从这个数字开始就可以避免重复查找的情况了。
Code
1 |
|
贴个 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
using namespace std;
const int maxn = 100000 + 5;
int arr[maxn];
unordered_map<int, int> numandindex;
int main() {
int n, cnt = 0;
cin >> n;
for(int i = 0; i < n; i++) {
cin >> arr[i];
numandindex[arr[i]] = i;
}
int index0 = numandindex[0], i = 0;
while(true) {
if(index0 == 0) {
for(; i < n; i++) {
if(arr[i] != i) break;
}
if(i != n) {
numandindex[arr[i]] = 0;
numandindex[0] = i;
} else break;
}
int index = numandindex[index0];
swap(arr[index0], arr[index]);
cnt++;
index0 = index;
}
cout << cnt;
return 0;
}
本质上是下标在交换，所以用一个 map 来建立数组元素与对应下标的映射，这样理解起来会清楚一些。
1069 The Black Hole of Numbers
Analysis
此题与乙级题库的1019一样
Code
1 |
|
1070 Mooncake
Analysis
此题与乙级题库的1020类似（好像只是数据不一样），考察贪心。
Code
1 |
|
1071 Speech Patterns
Analysis
题目要求输入一句话，输出其中出现次数最长的字符串，字符串只能包含0-9、A-Z和a-z内的字符，其他字符均被认为是字符串之间的分隔符。
先将字符串整行读入，在逐个拆分出每个单词，并利用map来建立字符串（string）与次数（int）之间的映射，每统计到相同的字符串，次数加1。
输出时，遍历map，找出其中出现次数最多的字符串即可。
Code
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
26
27
28
29
30
31
32
using namespace std;
map<string, int> stringcnt;
const int maxn = 1048576 + 10;
int main() {
string str, tmp;
getline(cin, str);
int maxcnt = 0;
for(int i = 0; i < str.length(); i++) {
if(isalnum(str[i])) {
if(isupper(str[i])) str[i] = tolower(str[i]);
tmp.push_back(str[i]);
}
if(!isalnum(str[i]) || i == str.length() - 1) {
if(tmp != "") {
stringcnt[tmp]++;
maxcnt = max(maxcnt, stringcnt[tmp]);
}
tmp.clear();
}
}
for(auto &p: stringcnt) {
if(p.second == maxcnt) {
cout << p.first << ' ' << p.second;
break;
}
}
return 0;
}
以为可以直接用空格字符作为单词的分隔符，结果仔细一看Here a "word" is defined as a continuous sequence of alphanumerical characters separated by non-alphanumerical characters or the line beginning/end.，也就是说题目没说一定会用空格来分隔单词，这样就没法利用 cin 和 scanf 自动按空格读入特性了，只能获取一行后逐个提取出来。最后一个单词的结尾也可能是字母、数字，所以也要统计在内，测试点 4 应该是这样。
1072 Gas Station
Analysis
题目大意是给定若干个源点和固定点，求这些源点到所有固定点距离最小的源点，如果存在相同解，就输出平均距离最小的源点。
按照题目大意，可以将题目描述抽象为图，接着利用 Dijkstra 算法就可以求解源点到固定点的最短距离；由于题目给定的源点有多个，所以要使用多次 Dijkstra 算法，所以每次执行算法之前需要将用到的bool数组初始化为false。然后，按照题目条件来判断或筛选最优解。
Code
1 |
|
1073 Scientific Notation
Analysis
此题与乙级题库的1024一样。
Code
1 |
|
1074 Reversing Linked List
Analysis
此题与乙级题库的1025一样。
Code
1 |
|
1075 PAT Judge
Analysis
考察排序，题目说明比较多，要仔细读题。关键是输入数据的处理，处理后要达到便于排序（与题目一致）和输出的效果。
Code
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
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
using namespace std;
const int maxn = 10000 + 5;
struct student {
int id, grade[6], cnt;
bool flag;
} stu[maxn];
int perfect[6], n, k, m;
bool cmp(student a, student b) {
if(a.grade[0] != b.grade[0]) return a.grade[0] > b.grade[0];
else if(a.cnt != b.cnt) return a.cnt > b.cnt;
else return a.id < b.id;
}
void Init() {
for(int i = 0; i < maxn; i++) {
stu[i].id = i;
stu[i].cnt = 0;
stu[i].flag = false;
memset(stu[i].grade, -1, sizeof(stu[i].grade));
stu[i].grade[0] = 0;
}
}
int main() {
scanf("%d %d %d", &n, &k, &m);
Init();
for(int i = 1; i <= k; i++) {
scanf("%d", &perfect[i]);
}
int id, grade, pronum;
for(int i = 0; i < m; i++) {
scanf("%d %d %d", &id, &pronum, &grade);
if(grade != -1) stu[id].flag = true;
if(grade == -1 && stu[id].grade[pronum] == -1) stu[id].grade[pronum] = 0;
if(grade == perfect[pronum] && stu[id].grade[pronum] < perfect[pronum]) stu[id].cnt++;
if(grade > stu[id].grade[pronum]) stu[id].grade[pronum] = grade;
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= k; j++) {
if(stu[i].grade[j] > 0) stu[i].grade[0] += stu[i].grade[j];
}
}
sort(stu + 1, stu + n + 1, cmp);
int rank = 1;
for(int i = 1; i <= n && stu[i].flag; i++) {
if(i > 1 && stu[i].grade[0] != stu[i - 1].grade[0]) rank = i;
printf("%d %05d %d", rank, stu[i].id, stu[i].grade[0]);
for(int j = 1; j <= k; j++) {
if(stu[i].grade[j] == -1) printf(" -");
else printf(" %d", stu[i].grade[j]);
}
putchar('\n');
}
return 0;
}
1076 Forwards on Weibo
Analysis
Code
1 |
|
1077 Kuchiguse
Analysis
本题的实质是在求字符串的最长相同后缀，从后遍历字符串比较麻烦，所以采取先逆转字符串，然后从前遍历的做法，这样就会方便许多。
Code
1 |
|
贴个 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
using namespace std;
int main() {
int n, minlen = 0x3fffffff;
cin >> n;
getchar();
vector<string> strs;
for(int i = 0; i < n; i++) {
string tmp;
getline(cin, tmp);
reverse(tmp.begin(), tmp.end());
strs.push_back(tmp);
if(tmp.length() < minlen) minlen = tmp.length();
}
string ans;
bool flag = false;
for(int i = 0; i < minlen; i++) {
char tmp = strs[0][i];
for(int j = 1; j < n; j++) {
if(strs[j][i] != tmp) {
flag = true;
break;
}
}
if(flag) break;
ans += tmp;
}
reverse(ans.begin(), ans.end());
if(ans != "") cout << ans;
else cout << "nai";
return 0;
}
1078 Hashing
Analysis
题目大意是用线性探测的方法，构造哈希表，用平方探测的办法解决冲突。
Code
1 |
|
1079 Total Sales of Supply
Analysis
Code
1 |
|
1080 Graduate Admission
Analysis
这个题相当麻烦，基本思想是排序 + 贪心。
排序的规则很简单，第一判断依据是总分（不用与题目的计算公式一致），第二排序依据是 Ge 这个分数，顺序为非增序。排序的问题比较容易解决，难点在学校挑选学生上。
具体而言，整个录取过程是一个贪心的过程。首先按照分数，将每位学生的排名求出。然后根据排名，按照每位学生的选择，依次进行录取。之所以说是贪心，是因为以前面的选择优先（也就是第一志愿优先的规则），前面选择的学校名额不足时就顺排到后面的学校。
由于题目还要求，对于排名相同且选择相同学校的，学校应该扩额录取。所以需要记录下，在不超过限额的情况，每个学校能录取的最后一名的名次，并与后面的学生进行比较，如果排名相同，就得录取。
最后还有一点，学校的录取名单需要按照 id 非降序排序。
Code
1 |
|
贴个 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
using namespace std;
const int maxn = 40000 + 5;
struct student {
int ge, gi, id, rank;
int sum;
int choices[6];
} stu[maxn];
int n, m, k;
int quota[105] = {0};
int lastrank[105] = {0};
bool cmp(student a, student b) {
if(a.sum != b.sum) return a.sum > b.sum;
else return a.ge > b.ge;
}
int main() {
cin >> n >> m >> k;
for(int i = 0; i < m; i++) {
cin >> quota[i];
}
for(int i = 0; i < n; i++) {
cin >> stu[i].ge >> stu[i].gi;
stu[i].sum = stu[i].ge + stu[i].gi;
stu[i].id = i;
for(int j = 0; j < k; j++) {
cin >> stu[i].choices[j];
}
}
sort(stu, stu + n, cmp);
stu[0].rank = 1;
for(int i = 1; i < n; i++) {
if(stu[i].sum == stu[i - 1].sum && stu[i].ge == stu[i - 1].ge) stu[i].rank = stu[i - 1].rank;
else stu[i].rank = i + 1;
}
vector<vector<int>> ans(105);
for(int i = 0; i < n; i++) {
for(int j = 0; j < k; j++) {
int school = stu[i].choices[j];
if(quota[school] != 0) {
ans[school].push_back(stu[i].id);
quota[school]--;
lastrank[school] = stu[i].rank;
break;
} else {
if(stu[i].rank == lastrank[school]) {
ans[school].push_back(stu[i].id);
break;
}
}
}
}
for(int i = 0; i < m; i++) {
int size = ans[i].size();
if(size == 0) {
cout << endl;
continue;
} else {
sort(ans[i].begin(), ans[i].end());
cout << ans[i][0];
for(int j = 1; j < size; j++) {
cout << ' ' << ans[i][j];
}
cout << endl;
}
}
return 0;
}
1081 Rational Sum
Analysis
题目大意是给定N个a/b形式的分数，a为分子，b为分母，求这N个分数的和再输出。
给定的分数只有两种情况：真分数和假分数，不存在带分数，但输出要输出带分数，并且是最简形式。化简的目的其实题目考察求最大公约数，利用欧几里得算法即可求得两个数的最大公约数。
Code
1 |
|
贴个 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
using namespace std;
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
struct Fraction {
long long up, down;
void reduction() {
if(this->down < 0) {
this->up = - this->up;
this->down = - this->down;
}
if(this->up == 0) this->down = 1;
else {
long long d = gcd(abs(this->up), this->down);
this->up /= d;
this->down /= d;
}
}
void Add(Fraction b) {
this->up = this->up * b.down + this->down * b.up;
this->down = this->down * b.down;
this->reduction();
}
void Print() {
if(this->down == 1) printf("%lld", this->up);
else if(abs(this->up) > this->down) {
printf("%lld %lld/%lld", this->up / this->down, abs(this->up) % this->down, this->down);
} else printf("%lld/%lld", this->up, this->down);
printf("\n");
}
};
int main() {
int n;
scanf("%d", &n);
Fraction ans, tmp;
ans.down = 1, ans.up = 0;
while(n--) {
scanf("%lld/%lld", &tmp.up, &tmp.down);
ans.Add(tmp);
}
ans.Print();
return 0;
}
1082 Read Number in Chinese
Analysis
将数字按每4位一组分割为不同的组，若是 9 位数，则有三组分别为：个位组、万位组和亿位组，然后针对每一组单独进行判断。对每一小组而言，要注意1001只能输出为yi Qian ling yi而不是yi Qian ling ling yi，即有累积的0时，只能输出一个ling。
Code
1 |
|
1083 List Grades
Analysis
自定义结构体，输入数据后调用sort函数按照降序排序，然后根据题目给定的区间顺序输出符合这个区间内的元素即可。
Code
1 |
|
贴个 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
using namespace std;
const int maxn = 100000 + 5;
struct student {
string name, id;
int grade;
} stu[maxn];
int n;
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> stu[i].name >> stu[i].id >> stu[i].grade;
}
sort(stu, stu + n, [](student a, student b) {
return a.grade > b.grade;
});
int left, right, cnt = 0;
cin >> left >> right;
for(int i = 0; i < n; i++) {
if(left <= stu[i].grade && stu[i].grade <= right) {
cout << stu[i].name << ' ' << stu[i].id << endl;
cnt++;
}
}
if(!cnt) cout << "NONE" << endl;
return 0;
}
1084 Broken Keyboard
Analysis
遍历字符串，找出第一个字符串中出现过，但第二个字符串中未出现的字符即可，字母不区分大小写，但字符串内有空格和数字，用_表示，注意不能输出小写字母，且重复的字符只输出一次。
Code
1 |
|
1085 Perfect Sequence
Analysis
此题与乙级题库的1030一样。
Code
1 |
|
1086 Tree Traversals Again
Analysis
题目大意是给定用栈模拟二叉树中序遍历的入栈、出栈顺序，现在要求输出这个二叉树后序遍历序列。
根据题目给定的入栈、出栈序列，可以得到二叉树的先序遍历序列和后序遍历序列，根据这两个序列建树，然后再后序遍历这个二叉树即可。
Code
1 |
|
1087 All Roads Lead to Rome
Analysis
题目背景是旅游的路线图，要求按照条件求出最短路径及特定的值。
题目首先要求出的是从起点到终点的最短路径，由于不存在负环，所以可以直接使用 Dijkstra 算法求得；同时注意到，题目要求的某些特殊值与对应的路径可以在求解最短路时，一并求出，只不过需要使用多个数组而已。按照这样的思路，对题目要求的值增加对应的数组，并在求解最最短路的过程中写清楚这些条件之间的层次关系即可。
当然了，本题也可以使用 Dijkstra 算法先求出所有的最短路径，然后再利用 DFS 来求出符合条件的最优解和对应的值。
Code
Dijkstra
1 |
|
Dijkstra + DFS
1 |
|
1088 Rational Arithmetic
Analysis
此题与乙级题库的1034一样。
Code
1 |
|
贴个 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
using namespace std;
long long gcd(long long a, long long b) {
return b == 0 ? a : gcd(b, a % b);
}
struct Fraction {
long long up, down;
void reduction() {
if(this->down < 0) {
this->up = - this->up;
this->down = - this->down;
}
if(this->up == 0) this->down = 1;
else {
long long d = gcd(abs(this->up), this->down);
this->up /= d;
this->down /= d;
}
}
void Add(Fraction b) {
this->up = this->up * b.down + this->down * b.up;
this->down = this->down * b.down;
this->reduction();
}
void Minu(Fraction b) {
this->up = this->up * b.down - this->down * b.up;
this->down = this->down * b.down;
this->reduction();
}
void Mult(Fraction b) {
this->up = this->up * b.up;
this->down = this->down * b.down;
this->reduction();
}
void Div(Fraction b) {
this->up = this->up * b.down;
this->down = this->down * b.up;
this->reduction();
}
void printResult() {
this->reduction();
if(this->up < 0) printf("(");
if(this->down == 1) printf("%lld", this->up);
else if(abs(this->up) > this->down) {
printf("%lld %lld/%lld", this->up / this->down, abs(this->up) % this->down, this->down);
} else {
printf("%lld/%lld", this->up, this->down);
}
if(this->up < 0) printf(")");
}
};
int main() {
Fraction res, a, b;
scanf("%lld/%lld %lld/%lld", &a.up, &a.down, &b.up, &b.down);
res = a;
a.printResult();
printf(" + ");
b.printResult();
printf(" = ");
res.Add(b);
res.printResult();
printf("\n");
res = a;
a.printResult();
printf(" - ");
b.printResult();
printf(" = ");
res.Minu(b);
res.printResult();
printf("\n");
res = a;
a.printResult();
printf(" * ");
b.printResult();
printf(" = ");
res.Mult(b);
res.printResult();
printf("\n");
res = a;
a.printResult();
printf(" / ");
b.printResult();
printf(" = ");
if(b.up == 0) printf("Inf");
else {
res.Div(b);
res.printResult();
}
printf("\n");
return 0;
}
1089 Insert or Merge
Analysis
此题与乙级题库的1035一样。
Code
1 |
|
1090 Highest Price in Supply Chain
Analysis
Code
1 |
|
1091 Acute Stroke
Analysis
题目的背景大概是计算体积之和吧...
根据题目输入数据的形式和题目大意，思路是借助 BFS 对三维数组进行遍历，计算出每一个薄片（slice）中为“1”的个数，如果大于题目给定的T，则当前这个薄片内“1”的个数就可以认为是这个薄片的“急性脑卒中”区的体积。那么，依次遍历每个薄片即可得到最终结果。
Code
1 |
|
1092 To Buy or Not to Buy
Analysis
与乙级题库的1039一样。
Code
1 |
|
1093 Count PAT’s
Analysis
与乙级题库的1040一样。
Code
1 |
|
贴个 C++ 版：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
using namespace std;
int main() {
string str;
cin >> str;
int pcnt = 0, tcnt = 0;
for(char &ch: str) {
if(ch == 'T') tcnt++;
}
int ans = 0;
for(char &ch: str) {
if(ch == 'A') {
ans += tcnt * pcnt;
ans %= 1000000007;
} else if(ch == 'P') pcnt++;
else tcnt--;
}
cout << ans;
return 0;
}
1094 The Largest Generation
Analysis
Code
1 |
|
1095 Cars on Campus
Analysis
这又是一道相当麻烦的排序题，和 1016 很像，有些地方又比 1016 简单一点。
首先要注意的事情是，如何把题目的一些条件简化，比如时间全部简化成秒，这样排序时就可以直接按照秒数的大小进行排序了。不过，对于这个题而言，第一排序依据是plate_number，然后才是时间。排序完成后，需要将所有合法的记录对挑出来，作为后面查询每个时间内停车场内车辆数据的依据，也就是相邻的两个记录组成一对，plate_number相同，一个是in，另外一个是out。
此时，可以顺便把每辆车的停车时间和最长的停车时间算出来，每辆车的停车时间可以借助 map 来统计。
接着就是查询的过程，因为题目规定了给定的查询时间是从小到大的。所以，在查询前，先对合法记录按时间排序。然后，设置一个变量 now，从头开始进行遍历，遇到in的记录，当前车辆数就加 1，遇到out的记录，就减一，这样就只用遍历一次所有的合法记录。
最后就是输出停车时间与最长停车时间相等的车牌号和总时间了。
两个字：麻烦~🙃
Code
1 |
|
1096 Consecutive Factors
Analysis
题目大意是给定一个整数，找出其最长的因子序列并要求连续因子尽可能小，以样例为例，630=3*5*6*7，所以其连续因子序列为5*6*7，长度为 3 且此为其最长连续因子序列。
Code
1 |
|
贴个 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
using namespace std;
int main() {
int n;
cin >> n;
int anslen = 0;
vector<int> ans;
for(int i = 2; i <= sqrt(n); i++) {
int len = 0, j = i;
long long t = 1;
vector<int> tmp;
while(true) {
tmp.push_back(j);
t *= j;
if(n % t == 0) len++;
else break;
if(len > anslen) {
anslen = len;
ans = tmp;
}
j++;
}
}
if(anslen == 0) cout << 1 << endl << n;
else {
cout << anslen << endl;
for(int i = 0; i < anslen; i++) {
cout << ans[i];
if(i < anslen - 1) cout << '*';
}
}
return 0;
}
因为是从小到大枚举因子的，所以如果是符合条件的最终解，那么一定满足因子是最小的。实际上，这个题还可以从滑动窗口的角度来思考。
1097 Deduplication on a Linked List
Analysis
题目大意：给定一串链表的各个结点，删除其中重复的结点，并将删除的结点重新组成一个链表。然后，先输出原链表删除结点后的新链表，紧接着在输出由所删除的结点构成的链表。
使用静态链表来处理这个问题，先默认初始化链表内的所有结点全部为无效结点，即置为2 * maxn，然后将链表内所有结点根据地址存储。紧接着，遍历链表，使用一个bool数组来记录结点是否出现过，对于没有出现的合法结点，从0开始编号，出现过的结点，从maxn开始编号。最后，使用sort函数根据order来排序，就可以将结点按序分为删除结点后的链表、新链表和无效结点三部分，在输出即可。
注意要使用%05d来输出地址位数较少的结点。
Code
1 |
|
1098 Insertion or Heap Sort
Analysis
Code
1 |
|
1099 Build A Binary Search Tree
Analysis
题目大意给定一颗二叉排序树（BST），输出这棵树的层次序列。
根据题目输入数据的形式，利用结构数组建树比较方便。建树之后，中序遍历这棵树，将按升序排好的结点值序列，按照顺序赋给每个结点，这样每个结点的值就符合 BST 的性质了，接着层次遍历，输出其序列即可。
Code
1 |
|
1100 Mars Numbers
Analysis
此题与乙级题库的1044一样。
Code
1 |
|
1101 Quick Sort
Analysis
此题与乙级题库的1045一样。
Code
1 |
|
1102 Invert a Binary Tree
Analysis
题目大意是给定一个二叉树，反转这个二叉树并输出反转后的二叉树的中序序列和层序序列。
本题使用结构数组建树比较方便，并且反转时直接交换每个结点的左右孩子指针即可。然后再利用中序遍历和层序遍历，输出对应的序列。
Code
1 |
|
1103 Integer Factorization
Analysis
题目大意，给定三个数N、K和P，将N表示为K个因子的P次方的连加。
注意题目的要求：
- 因子之和必须最大
- 因子序列按字典序最大
由于存在多解的情况，本题需要借助 DFS 来搜索所有解，找到符合条件的最优解，对于上述两个题目的要求，其对应的解决方法：
- 使用全局变量，记录每个解和其因子和，选择因子和最大的为最优解
- 将因子的
P次方依次算好存储在数组中，然后从后往前枚举即可
Code
1 |
|
1104 Sum of Number Segments
Analysis
此题与乙级题库的1049一样。
Code
1 |
|
1106 Lowest Price in Supply Chain
Analysis
Code
1 |
|
1107 Social Clusters
Analysis
Code
1 |
|
