【决赛】全国高校计算机能力挑战赛决赛C++组题解

12月1日09:58:59

决赛题目为6道编程题，题目不是很难。但是不能OJ，感觉要凉凉，因为我自己只会单纯的过测试样例。

1. 自动编码。给一个字符串，里面含有数字字符，将数字加3后模10的结果放在原位上。即’1’变成’4’，’2’变成’5’,’9’变成’2’，请输出变换后的字符串。

输入说明：一个字符串（长度小于255）。

输出说明：按照题目规则变换后得到的字符序列。

输入样例：-09-05A

输出样例：5345-32-38A

代码提交说明：

1.请严格按照每道题目给出的输入/输出样例编写相关I/O代码，数字间的默认间隔是一个空格，浮点数的默认输出精度是保持小数点后2位。样例以外的提示信息请不要在屏幕上输出。

2.请大家确保提交的代码可以在指定的编译条件下正确地编译执行，否则自动评测程序将给出编译错误或运行时错误的信息。

3.每道编程题目，如果没有特殊说明，需要在1秒内完成程序的运行和输出结果，超过这个时间限制将会被判超时，失去相应测试用例的分数。每个可执行文件可使用的空间不得大于64MB。

4.每道编程题会有多个测试用例，每通过一些测试用例可以获得相应的分值，但只有通过全部测试用例才能拿到这题全部的分数。

#include<iostream>using namespace std;int main(){string s;cin>>s;for(int i=0;i<s.length();i++){if(s[i]>='0'&&s[i]<='9'){s[i]=((s[i]-'0'+3)%10+'0');}}cout<<s;return 0;}

2. 求各种三维物体的体积，输入图形类型，之后是参数表，请计算它们的体积，按体积从大到小排序，输出这些体积的值。输入图形类型包括长方体Cu、球体Sp和圆柱体Cy。

输入说明：第一行是一个正整数N（0输出说明：从大到小排序后的体积，精度保留小数点后2位。

输入样例：3

Cu 3 4 5

Sp 3

Cy 3 6

输出样例：169.56 113.04 60.00

说明：π取值3.14

代码提交说明：

1.请严格按照每道题目给出的输入/输出样例编写相关I/O代码，数字间的默认间隔是一个空格，浮点数的默认输出精度是保持小数点后2位。样例以外的提示信息请不要在屏幕上输出。

2.请大家确保提交的代码可以在指定的编译条件下正确地编译执行，否则自动评测程序将给出编译错误或运行时错误的信息。

3.每道编程题目，如果没有特殊说明，需要在1秒内完成程序的运行和输出结果，超过这个时间限制将会被判超时，失去相应测试用例的分数。每个可执行文件可使用的空间不得大于64MB。

4.每道编程题会有多个测试用例，每通过一些测试用例可以获得相应的分值，但只有通过全部测试用例才能拿到这题全部的分数。

#include<iostream>#include<vector>#include<algorithm>using namespace std;int main(){string s;vector<float>v;char ch;while(cin>>s){float sum=0;if(s=="Cu"){int a,b,c;cin>>a>>b>>c;sum=a*b*c;v.push_back(sum);}else if(s=="Sp"){int a;cin>>a;sum=3.14*a*a*a*4/3;v.push_back(sum);}else if(s=="Cy"){int a,b;cin>>a>>b;sum=3.14*a*a*b;v.push_back(sum);}}sort(v.begin(),v.end());int flag=0;for(int i=0;i<v.size();i++){if(flag)printf(" ");flag=1;printf("%.2f",v[v.size()-i-1]);}return 0;}

3. 对给定的整数数组（数组长度N满足1〈N〈10000），选择一个位置，把数组分割为前后两个部分。求使得前后两个部分所有元素和的差值绝对值最大的分割位置（即使得分割后前后两部分数据的和尽可能悬殊）。如有多种分割情况，选择分割位置最小的情况输出。

输入说明：第一行是整数N，说明数组中元素个数，接下来一行是这N个数。

输出说明：一个整数，即前面部分包含的元素个数。

输入样例：6

11 102 13 24 35 46

输出样例：1

代码提交说明：

1.请严格按照每道题目给出的输入/输出样例编写相关I/O代码，数字间的默认间隔是一个空格，浮点数的默认输出精度是保持小数点后2位。样例以外的提示信息请不要在屏幕上输出。

2.请大家确保提交的代码可以在指定的编译条件下正确地编译执行，否则自动评测程序将给出编译错误或运行时错误的信息。

3.每道编程题目，如果没有特殊说明，需要在1秒内完成程序的运行和输出结果，超过这个时间限制将会被判超时，失去相应测试用例的分数。每个可执行文件可使用的空间不得大于64MB。

4.每道编程题会有多个测试用例，每通过一些测试用例可以获得相应的分值，但只有通过全部测试用例才能拿到这题全部的分数。

#include<iostream>#include<vector>#include<algorithm>using namespace std;int main(){int n;cin>>n;vector<int>num(n);int sum=0;for(int i=0;i<n;i++){cin>>num[i];sum+=num[i];}int sum2=0;int id=0;int maxsum=0;for(int i=0;i<n;i++){sum2+=num[i];if(abs(sum2-sum)>maxsum){id=i;maxsum=abs(sum2-sum);}}cout<<id+1;return 0;}

4. 铁艺加工厂有部分钢板加工余料，这些余料外观顶部呈现为阶梯方波状，如图1所示，请求出可切割出最大长方形铁皮的面积。图1左图黄色部分为最大可裁剪的长方形铁皮，右图蓝色部分为最大可裁剪的长方形铁皮。

输入说明：第一行是正整数N（0〈N〈100000），表示余料中的矩形个数。接下来是N行，每行给出每个矩形的宽和高。

输出说明：可以裁剪出的最大矩形面积，面积保留小数点后一位。

输入样例：5

5 3

2 2.5

5 3

3 4

6 4

输出样例：52.5

代码提交说明：

1.请严格按照每道题目给出的输入/输出样例编写相关I/O代码，数字间的默认间隔是一个空格，浮点数的默认输出精度是保持小数点后2位。样例以外的提示信息请不要在屏幕上输出。

2.请大家确保提交的代码可以在指定的编译条件下正确地编译执行，否则自动评测程序将给出编译错误或运行时错误的信息。

3.每道编程题目，如果没有特殊说明，需要在1秒内完成程序的运行和输出结果，超过这个时间限制将会被判超时，失去相应测试用例的分数。每个可执行文件可使用的空间不得大于64MB。

4.每道编程题会有多个测试用例，每通过一些测试用例可以获得相应的分值，但只有通过全部测试用例才能拿到这题全部的分数。

#include<iostream>#include<vector>using namespace std;struct ju{float a;float b;};int main(){float max=0;int n;cin>>n;vector<ju> ju(n);for(int i=0;i<n;i++){float a;float b;cin>>a>>b;ju[i].a=a;ju[i].b=b;}for(int i=0;i<n;i++){float len=0;float high=ju[i].b;for(int l=i;l<n;l++){len+=ju[l].a;if(high>ju[l].b){high=ju[l].b;}float sum=len*high;if(sum>max){max=sum;}//cout<<sum<<" "<<len<<" "<<high<<endl;} }printf("%.1f",max);return 0;}

5. 村村通：求解2个村庄之间的修路最低成本。输入包括两两村庄之间道路的建设成本。计算修筑给定两个村庄之间道路的最小建设成本，如果两村之间通过已知数据发现不能构成联通，输出-1。

输入说明：第一行是3个整数，分别表示村庄的数目N（村庄编号1~N，0〈N〈10000）和待求解的两个村庄的编号，之后是多行道路修筑成本信息，每行有3个整数，分别表示两个村庄的编号和修筑这两个村庄之间道路的建设成本，以-1 -1 -1结束。

输出说明：修筑指定村落间道路的最小建设成本。

输入样例：5 1 3

1 2 11

1 4 12

2 3 8

3 4 5

4 5 8

-1 -1 -1

输出样例：17

代码提交说明：

1.请严格按照每道题目给出的输入/输出样例编写相关I/O代码，数字间的默认间隔是一个空格，浮点数的默认输出精度是保持小数点后2位。样例以外的提示信息请不要在屏幕上输出。

2.请大家确保提交的代码可以在指定的编译条件下正确地编译执行，否则自动评测程序将给出编译错误或运行时错误的信息。

3.每道编程题目，如果没有特殊说明，需要在1秒内完成程序的运行和输出结果，超过这个时间限制将会被判超时，失去相应测试用例的分数。每个可执行文件可使用的空间不得大于64MB。

4.每道编程题会有多个测试用例，每通过一些测试用例可以获得相应的分值，但只有通过全部测试用例才能拿到这题全部的分数。

#include<iostream>#include<vector>using namespace std;int main(){int n,a,b;cin>>n>>a>>b;vector<vector<int>>v;for(int i=0;i<n+1;i++){vector<int >vv(n+1,99999);v.push_back(vv);}while(1){int na,nb,nn;cin>>na>>nb>>nn;if(na==-1&&nb==-1&&nn==-1){break;}v[na][nb]=nn;v[nb][na]=nn;}for(int i=1;i<=n;i++){if (v[a][i]!=99999){for(int l=1;l<=n;l++){if(v[a][l]>(v[i][l]+v[a][i])){v[a][l]=v[i][l]+v[a][i];}}}}cout<<v[a][b];return 0;}

6. 工地上需要顺序采购N批材料，所需费用依次为F1, F2, …, Fn，因施工关系，采购顺序不能改变，需要在连续的K个月内采购完成。财务希望支出尽可能平稳，即这K个月的采购支出的最大值最小，例如需要分2个月依次采购3批材料，所需费用依次是5、3、7。一种方案是先采购5，然后采购3和7，最大支出为10；另一方案是先采购5和3，再采购7，最大支出为8，比前一种采购方式平稳，采购支出的最大值最小是8。

输入说明：第一行是两个正整数，分别是采购批数N（0〈N〈10000）和采购月数K（0〈K〈=N〈10000）。第二行是N个正整数，对应N批材料的费用F1, F2, …, Fn。

输出说明：所有采购方案中，支出最大值最小的值。

输入样例：3 2

5 3 7

输出样例：8

代码提交说明：

1.请严格按照每道题目给出的输入/输出样例编写相关I/O代码，数字间的默认间隔是一个空格，浮点数的默认输出精度是保持小数点后2位。样例以外的提示信息请不要在屏幕上输出。

2.请大家确保提交的代码可以在指定的编译条件下正确地编译执行，否则自动评测程序将给出编译错误或运行时错误的信息。

3.每道编程题目，如果没有特殊说明，需要在1秒内完成程序的运行和输出结果，超过这个时间限制将会被判超时，失去相应测试用例的分数。每个可执行文件可使用的空间不得大于64MB。

4.每道编程题会有多个测试用例，每通过一些测试用例可以获得相应的分值，但只有通过全部测试用例才能拿到这题全部的分数。

#include<iostream>#include<vector>#include<algorithm>using namespace std;int main(){int a,b;cin>>a>>b;vector<int>v(a);vector<int>mou(b);for(int i=0;i<a;i++){cin>>v[i];}sort(v.begin(),v.end());for(int i=0;i<a;i++){sort(mou.begin(),mou.end());mou[0]+=v[a-i-1];}sort(mou.begin(),mou.end());cout<<mou[b-1];return 0;}