0%

2019程序设计能力实训第二次机考题解

2019程序设计能力实训第二次机考题解

题目链接:题目还没有公开

机考环境:CodeBlocks

编程语言:C++

#A. 点对

描述:从输入的偶数个数字里面两两选择,使得所有数对内部差的和为最小。

思路:排序后相邻的数差值总是最小的,所以只需排序并两两选择相邻数字即可。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>

typedef long long int ll;

using namespace std;

int main()
{
ll num,nums[100005] = {}, sum = 0;
cin>>num;
for(ll i = 0;i < num;i++){
cin>>nums[i];
}
sort(nums,nums+num);
for(ll i = 0;i < num;i+=2){
sum += nums[i + 1] - nums[i];
}
cout<<sum<<endl;
}
#B. QR Code

描述:

​ 比较繁琐的字符串与进制处理题。

​ 提供一个十进制表示的字符串s,将其按每3位转换为10位的二进制串,最后若剩余1位或2位则转换为4位或7位二进制字符串,叠加得到字符串res。

​ 最后的输出:”0001”+输入的s的长度对应的10位二进制字符串+res。

相关方法:

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
#include <iostream>
#include <string>
using namespace std;

int StrtoDec(string temp){ //十进制字符串转十进制数
int Dec = 0, weight = 1;
for(int i = temp.size() - 1;i>=0;i--){
Dec+=weight*int(temp[i]-'0');
weight*=10;
}
return Dec;
}

string DectoBin(int Dec,int num){ //十进制数转二进制
string bin = "";
int index = num - 1;
for(int i = 0;i<num;i++){
bin+='0';
}
while(Dec){
if(Dec%2){
bin[index]='1';
}
Dec /= 2;
index--;
}
return bin;
}

int main()
{
string s, temp, res = "";
int tag = 0,length = s.size(),index; //index指向末尾不成3个一组的一组数字的开头
cin>>s;
index = s.size()-s.size()%3;
for(int i = 0;i<index;i++){ //先处理三个一组的位
temp += s[i];
if(i % 3 == 2){ //每三位生成一个10位二进制串
int Dec = StrtoDec(temp);
res+=DectoBin(Dec,10);
temp = "";
}
}
for(int i = index;i<s.size();i++){ //如果剩下1、2位则加到temp上
temp+=s[i];
}
if(temp.size()==1){ //处理末尾1位的情况
int Dec = StrtoDec(temp);
res+=DectoBin(Dec,4);
}
else if (temp.size()==2){ //处理末尾2位的情况
int Dec = StrtoDec(temp);
res+=DectoBin(Dec,7);
}
cout<<"0001"<<DectoBin(s.size(),10)<<res<<endl;
return 0;
}
#C. 浮点数加法

描述:实现输入所要求精度的浮点数加法。输入的字符串可能会省略小数点、小数点前后的0。末尾四舍五入。

思路:

​ 首先需要做字符串处理,注意没有小数点、省略小数点前后的0的情形。

​ 随后,按精度对小数点后的位数进行分割或补充,原位数>精度时截取精度+1位(原因是末尾需要四舍五入,要多算一位),原位数<精度时补0)。

​ 分别用大整数方法加整数部和小数部。首先处理小数部末尾的进位,其次处理小数部头部的进位(看位数是否是精度+1,如果大于精度+1则说明有进位)。如进位则将小数部的头部([0]索引)加到整数部上并输出头部后的尾部(别忘了输出时删除用于四舍五入的末尾)。如无进位则输出小数部并剔除用于四舍五入的末位。

​ 还有一些暗坑没有发现,目前可以A过91分。

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
#include <iostream>
#include <string>
#include <regex>
using namespace std;

string add(string s1, string s2) { //大整数加法
string s;
int len1 = s1.size(), len2 = s2.size();
if (len1 < len2) {
for (int i = 1;i <= len2 - len1;++i) {
s1 = "0" + s1;
}
}
else {
for (int i = 1; i <= len1 - len2;++i) {
s2 = "0" + s2;
}
}
len1 = s1.size();
int Plus = 0, tmp;
for (int i = len1 - 1;i >= 0;--i) {
tmp = s1[i] - '0' + s2[i] - '0' + Plus;
Plus = tmp / 10;
tmp %= 10;
s = char(tmp + '0') + s;
}
if (Plus) {
s = char(Plus + '0') + s;
}
return s;
}

string split_int(string a,int index) { //从字符串中分割出整数部
string integer = "";
if(index == -1){ //省略小数点的情形
return a;
}
else if (index == 0){ //省略整数的情形
return "0";
}
else{
for(int i = 0;i<index;i++){
integer+=a[i];
}
}
return integer;
}

string split_flout(string a,int index) { //从字符串中分割出小数部
string flout = "";
if(index == -1){
return "0";
}
else if (index == a.size()-1){ //省略小数部分的情形
return "0";
}
else{
for(int i = index + 1; i<a.size();i++){
flout+= a[i];
}
return flout;
}
}

int find_index(string s){
for(int i = 0;i<s.size();i++){
if(s[i]=='.'){
return i;
}
}
return -1;
}

string format_flout(string s, int n) { //规范化小数位
int len = s.size();
if (n >= len) { //精度>原小数位数,补零
for (int i = 0;i < (n - len + 1);i++) {
s += "0";
}
}
else { //精度<=原小数位数,截断为长度为精度+1的字串
string temp = "";
for (int i = 0;i < n + 1;i++) {
temp += s[i];
}
s = temp;
}
return s;
}

int main()
{
string a, b, int_a, int_b, flout_a, flout_b, sum_flout, sum_int, sum = "", Plus = "";
int n, index_a, index_b;
cin >> a >> b >> n;

index_a = find_index(a); //记录小数点位置
index_b = find_index(b);

int_a = split_int(a,index_a); //a的整数部
flout_a = format_flout(split_flout(a,index_a), n); //a的小数部

int_b = split_int(b,index_b); //b的整数部
flout_b = format_flout(split_flout(b,index_b),n); //b的小数部

sum_flout = add(flout_a, flout_b);
sum_int = add(int_a, int_b);

if (sum_flout[sum_flout.size() - 1] > '4') { //末尾>4则四舍五入
sum_flout = add(sum_flout, "10");
}

int sum_flout_len = sum_flout.size();
if (sum_flout_len > n + 1) { //如果小数部长度大于精度+1则有进位
Plus += sum_flout[0]; //标记进位
sum_int = add(sum_int, Plus); //把小数部溢出的进位加给整数部
for (int i = 1;i < n + 1;i++) { //从第二位开始输出(第一位溢出进位了)
sum += sum_flout[i];
}
}
else {
for (int i = 0;i < n;i++) {
sum += sum_flout[i];
}
}
if(sum_int[0]=='0'&&sum_int.size()>1){ //sum_int有前导零
string temp = "";
for(int i = 0;i<sum_int.size();i++){
if(sum_int[i]!='0'){
temp+= sum_int[i];
}
}
sum_int = temp;
}
cout << sum_int << "." << sum << endl;
}
#D. 计算步数

描述:这道题目前还不会。

#E. 挑数字

描述:在 n 个正整数中挑选 m 个数。要使这 m 个数与其中最大的一个数之间的差值之和最小化。

思路:跟2018年实训第一次考试的圆柱体排序那道题原理一样。还有10分是数组超大了,还不知道怎么解决。

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
#include <iostream>
#include <algorithm>
typedef long long int ll;

using namespace std;

int main()
{
ll n,m,nums[100005],min_num;
cin>>n>>m;
for(ll i = 0;i < n;i++){
cin>>nums[i];
}
sort(nums,nums+n);
min_num = (m-1)*nums[m-1]; //随便初始化一个
for(ll i = 0;i < n-m+1;i++)
{
ll sum = (m-1)*nums[i+m-1];
for(ll j = 0;j < m-1;j++){
sum-=nums[j + i];
}
if(sum < min_num)
{
min_num = sum;
}
}
cout<<min_num<<endl;
}