第一题【深基7.例4】歌唱比赛

题目描述

$n(n\le 100)$ 名同学参加歌唱比赛，并接受 $m(m\le 20)$ 名评委的评分，评分范围是 $0$ 到 $10$ 分。这名同学的得分就是这些评委给分中去掉一个最高分，去掉一个最低分，剩下 $m-2$ 个评分的平均数。请问得分最高的同学分数是多少？评分保留 $2$ 位小数。

输入格式

第一行两个整数 $n,m$。
接下来 $n$ 行，每行各 $m$ 个整数，表示得分。

输出格式

输出分数最高的同学的分数，保留两位小数。

样例 #1

样例输入 #1

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

样例输出 #1

6.00
1

解题思路

• 1）记录单个人的成绩，进行排序和求和。
• 2）减去最大值和最小值，计算平均分。
• 3）和最大成绩比较，得到答案。

参考代码

#include
using namespace std;
int main()
{
    int n,m;
    double MAX=INT_MIN;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        double tmp[10001],sum=0;
        for(int j=1;j<=m;j++)
        {
            cin>>tmp[j];    
            sum+=tmp[j];
        }
        sort(tmp+1,tmp+m+1);
        sum=sum-tmp[1]-tmp[m];
        sum/=(m-2);
        if(sum>MAX) MAX=sum;
    }    
    printf("%.2f",MAX);
    return 0;   
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

第二题 求细胞数量

题目描述

一矩形阵列由数字 $0$ 到 $9$ 组成，数字 $1$ 到 $9$ 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。

输入格式

第一行两个整数代表矩阵大小 $n$ 和 $m$。

接下来 $n$ 行，每行一个长度为 $m$ 的只含字符 0 到 9 的字符串，代表这个 $n\times m$ 的矩阵。

输出格式

一行一个整数代表细胞个数。

样例 #1

样例输入 #1

4 10
0234500067
1034560500
2045600671
0000000089
1
2
3
4
5

样例输出 #1

4
1

提示

数据规模与约定

对于 $100\%$ 的数据，保证 $1\le n,m\le 100$。

解题思路

• 1）题目相当于求连通块的个数。
• 2）当遍历到非 0 元素时，进行深度优先搜索，将这个元素周围的非零元素全变成 0。连通块次数加一。
• 3）遍历到全是非 0 元素时，输出答案。

参考代码

#include
using namespace std;
int n,m;
char a[105][105];

int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};

int ans=0;

void dfs(int x,int y)
{
	if(a[x][y]=='0')return;
	a[x][y]='0';
	for(int i=0;i<4;i++)
	{
		int nx=x+dx[i];
		int ny=y+dy[i];
		if(nx<1||nx>n||ny<1||ny>m)
		{
			continue;
		}
		else
		{
			dfs(nx,ny);
		}
	}
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>a[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(a[i][j]!='0')
			{
				ans++;
				dfs(i,j);
			}
		}
	}
	cout<<ans;
	return 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
52
53

第三题 小A点菜

题目背景

uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。

uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。

题目描述

不过 uim 由于买了一些书，口袋里只剩 $M$ 元 $(M\le 10000)$。

餐馆虽低端，但是菜品种类不少，有 $N$ 种 $(N\le 100)$，第 $i$ 种卖 $a_i$ 元 $(a_i\le 1000)$。由于是很低端的餐馆，所以每种菜只有一份。

小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。

由于小 A 肚子太饿，所以最多只能等待 $1$ 秒。

输入格式

第一行是两个数字，表示 $N$ 和 $M$。

第二行起 $N$ 个正数 $a_i$（可以有相同的数字，每个数字均在 $1000$ 以内）。

输出格式

一个正整数，表示点菜方案数，保证答案的范围在 int 之内。

样例 #1

样例输入 #1

4 4
1 1 2 2
1
2

样例输出 #1

3
1

解题思路

• 1）简单的01背包问题。

参考代码

#include
using namespace std;
int dp[10500];
int main()
{
	int N,M;
	cin>>N>>M;
	dp[0]=1;
	for(int i=1;i<=N;i++)
	{
		int a;
		cin>>a;
		for(int j=M;j>=a;j--)
		{
			dp[j]=dp[j]+dp[j-a];
		}
	}
	cout<<dp[M];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

第四题 好奇怪的游戏

题目背景

《爱与愁的故事第三弹·shopping》娱乐章。

调调口味来道水题。

题目描述

爱与愁大神坐在公交车上无聊，于是玩起了手机。一款奇怪的游戏进入了爱与愁大神的眼帘：***（游戏名被打上了马赛克）。这个游戏类似象棋，但是只有黑白马各一匹，在点x1,y1和x2,y2上。它们得从点x1,y1和x2,y2走到1,1。这个游戏与普通象棋不同的地方是：马可以走“日”，也可以像象走“田”。现在爱与愁大神想知道两匹马到1,1的最少步数，你能帮他解决这个问题么？

输入格式

第1行：两个整数x1，y1

第2行：两个整数x2，y2

输出格式

第1行：黑马到1,1的步数

第2行：白马到1,1的步数

样例 #1

样例输入 #1

12 16
18 10
1
2

样例输出 #1

8 
9
1
2

提示

100%数据：x1,y1,x2,y2<=20

解题思路

• 1）题目问的是最少步数，这里就能看出应该用广度优先搜索。
• 2）用结构体存储位置和步数，使用STL模板库中的。将起点入队。
• 3）循环取队头元素，队头位置能到达的点都依次入队并标记为以访问。
• 4）到达(1，1)退出循环，将标记访问的数组归零，广度优先搜索下一起点。

参考代码

#include
using namespace std;

int x1,x2,yy1,yy2;
struct node{
	int x,y;
	int step;
}now,top;
int dx[12]={2,2,-2,-2,-1,-1,1,1,-2,-2,2,2};
int dy[12]={2,-2,2,-2,-2,2,-2,2,1,-1,1,-1};
int b[1000][1000];
queue<node> Q;

void bfs(int x,int y,int step)
{
	now.x=x;
	now.y=y;
	now.step=step;
	Q.push(now);
	while(!Q.empty()){
		top=Q.front();
		Q.pop();
		for(int i=0;i<12;i++)
		{
			int nx=top.x+dx[i];
			int ny=top.y+dy[i];
			if(nx>=1&&ny>=1&&nx<=50&&ny<=50&&b[nx][ny]==0)
			{
				now.x=nx;
				now.y=ny;
				now.step=top.step+1;
				Q.push(now);
				b[nx][ny]=1;
				if(nx==1&&ny==1)
				{
					cout<<now.step<<endl;
					return;
				}
				
			}
		}
	}
}

int main()
{
	cin>>x1>>yy1>>x2>>yy2;
	bfs(x1,yy1,0);
	memset(b,0,sizeof(b));
	while(!Q.empty())Q.pop();
	bfs(x2,yy2,0);
	return 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
52
53