MENU

2019中南大学研究生招生夏令营机试题

2019 年 06 月 15 日 • 阅读: 1814 • 练习阅读设置

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

来源/分类

2019中南大学研究生招生夏令营机试题


题解

用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

来源/分类

2019中南大学研究生招生夏令营机试题


题解

题目要求总费用最少,所以我们要让手续费尽可能少,即转化率$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

来源/分类

2019中南大学研究生招生夏令营机试题


题解

分别考虑偶数长度回文串和奇数长度回文串,即以单个字符为中心和以双字符为中心向周围扩散。这样做的时间复杂度为$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

来源/分类

2019中南大学研究生招生夏令营机试题


题解

输入的时候就放到一个数组然后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

来源/分类

2019中南大学研究生招生夏令营机试题


题解

十六进制数超过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日 星期六
最后编辑于: 2020 年 04 月 24 日