2019中南大学研究生招生夏令营机试题
来源：传送门说明：代码不规范以及题解不清楚敬请谅解：）部分其他解法和详细题解后续补充。
1110: 地砖问题（搜索 / bfs）
- 时间限制: 1 Sec
- 内存限制: 128 MB
- 提交: 2
- 解决: 1
题目描述
小明站在一个矩形房间里，这个房间的地面铺满了地砖，每块地砖的颜色或是红色或是黑色。小明一开始站在一块黑色的地砖上，并且小明从一块地砖可以向上下左右四个方向移动到其他的地砖上，但是他不能移动到红色地砖上，只能移动到黑色地砖上。
请你编程计算小明可以走到的黑色地砖最多有多少块。
输入
输入包含多组测试数据。
每组输入首先是两个正整数W和H，分别表示地砖的列行数。（1<=W，H<=20）
接下来H行，每行包含W个字符，字符含义如下：
‘.’表示黑地砖；
‘#’表示红地砖；
‘@’表示小明一开始站的位置，此位置是一块黑地砖，并且这个字符在每组输入中仅会出现一个。
当W=0，H=0时，输入结束。
输出
对于每组输入，输出小明可以走到的黑色地砖最多有多少块，包括小明最开始站的那块黑色地砖。
样例输入
7 7
..#.#..
..#.#..
###.###
...@...
###.###
..#.#..
..#.#..
0 0样例输出
13来源/分类
题解
用BFS搜索一下统计一下就好了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 30;
char s[maxn][maxn];
bool vis[maxn][maxn];
int n, m;
struct Node
{
int x, y;
Node(int _x, int _y):x(_x), y(_y) {}
};
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
bool check(int x, int y)
{
if (x < 1 || x > n || y < 1 || y > m || s[x][y] == '#')
return false;
return true;
}
int main()
{
while (scanf("%d%d", &m, &n) && n && m)
{
int x, y, ans = 0;
memset(vis, 0, sizeof vis);
for (int i = 1; i <= n; ++i)
scanf("%s", s[i] + 1);
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
if (s[i][j] == '@')
{
x = i, y = j;
vis[x][y] = true;
break;
}
}
queue <Node> que;
que.push(Node(x, y));
while (!que.empty())
{
Node u = que.front();
que.pop();
ans++;
for (int i = 0; i < 4; ++i)
{
x = u.x + dir[i][0], y = u.y + dir[i][1];
if (!vis[x][y] && check(x, y))
{
que.push(Node(x, y));
vis[x][y] = true;
}
}
}
printf("%d\n", ans);
}
return 0;
}1111: 最小花费（图论 / 最短路）
- 时间限制: 1 Sec
- 内存限制: 128 MB
- 提交: 1
- 解决: 1
题目描述
在n个人中，某些人的银行账号之间可以互相转账。这些人之间转账的手续费各不相同。给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问A最少需要多少钱使得转账后B收到100元。
输入
第一行输入两个正整数n,m,分别表示总人数和可以互相转账的人的对数。（0<n<=2000）以下m行每行输入三个正整数x,y,z。表示标号为x的人和标号为y的人之间互相转账需要扣除z%的手续费（z<100）。
最后一行输入两个正整数A,B。数据保证A与B之间可以直接或间接地转账
输出
输出A使得B到账100元最少需要的总费用。精确到小数点后8位。
样例输入
3 3
1 2 1
2 3 2
1 3 3
1 3样例输出
103.07153164来源/分类
题解
题目要求总费用最少，所以我们要让手续费尽可能少，即转化率$1-z\%$尽可能高。可以以两人间的转化率$1-z\%$为权值连边建图，然后跑一个“最长路”，得到最高的转化率x，那么最后的答案就是100/x。
（点数只有2000就偷懒用邻接矩阵建图了Qrz）
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2010;
const int inf = -0x3f3f3f3f;
double G[maxn][maxn];
bool vis[maxn];
double dist[maxn];
int n, m;
void Dijkstra(int s)
{
for (int i = 1; i <= n; ++i)
{
dist[i] = inf * 1.0;
vis[i] = 0;
}
dist[s] = 1.0;
for (int i = 1; i <= n; ++i)
{
double Max = inf * 1.0;
int k = -1;
for (int j = 1; j <= n; ++j)
{
if (dist[j] > Max && !vis[j])
{
Max = dist[j];
k = j;
}
}
if (k == -1)
break;
vis[k] = true;
for (int j = 1; j <= n; ++j)
{
if (G[k][j] * Max > dist[j] && !vis[j])
dist[j] = Max * G[k][j];
}
}
}
int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
int u, v, w;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= n; ++j)
G[i][j] = ((i == j) ? 0.0 : inf * 1.0);
for (int i = 0; i < m; ++i)
{
scanf("%d%d%d", &u, &v, &w);
G[u][v] = G[v][u] = 1.0 - w * 1.0 / 100;
}
int s, t;
scanf("%d%d", &s, &t);
Dijkstra(s);
double ans = 100.0;
printf("%.8f", ans / dist[t]);
}
return 0;
}1112: 回文串（字符串 / 回文串）
- 时间限制: 1 Sec
- 内存限制: 128 MB
- 提交: 4
- 解决: 3
题目描述
现在给你一个字符串S，请你计算S中有多少连续子串是回文串。
输入
输入包含多组测试数据。每组输入是一个非空字符串，长度不超过5000.
输出
对于每组输入，输出回文子串的个数。
样例输入
aba样例输出
4来源/分类
题解
分别考虑偶数长度回文串和奇数长度回文串，即以单个字符为中心和以双字符为中心向周围扩散。这样做的时间复杂度为$O(n^2)$，当然还有更好的方法，待补充。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 5010;
char s[maxn];
int n, ans;
void expand(int i, int j)
{
while (i >= 0 && j < n && s[i] == s[j])
{
--i, ++j;
++ans;
}
}
int main()
{
while (~scanf("%s", s))
{
n = strlen(s);
ans = 0;
for (int i = 0; i < n; ++i)
{
expand(i, i); // 奇数回文串
expand(i, i + 1); // 偶数回文串
}
printf("%d\n", ans);
}
return 0;
}1113: 有序合并（模拟 / 排序）
- 时间限制: 1 Sec
- 内存限制: 128 MB
- 提交: 2
- 解决: 1
题目描述
已知线性表LA和LB中的数据元素按值非递减有序排列，现要求LA和LB归并为一个新的线性表LC，且LC中的数据元素仍然按值非递减有序排列。例如，设LA=（3,5,8,11），LB=（2,6,8,9,11,15,20）则LC=（2,3,6,6,8,8,9,11,11,15,20）。
输入
有多组测试数据，每组测试数据占两行。第一行是集合A，第一个整数m（0<=m<=100）代表集合A起始有m个元素，后面有m个非递减排序的整数，代表A中的元素。第二行是集合B，第一个整数n（0<=n<=100）代表集合B起始有n个元素，后面有n个非递减排序的整数，代表B中的元素。每行中整数之间用一个空格隔开。
输出
每组测试数据只要求输出一行，这一行含有m+n个来自集合A和集合B中的元素。结果依旧是非递减的。每个整数间用一个空格隔开。
样例输入
4 3 5 8 11
7 2 6 8 9 11 15 20样例输出
2 3 5 6 8 8 9 11 11 15 20来源/分类
题解
输入的时候就放到一个数组然后sort一下就好了。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 210;
int a[maxn];
int n, m;
int main()
{
while (~scanf("%d", &m))
{
for (int i = 0; i < m; ++i)
scanf("%d", &a[i]);
scanf("%d", &n);
for (int j = m; j < m + n; ++j)
scanf("%d", &a[j]);
sort(a, a + m + n);
printf("%d", a[0]);
for (int i = 1; i < m + n; ++i)
printf(" %d", a[i]);
printf("\n");
}
return 0;
}1114: 十六进制转换（思维 / 字符串）
- 时间限制: 1 Sec
- 内存限制: 128 MB
- 提交: 2
- 解决: 1
题目描述
输入一个不超过100000位的十六进制数，请转换成八进制数。
注：十六进制数中，字母0~9还对应表示数字0~9。字母”A”（大写）表示10，”B”表示11，”...”，”F”表示15，比如：十六进制数A10B表示的是10进制数是10×163+1×162+0×161+11×160=41227。转换成的八进制数是120413，因为1×85+2×84+0×83+4×82+1×81+3×80=41227。
输入
一个十六进制数，没有前导0（除非是数字0）。
输出
一个八进制数，没有前导0（除非是数字0）。
样例输入
123ABC样例输出
4435274来源/分类
题解
十六进制数超过100000位，所以没法直接转化为十进制再转为八进制，但是我们可以考虑十六进制和八进制与二进制之间的关系：十六进制等价于四位二进制，八进制等价于三位二进制，知道这个之后就很好办了，接下来的操作就是字符串的模拟，注意一些细节问题就好了。
代码
代码有点拖沓见谅：）
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
string sHex, sBin;
map <char, int> mp;
void init()
{
mp['0'] = 0;
mp['1'] = 1;
mp['2'] = 2;
mp['3'] = 3;
mp['4'] = 4;
mp['5'] = 5;
mp['6'] = 6;
mp['7'] = 7;
mp['8'] = 8;
mp['9'] = 9;
mp['A'] = 10;
mp['B'] = 11;
mp['C'] = 12;
mp['D'] = 13;
mp['E'] = 14;
mp['F'] = 15;
}
string toBinary(char ch)
{
string res = "0000";
int val = mp[ch];
int k = 3;
while (val)
{
res[k--] = (val % 2 + '0');
val /= 2;
}
return res;
}
string toOct(string s)
{
int n = s.length();
string res = "";
if (n % 3 != 0)
{
string tmp(3 - n % 3, '0');
s.insert(0, tmp);
n += 3 - n % 3;
}
int x = (s[0] - '0') * 4 + (s[1] - '0') * 2 + (s[2] - '0') * 1;
if (x != 0) // 可能存在前导0问题，特殊处理
res += (x + '0');
for (int i = 3; i < n; i += 3)
{
int x = (s[i] - '0') * 4 + (s[i+1] - '0') * 2 + (s[i+2] - '0') * 1;
res += (x + '0');
}
return res;
}
int main()
{
init();
cin >> sHex;
int n = sHex.length();
sBin = "";
for (int i = 0; i < n; ++i)
sBin += toBinary(sHex[i]);
cout << toOct(sBin) << endl;
return 0;
}- 2019年6月15日 星期六