700字范文 > 计算机高校挑战赛英语全国高校计算机能力挑战赛

计算机高校挑战赛英语全国高校计算机能力挑战赛

时间：2022-09-11 14:43:38

初赛题解：/qq_41895747/article/details/103106367

决赛题解：/shiliang97/article/details/103332528

C++组决赛

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

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

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

输入样例：-09-05A

输出样例：5345-32-38A

简单的字符串处理

#include

using namespace std;

const int N = 1e4 + 5;

char s[260];

int main(void)

{

cin >> s;

int len = strlen(s);

int t;

for (int i = 0; i < len; i++){

if (s[i] >= '0' && s[i] <= '9'){

t = s[i] - '0';

t = (t + 3) % 10;

s[i] = t + '0';

}

cout << s << endl;

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

计算出体积后，排序输出

#include

using namespace std;

const int N = 1e4 + 5;

const double pi = 3.14;

double arr[N];

bool cmp(double a, double b)

{

return a > b;

}

int main(void)

{

int n;

char s[5];

double x, y;

scanf("%d", &n);

for (int i = 0; i < n; i++){

scanf("%s", s);

if (s[1] == 'T'){//RTri直角三角形

scanf("%lf%lf", &x, &y);

arr[i] = x * y / 2;

}

else if (s[1] == 'E'){//RECT矩形

scanf("%lf%lf", &x, &y);

arr[i] = x * y;

}

else{//CIRC圆形

scanf("%lf", &x);

arr[i] = x * x * pi;

}

sort(arr, arr + n, cmp);

for (int i = 0; i < n - 1; i++)

printf("%.2lf ", arr[i]);

printf("%.2lf\n", arr[n - 1]);

return 0;

}

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

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

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

输入样例：6

11 102 13 24 35 46

输出样例：1

先计算出前缀和，再枚举断点找到最小的情况即可

#include

using namespace std;

const int N = 1e4 + 5;

typedef long long ll;

ll arr[N], sum[N];

int main(void)

{

int n, pos = 0;

ll maxv = 0;

scanf("%d", &n);

for (int i = 0; i < n; i++){

scanf("%lld", &arr[i]);

if (i == 0){

sum[i] = arr[i];

}

else{

sum[i] = sum[i - 1] + arr[i];

}

for (int i = 0; i < n - 1; i++){

if (abs(sum[i] - (sum[n - 1] - sum[i])) > maxv){

maxv = abs(sum[i] - (sum[n - 1] - sum[i]));

pos = i + 1;

}

printf("%d\n", pos);

return 0;

}

4、这道题没有找到题目，只有代码还在

忘记了题目是什么了，大概是求第k大的数

#include

using namespace std;

const int N = 1e5 + 5;

int arr[N];

int main(void)

{

int n, k;

scanf("%d%d", &n, &k);

for (int i = 0; i < n; i++){

scanf("%d", &arr[i]);

}

sort(arr, arr + n);

printf("%d\n", arr[n - k]);

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

看到村庄数是1w之后本菜鸡蒙了，当时只开了1k的数组，并且没有考虑无法到达的情况

因为村庄数目是1w，不能用邻接矩阵来存储，需要使用邻接表来存储。

复杂度为 O ( n l o g n ) O(nlogn)O(nlogn)

#include

#define PUSH(x,y,z) G[x].push_back(P(y,z))// 宏函数

using namespace std;

const int INF = 0x3f3f3f3f, N = 10005;

typedef pair P;

int n, m, st, ed;

vector

G[N];

int dis[N];

bool vis[N];

void init()

{

for(int i = 0; i < N; i++)

G[i].clear();

memset(dis, INF, sizeof dis);

memset(vis, false, sizeof vis);

}

void Dijk()

{

dis[st] = 0;

priority_queue

, greater

> que;

que.push(P(0, st));

while(que.size()) {

P p = que.top(); que.pop();

int u = p.second;

if(vis[u])

continue;

vis[u] = true;

for(int i = 0; i < G[u].size(); ++i) {

int v = G[u][i].first;

int cost = G[u][i].second;

if(!vis[v] && dis[v] > dis[u] + cost) {

dis[v] = dis[u] + cost;

que.push(P(dis[v], v));

}

int main(void)

{

int a, b, c;

cin >> n >> st >> ed;

init();

while(cin >> a >> b >> c) {

if (a == -1)

break;

PUSH(a, b, c);

PUSH(b, a, c);

}

Dijk();

cout << (dis[ed] == INF ? -1 : dis[ed]) << endl;

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

二分问题，数列分段

题解链接：/weixin_43772166/article/details/105269478

#include

using namespace std;

const int N = 1e5 + 5;

typedef long long ll;

ll a[N];