第一题【深基7.例4】歌唱比赛
题目描述
n ( n ≤ 100 )名同学参加歌唱比赛，并接受 m ( m ≤ 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
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到 9组成，数字 1 到 9代表细胞，细胞的定义为沿细胞数字上下左右若还是细胞数字则为同一细胞，求给定矩形阵列的细胞个数。
输入格式
第一行两个整数代表矩阵大小 n和 m。
接下来 n 行，每行一个长度为 m的只含字符 0 到 9 的字符串，代表这个 n × m 的矩阵。
输出格式
一行一个整数代表细胞个数。
样例 #1
样例输入 #1
4 10 0234500067 1034560500 2045600671 0000000089
样例输出 #1
4
提示
数据规模与约定
对于 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 ≤ 10000 ) 。
餐馆虽低端，但是菜品种类不少，有 N种 ( N ≤ 100 )，第 i 种卖 a i 元 ( a i ≤ 1000 )。由于是很低端的餐馆，所以每种菜只有一份。
小 A 奉行“不把钱吃光不罢休”，所以他点单一定刚好把 uim 身上所有钱花完。他想知道有多少种点菜方法。
由于小 A 肚子太饿，所以最多只能等待 1 秒。
输入格式
第一行是两个数字，表示 N 和 M。
第二行起 N 个正数 a i（可以有相同的数字，每个数字均在 1000 以内）。
输出格式
一个正整数，表示点菜方案数，保证答案的范围在 int 之内。
样例 #1
样例输入 #1
4 4 1 1 2 2
样例输出 #1
3
解题思路
1）简单的01背包问题。
参考代码
#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; }
