陕西师范大学第七届程序设计竞赛题解

WWX的520

题目描述

520,因为谐音为我爱你,所以也被称之为表白日。

这一天,人们借机把藏在心底的洪荒之力通过表白、撒娇、传情、送礼、结婚等形式释放出来,商家也会趁势开展各类优惠促销活动,掀起一波或浪漫或虐狗的节日热浪。

这一天,也是送男朋友礼物、送女朋友礼物、送自己礼物、送亲朋好友礼物的好时机。

在520即将到来之际,wwx准备为她的女朋友购买一批礼物。于是他列出了一份礼物清单,但由于预算有限,必须删掉一种礼物。经过深思熟虑,他决定删掉价格第k高的礼物,你能帮帮他,找出是哪一种礼物吗?

输入描述:

1
2
3
4
第一行是一个整数T(1<=T<=80),表示有T组数据.
对于每一组数据,首先一行输入N(3<=N<=1000),接下来的N行每行输入一个字符串和一个整数,以空格间隔,分别作为每种礼物的名字和价格。
接下来一行输入k,表示要删去第k(1<=<=N)高的礼物
礼物的名字的长度不超过30,礼物的价格不超过1000,且均为整数。

输出描述:

1
2
对于每组输入数据,依次输出它的组号和要删去的礼物的名字和价格,以空格间隔。
若两种商品的价格相同,则比较礼物名字的字典序大小。即:两种礼物的价格相同时,字典序大者若为第k高,字典序小者则为第k+1高。

示例1

输入

1
2
3
4
5
6
7
8
9
10
11
12
2
3
Apple 18
Book 30
Milk 8000
3
4
Apple 300
Bananas 200
Bracelet 200
Candy 200
3

输出

1
2
#1: Apple 18
#2: Bracelet 200

备注:

1
2
3
4
5
1.
可用strcmp(s1,s2)函数进行字符串的比较。
2.
对于样例一中第二组数据:Apple 300是价格第一大,Candy 200是价格第二高,Bracelet
200是价格第三大。

题解

直接按照价格从大到小排序,如果价格相同按照字母序从大到小排序。排完序之后直接输出第k位的礼物名称与价格即可。

代码

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
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
struct node {
string str;
int v;
}a[1005];
int cmp(node a, node b) {
if (a.v == b.v) {
return a.str>b.str;
}
return a.v>b.v;
}
int main() {
int t;
cin >> t;

for (int z = 1; z <= t; z++) {
int n, k;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i].str;
cin >> a[i].v;
}
sort(a, a + n, cmp);
cin >> k;
cout << "#" << z << ": " << a[k - 1].str << " " << a[k - 1].v << endl;
}
return 0;
}

配环境

题目描述

​ 黑猫在给校赛配环境,结果被服务器的各种入站规则出站规则搞得头疼,想到自己要上传GVIM、EMACS、VSCODE、Jetbrain全家桶、Visual Studio、Gedit、Microsoft Office Word、Eclipse等等,完全不知道要要花费多少时间才能上传完校赛需要的环境。

​ 黑猫跑去问ddjing,谁知道ddjing说:“我要去实习了,没功夫解决这个问题,你去问问其他人吧。“

​ 于是黑猫想请你帮他解决这个问题。

​ 服务器总传输速度为每秒M个单位(本题出现的所有单位都统一),黑猫现在需要上传总共n个软件(按优先级顺序从高到低给出),每个软件的大小分别为v1、v2….vn,每个软件为保持稳定连接,上传需要一个最小的传输速度为m1、m2…mn。

​ 服务器带宽分配的策略是:按优先级满足每一个软件要求的传输速度。如果服务器剩余的带宽不能满足某个软件最小传输速度的话,服务器将继续寻找下去,直到找到能满足最小传输速度的软件。

​ 如果目前服务器的总传输速度不能满足所有还需要上传的软件的话,服务器将把传输速度全部给予当前优先级最高的(即使不能满足其最小传输速度)。

​ 如果目前对所有软件都满足了其最小传输速度的话,服务器将把剩余所有传输速度全部给予当前优先级最高的软件。

输入描述:

1
2
3
4
5
第一行给出一个正整数,表示服务器总带宽M
第二行给出整数n,表示需要上传的n个软件。
第三行为n个正整数,第i个数表示vi。
第四行为n个正整数,第i个数表示mi。
( 1 <= M <= 1000, 1 <= n <= 100 , 1 <= vi <= 1000 , 1 <= mi <= 1000 )

输出描述:

1
输出一行,为上传完毕所有软件所需要的时间,保留两位小数。

示例1

输入

1
2
3
4
10
6
1 1 4 5 1 4
10 9 8 7 6 5

输出

1
1.60

示例2

输入

1
2
3
4
10
6
10 9 8 7 6 5
1 1 4 5 1 4

输出

1
4.50

题解

原本是一道水题,结果成功被题面绕进去了。其实只需要把所有软件的大小V加起来除以宽带大小M即可。所谓最小速度都是迷惑人的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include<stdio.h>
int main() {
int M, n;
scanf("%d%d", &M, &n);
double tmp, ans = 0;
for (int i = 0; i < n;i++) {
scanf("%lf", &tmp);
ans += tmp;
}
for (int i = 0; i < n; i++) {
scanf("%lf", &tmp);
}
ans /= M;
printf("%.2lf\n", ans);
return 0;
}

下面是一段超时代码,成功将题面的过程给模拟了出来,当时没仔细看数据是怎么得到的,一直超时很不可思议。因此总结出了经验,以后做题一定得分析出数据是怎么得到的,有时候就很容易找到规律或者发现玄机。另外下面的代码总结出了一个新的方法,就是利用滚动数组实现删除元素,虽然vector有删除功能,但删除效率低。以下的方法是利用滚动数组,将未删除的元素重新压入数组,删除的元素不进行操作,然后清空数组,这样循环操作。

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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<vector>
using namespace std;
#define inf 0x3f3f3f3f
int M, n;
struct node{
double v;
int m;
}a[1005];
int vis[1005];
vector<int>vv[2];
int main() {
cin >> M >> n;
double ans = 0, wei;
int ff[2] = { 0,1 };
for (int i = 0; i < n; i++)
cin >> a[i].v;
for (int i = 0; i < n; i++) {
cin >> a[i].m;
vv[ff[0]].push_back(i);
}
int flag = 1;
while (flag >= 0) {
flag = -1;
wei = M;
double mint = inf;
vv[ff[1]].clear();
vector<int>::iterator it;
for (it = vv[ff[0]].begin(); it != vv[ff[0]].end(); it++) {
if (a[*it].v <= 0) {
continue;
} vis[*it] = 0;
vv[ff[1]].push_back(*it);
if (flag < 0)
flag = *it;
if (a[*it].v <= wei) {
vis[*it] = 1;
wei -= a[*it].m;
if (*it != flag)
mint = min(mint, a[*it].v / a[*it].m);
}
}
if (flag < 0)
break;
mint = min(mint, a[flag].v / (vis[flag] ? a[flag].m + wei : wei));
for (it = vv[ff[1]].begin(); it != vv[ff[1]].end(); it++) {
if (a[*it].v <= 0 || !vis[*it] || flag == *it)
continue;
a[*it].v -= a[*it].m*mint;
}
a[flag].v -= (vis[flag] ? a[flag].m + wei : wei)*mint;
ans += mint;
ff[0] = ff[0] ^ ff[1];
ff[1] = ff[0] ^ ff[1];
ff[0] = ff[0] ^ ff[1];
//cout << flag << " " << mint << endl;
}
printf("%.2lf\n", ans);
return 0;
}

iko和她的糖

题目描述

​ iko超级超级喜欢吃糖,有一天iko想出去玩,她计划从1点走到N点(按1,2,3,…,n的顺序走),每个点都有一个补给站,第i点的补给站有a[i]颗糖,从i点走到i+1点会消耗掉b[i]颗糖,iko在出游的途中可以选择三个补给站,iko想知道她走完全程到达N点时口袋里最多还能剩下几颗糖(初始时iko的口袋里一颗糖都没有)。

输入描述:

1
2
3
第一行输入N(3<=N<=1000)
第二行输入N个数代表a[1].......a[N] (0<=a[i]<=1000 )
第三行输入N-1个数代表b[1]......b[N-1] ( 1<=b[i]<=1000 )

输出描述:

1
2
输出一个数字表示iko到达n点时口袋里最多剩下的糖,
若不能到达N点输出-1。

示例1

输入

1
2
3
3
1 3 4
3 4

输出

1
-1

示例2

输入

1
2
3
5
3 4 5 2 4
3 2 2 2

输出

1
3

题解

首先,3个补给站必须得选择第1个,因为一开始没有糖,而每条路都需要消耗糖,所以必须拿起点的糖。之后就很好理解了,每走一条路记录当前走过的补给站最大的两个,如果哪一条路糖果不够了,就把最大的补给站加上,如果还不够就把次大的也加上。每次记录走到这条路经过的最大补给站记录下来,然后现有糖果减去消耗的糖果,如果为负就把之前的最大补给站的糖果加上。例如第2组数据,初始是3,走到第1条路剩余糖果为0,此时记录的最大补给站是4,然后走到下一条路糖果变成了-2,那就把最大补给站的加上,现在剩余糖果是2。此时最大补给站记录5,再往下走是2,剩余糖果是0,继续走,消耗2个为-2,则加上最大补给站的糖5。最终就是3。

代码

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
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 1005;
int N, cur, MAX1, MAX2, flag, a[maxn];
void check(int &cnt) {
while (cnt&&cur < 0) {
cur += MAX1;
MAX1 = MAX2;
cnt--;
}
}
void fun(int i) {
if (MAX1 <= a[i]) {
MAX2 = MAX1;
MAX1 = a[i];
}
else if (MAX2 < a[i]) {
MAX2 = a[i];
}
}
int main() {
while (cin >> N) {
memset(a, 0, sizeof(a));
MAX1 = -1, MAX2 = -1, flag = 0;
int tmp, cnt = 3;
cur = 0;
for (int i = 0; i < N; i++)
cin >> a[i];
for (int i = 0; i < N - 1; i++) {
fun(i);
cin >> tmp;
cur -= tmp;
if (cur < 0) {
check(cnt);
}
if (cur < 0)
flag = 1;
}
fun(N - 1);
if (flag)
printf("-1\n");
else {
if (cnt == 2)
cur += MAX1 + MAX2;
else if (cnt == 1)
cur += MAX1;
printf("%d\n", cur);
}
}
return 0;
}

ZQ的睡前故事

题目描述

​ ZQ是一个拥有n女朋友的万人迷,她的每一个女朋友每天晚上都会挨个给他打电话,要他讲了睡前故事才能睡觉。可是,每次他的女朋友都会挑他在吃鸡的时候打电话,ZQ总是因为挂机被舍友赶出宿舍,于是,ZQ告诉他的女朋友们,别打电话了,他会主动打过去给他们讲故事,再打电话就分手!

​ 于是,ZQ把他的女朋友名字写在纸上,画成一圈,顺时针编号为1~n,然后从1开始顺时针数。在每一次数数中,ZQ数k个就停下来,然后给选中的女朋友打电话讲故事。

输入描述:

1
先输入一个t,然后t组数据,每行包含两个数字n,k,n<20,k>0

输出描述:

1
按顺序输出每轮被选中的女朋友的编号。

示例1

输入

1
2
3
4
3
10 3
5 2
11 4

输出

1
2
3
3 6 9 2 7 1 8 5 10 4
2 4 1 5 3
4 8 1 6 11 7 3 2 5 10 9

题解

约瑟夫环。由于数据比较水,所以多种方法求解,这里不介绍了。

代码

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
#include<stdio.h>
int main() {
int n, k, t;
scanf("%d", &t);
while (t--) {
scanf("%d%d", &n, &k);
int i = 0;
int cnt = n;
int vis[20] = { 0 };
while (cnt) {
int kk = k;
while (vis[i%n])
i++;
for (int j = 1; j < kk; j++) {
i++;
while (vis[i%n])
i++;
}
vis[i%n] = 1;
cnt--;
cnt ? printf("%d ", i%n + 1) : printf("%d\n", i%n + 1);
}
}
return 0;
}

附加:hdu5135 Little Zu Chongzhi’s Triangles

题意:

有n条边组三角形,每个三角形必须由3条边组成,三角形边不可以重复利用,不可以共线,只能是分开的三角形。问这n条边组成的所有三角形的面积和最大为多少。

题解

原本状压dp求解,但数据比较水,因此递归还没有记忆化搜索直接就过了。每次从n条边里面选择3条边组成三角形,方程maxx[i],[j] = max(maxx[i-1],[j],[1~n] );由于状态是集合,因此需要状压以下。这里主要说的是一个常犯的错误。我没找到vis是当前状态是否已经选过,尤其是搜索时vis的作用非常重要。但本题用深搜时犯了一个错误,就是在vis=1,与vis=0之间多了一个continue,即vis=1,continue,dfs,vis=0,导致状态更改,数据一直错误。正确顺序应该是continue,vis=1,dfs,vis=0。因此之后比赛时一定要注意此细节。在vis=1与vis=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
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
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n;
int vis[15];
double a[15];
double dfs(int x) {
double ans = 0, maxx = 0;
for (int i = x; i<n; i++) {
if (vis[i])
continue;
vis[i] = 1;
for (int j = i + 1; j< n; j++) {
if (vis[j])
continue;
vis[j] = 1;
for (int k = j + 1; k<n; k++) {
if (vis[k])
continue;
if (a[k] >= a[i] + a[j] || a[j] >= a[i] + a[k] || a[i] >= a[j] + a[k])
continue;
vis[k] = 1;
double c = (a[i] + a[k] + a[j]) / 2.0;
ans = sqrt(c*(c - a[i])*(c - a[j])*(c - a[k]));
ans += dfs(i + 1);
maxx = max(maxx, ans);

vis[k] = 0;
}
vis[j] = 0;
}
vis[i] = 0;
}
return maxx;
}
int main() {
while (cin >> n) {
if (!n)
break;
memset(a, 0, sizeof(a));
for (int i = 0; i<n; i++) {
cin >> a[i];
}
memset(vis, 0, sizeof(vis));
double ans = dfs(0);
printf("%.2lf\n", ans);
}
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!