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

发表于 | 分类于 ， | 热度 ℃
字数统计: 3,585 | 阅读时长 ≈ 16

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;
}
文章结束了，但我们的故事还在继续
坚持原创技术分享，您的支持将鼓励我继续创作！