一共15道不定项选择+5道编程+2道问答
不定项选择以及问答基本都是测试相关的内容，比较恶心的是选择是不定项选择，多选不得分，少选得一半分，下面主要说一下五道编程题：
1、小球下落问题
一个小球从初始高度为H的地方下落，每次落地后反跳回原高度的一半; 再落下, 求它在第n次落地时，共经历多少米?结果保留两位小数：(n不超过五次)
输入测试用例：1 5 2 (第一个数代表测试用例个数，第二个数代表小球下落的起始高度，最后一个数代表第n次落地)
输出：10.00
这道题是全AC的
#include <iostream>
#include <iomanip>
using namespace std;
int main()
{
int number;
cin>>number;
while (number--)
{
double height;
while (cin >> height){
double back = height;
double sum = 0.0;
int n;
cin >> n;
for (int i = 1; i <= n; i++){
sum += back + back / 2.0;
back /= 2.0;
}
cout << fixed << setprecision(2) << sum - back << endl;
}
}
return 0;
} 2、最小长方形问题
给定一系列2维平面点的坐标(x, y)，其中x和y均为整数，要求用一个最小的长方形框将所有点框在内。长方形框的边分别平行于x和y坐标轴，点落在边上也算是被框在内。
输入测试用例： 测试输入包含若干测试用例，每个测试用例由一系列坐标组成，每对坐标占一行，其中|x|和|y|小于 231；一对0 坐标标志着一个测试用例的结束。注意(0, 0)不作为任何一个测试用例里面的点。一个没有点的测试用例标志着整个输入的结束。
12 56
23 56
13 10
0 0
12 34
0 0
0 0
输出：对每个测试用例，在1行内输出2对整数，其间用一个空格隔开。第1对整数是长方形框左下角的坐标，第2对整数是长方形框右上角的坐标。
12 10 23 56
12 34 12 34
这道题是全AC的
#include <iostream>
using namespace std;
int main()
{
int x, y, max_x, min_x, max_y, min_y;
while (cin>>x>>y)
{
if (x == 0 && y == 0)
{
break;
}
max_x = min_x = x;
max_y = min_y = y;
while (cin>>x>>y)
{
if (x == 0 && y == 0)
{
break;
}
if (x > max_x)
{
max_x = x;
}
else if (x < min_x)
{
min_x = x;
}
if (y > max_y)
{
max_y = y;
}
else if (y < min_y)
{
min_y = y;
}
}
cout << min_x <<" "<< min_y <<" "<< max_x <<" "<< max_y << endl;
}
return 0;
} 3、N人围圈报数问题
有n个人围成一圈，按顺序从1到n编号。从第一个人开始报数，报数3的人退出圈子，下一个人从1开始重新报数，报数3的人退出圈子。如此循环，直到留下最后一个人。依次输出退出人的编号：
输入测试用例：1 4 (第一个数代表测试用例个数，第二个数代表编号n)
输出：3 2 4 1
这道题博主没有全AC，通过了40%，提示算法复杂度过大，以下是博主40%的解法：
#include <iostream>
using namespace std;
int main()
{
int number;
cin >> number;
while (number--)
{
int i, j = 0, k = 0, n;
int a[50] = { 0 };
cin >>n;
for (i = 0; i < n; i++)
{
a[i] = 1;
}
for (i = 1; i < 4; i = i % 3 + 1)
{
if (3 == i && a[j] != 0)
{
a[j] = 0;
cout << j + 1 << " ";
k++;
if (n - 1 == k)
break;
j = (j + 1) % n;
continue;
}
if (0 == a[j])
{
j = (j + 1) % n;
i--;
continue;
}
j = (j + 1) % n;
}
for (i = 0; i < n; i++)
{
if (1 == a[i])
cout << i + 1 << endl;
}
}
return 0;
} 4、死亡骑士问题
不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.
死亡骑士:"我要买道具!"
地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."
死亡骑士:"好的,给我一个血瓶."
说完他掏出那张N元的大钞递给地精商人.
地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."
死亡骑士:"......"
死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.
现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.
不死族的巫妖王发工资拉,死亡骑士拿到一张N元的钞票(记住,只有一张钞票),为了防止自己在战斗中频繁的死掉,他决定给自己买一些道具,于是他来到了地精商店前.
死亡骑士:"我要买道具!"
地精商人:"我们这里有三种道具,血瓶150块一个,魔法药200块一个,无敌药水350块一个."
死亡骑士:"好的,给我一个血瓶."
说完他掏出那张N元的大钞递给地精商人.
地精商人:"我忘了提醒你了,我们这里没有找客人钱的习惯的,多的钱我们都当小费收了的,嘿嘿."
死亡骑士:"......"
死亡骑士想,与其把钱当小费送个他还不如自己多买一点道具,反正以后都要买的,早点买了放在家里也好,但是要尽量少让他赚小费.
现在死亡骑士希望你能帮他计算一下,最少他要给地精商人多少小费.
输入测试用例：
输入数据的第一行是一个整数T(1<=T<=100),代表测试数据的数量.然后是T行测试数据,每个测试数据只包含一个正整数N(1<=N<=10000),N代表死亡骑士手中钞票的面值.
注意:地精商店只有题中描述的三种道具.
2
900
250
输出：对于每组测试数据,请你输出死亡骑士最少要浪费多少钱给地精商人作为小费.
0
50
这道题是全AC的
#include<iostream>
using namespace std;
int main()
{
int T;
cin>>T;
while(T--)
{
int N,sum=0;
cin>>N;
if(N<150)
sum=N;
if(N>=150&&N<200)
sum=N-150;
if(N>=200&&N<300)
sum=N-200;
if(N>=300)
sum=N%50;
cout<<sum<<endl;
}
return 0;
} 5、连连看问题
“连连看”相信很多人都玩过。没玩过也没关系，下面我给大家介绍一下游戏规则：在一个棋盘中，放了很多的棋子。如果某两个相同的棋子，可以通过一条线连起来（这条线不能经过其它棋子），而且线的转折次数不超过两次，那么这两个棋子就可以在棋盘上消去。不好意思，由于我以前没有玩过连连看，咨询了同学的意见，连线不能从外面绕过去的，但事实上这是错的。现在已经酿成大祸，就只能将错就错了，连线不能从外围绕过。玩家鼠标先后点击两块棋子，试图将他们消去，然后游戏的后台判断这两个方格能不能消去。现在你的任务就是写这个后台程序。
输入测试用例：输入数据有多组。每组数据的第一行有两个正整数n,m(0<n<=1000,0<m<1000)，分别表示棋盘的行数与列数。在接下来的n行中，每行有m个非负整数描述棋盘的方格分布。0表示这个位置没有棋子，正整数表示棋子的类型。接下来的一行是一个正整数q(0<q<50)，表示下面有q次询问。在接下来的q行里，每行有四个正整数x1,y1,x2,y2,表示询问第x1行y1列的棋子与第x2行y2列的棋子能不能消去。n=0,m=0时，输入结束。注意：询问之间无先后关系，都是针对当前状态的！
3 4
1 2 3 4
0 0 0 0
4 3 2 1
4
1 1 3 4
1 1 2 4
1 1 3 3
2 1 2 4
3 4
0 1 4 3
0 2 4 1
0 0 0 0
2
1 1 2 4
1 3 2 3
0 0
输出：每一组输入数据对应一行输出。如果能消去则输出"YES",不能则输出"NO"。
YES
NO
NO
NO
NO
YES
这道题博主没做完，无法验证是否能顺利AC，这里贴一段网上找到的相对靠谱的解法
#include <stdio.h>
#include <string.h>
int map[1005][1005], vis[1005][1005];
int dis[4][2] = { -1, 0, 0, 1, 1, 0, 0, -1 };
int n, m, f_x, f_y;
bool ispos;
// dfs开始
void dfs(int x, int y, int direct, int turn)
{
// 如果转向大于2 或者 已经找到了 则直接返回
if (turn>2 || ispos == 1) return;
// 如果到了目标，直接判定可以连接，因为之前转向大于2的都返回了
if (x == f_x && y == f_y)
{
ispos = true;
return;
}
// 强大的剪枝啊=。=
if (turn == 2)
{
if (x != f_x && y != f_y) return;
else if (x == f_x)
if (direct != 1) return;
else if (y == f_y)
if (direct != 0) return;
}
int i, xx, yy;
// 四个方向的遍历
for (i = 0; i<4; ++i)
{
xx = x + dis[i][0];
yy = y + dis[i][1];
// 边界判定
if (xx<1 || yy<1 || xx>n || yy>m || vis[xx][yy] == 1) continue;
// 如果下一个点是0或者终点
if (map[xx][yy] == 0 || (xx == f_x && yy == f_y))
{
vis[xx][yy] = 1;
//根据原来的方向来确定是否转向
if (direct == -1) dfs(xx, yy, i % 2, turn);
else if (direct == 0)
{
if (i % 2 == 1) dfs(xx, yy, 1, turn + 1);
else dfs(xx, yy, 0, turn);
}
else if (direct == 1)
{
if (i % 2 == 0) dfs(xx, yy, 0, turn + 1);
else dfs(xx, yy, 1, turn);
}
vis[xx][yy] = 0;
}
}
}
int main()
{
int i, j, q, s_x, s_y;
while (scanf("%d%d", &n, &m) != EOF)
{
if (n == 0 && m == 0) break;
// 输入
for (i = 1; i <= n; ++i)
for (j = 1; j <= m; ++j)
scanf("%d", &map[i][j]);
scanf("%d", &q);
while (q--)
{
scanf("%d%d%d%d", &s_x, &s_y, &f_x, &f_y);
// 如果搜寻的两个点不相等或者搜寻的点是空点(即搜寻的点有0)
if (map[s_x][s_y] != map[f_x][f_y] || map[s_x][s_y] == 0)
{
printf("NO\n");
continue;
}
// 如果搜寻两个点都为本身（去掉后增加了点时间）
if (s_x == f_x && s_y == f_y && map[s_x][s_y] != 0)
{
printf("NO\n");
continue;
}
// 初始化
memset(vis, 0, sizeof(vis));
ispos = false;
dfs(s_x, s_y, -1, 0);
// 判断输出
if (ispos) printf("YES\n");
else printf("NO\n");
}
}
return 0;
}
京公网安备 11010502036488号