第一题【深基7.例4】歌唱比赛
题目描述
n
(
n
≤
100
)
n(n\le 100)
n(n≤100) 名同学参加歌唱比赛，并接受
m
(
m
≤
20
)
m(m\le 20)
m(m≤20) 名评委的评分，评分范围是
0
0
0 到
10
10
10 分。这名同学的得分就是这些评委给分中去掉一个最高分，去掉一个最低分，剩下
m
?
2
m-2
m?2 个评分的平均数。请问得分最高的同学分数是多少？评分保留
2
2
2 位小数。
输入格式
第一行两个整数
n
,
m
n,m
n,m。
接下来
n
n
n 行，每行各
m
m
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
6.00
解题思路
- 1）记录单个人的成绩，进行排序和求和。
- 2）减去最大值和最小值，计算平均分。
- 3）和最大成绩比较，得到答案。
参考代码
#include<bits/stdc++.h>
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;
}
第二题 求细胞数量
题目描述
一矩形阵列由数字
0
0
0 到
9
9
9 组成，数字
1
1
1 到
9
9
9 代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
输入格式
第一行两个整数代表矩阵大小
n
n
n 和
m
m
m。
接下来
n
n
n 行，每行一个长度为
m
m
m 的只含字符 0 到 9 的字符串，代表这个
n
×
m
n \times m
n×m 的矩阵。
输出格式
一行一个整数代表细胞个数。
样例 #1
样例输入 #1
4 10
0234500067
1034560500
2045600671
0000000089
样例输出 #1
4
提示
数据规模与约定
对于
100
%
100\%
100% 的数据，保证
1
≤
n
,
m
≤
100
1 \le n,m \le 100
1≤n,m≤100。
解题思路
- 1）题目相当于求连通块的个数。
- 2）当遍历到非 0 元素时，进行深度优先搜索，将这个元素周围的非零元素全变成 0。连通块次数加一。
- 3）遍历到全是非 0 元素时，输出答案。
参考代码
#include<bits/stdc++.h>
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;
}
第三题 小A点菜
题目背景
uim 神犇拿到了 uoi 的 ra（镭牌）后，立刻拉着基友小 A 到了一家……餐馆，很低端的那种。
uim 指着墙上的价目表（太低级了没有菜单），说：“随便点”。
题目描述
不过 uim 由于买了一些书，口袋里只剩
M
M
M 元
(
M
≤
10000
)
(M \le 10000)
(M≤10000)。
餐馆虽低端，但是菜品种类不少，有
N
N
N 种
(
N
≤
100
)
(N \le 100)
(N≤100)，第
i
i
i 种卖
a
i
a_i
ai? 元
(
a
i
≤
1000
)
(a_i \le 1000)
(ai?≤1000)。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待
1
1
1 秒。
输入格式
第一行是两个数字，表示
N
N
N 和
M
M
M。
第二行起
N
N
N 个正数
a
i
a_i
ai?（可以有相同的数字，每个数字均在
1000
1000
1000 以内）。
输出格式
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
样例 #1
样例输入 #1
4 4
1 1 2 2
样例输出 #1
3
解题思路
参考代码
#include<bits/stdc++.h>
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;
}
第四题 好奇怪的游戏
题目背景
《爱与愁的故事第三弹·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
8
9
提示
100%数据：x1,y1,x2,y2<=20
解题思路
- 1）题目问的是最少步数，这里就能看出应该用广度优先搜索。
- 2）用结构体存储位置和步数，使用STL模板库中的
<queue>。将起点入队。 - 3）循环取队头元素，队头位置能到达的点都依次入队并标记为以访问。
- 4）到达
(1，1)退出循环，将标记访问的数组归零，广度优先搜索下一起点。
参考代码
#include<bits/stdc++.h>
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;
}
|