近日一些简单题解

作者: KalarMorghulis | 来源:发表于2021-06-09 00:13 被阅读0次

最近在实验室老师那儿实习，第一个任务是完成几道算法题。拿到题目的时候，简单看了看，是青少年信息学奥林匹克联赛的试题。题目不是很难，但是有些解法会容易踩坑。接下来就简要分析这几道算法题。

第一题：不高兴的津津

【问题描述】
津津上初中了。妈妈认为津津应该更加用功学习，所以津津除了上学之外，还要参加妈妈为她报名的各科复习班。另外每周妈妈还会送她去学习朗诵、舞蹈和钢琴。但是津津如果一天上课超过八个小时就会不高兴，而且上得越久就会越不高兴。假设津津不会因为其它事不高兴，并且她的不高兴不会持续到第二天。请你帮忙检查一下津津下周的日程安排，看看下周她会不会不高兴；如果会的话，哪天最不高兴。

【输入文件】
输入文件unhappy.in 包括七行数据，分别表示周一到周日的日程安排。每行包括两个小于10 的非负整数，用空格隔开，分别表示津津在学校上课的时间和妈妈安排她上课的时间。

【输出文件】
输出文件unhappy.out 包括一行，这一行只包含一个数字。如果不会不高兴则输出 0，如果会则输出最不高兴的是周几（用 1, 2, 3, 4, 5, 6, 7 分别表示周一，周二，周三，周四，周五，周六，周日）。如果有两天或两天以上不高兴的程度相当，则输出时间最靠前的一天。

【样例输入】
5 3
6 2
7 2
5 3
5 4
0 4
0 6
【样例输出】
3

【解答】

这道题用简单的数组存储数据，然后找出两个时间相加的和最大的那一天，就可以了。如果有两天相同的话，就取下标较小的。

#include <iostream>
#include <fstream>
using namespace std;
int main()
{
    ifstream in;
    ofstream out;
    int i = 0, temp, num_1, num_2, result[7], max = 0, day = 0;
    in.open("unhappy.in", ios::in);
    out.open("unhappy.out", ios::out);
    while (i < 7)
    {
        in >> temp;
        num_1 = temp;
        in >> temp;
        num_2 = temp;
        result[i] = num_1 + num_2;
        i++;
    }
    in.close();
    for (int i = 0; i < 7; i++)
    {
        if (result[i] > max)
        {
            max = result[i];
            day = i + 1;
        }
    }
    out << day;
    out.close();
}

第二题：花生采摘

【问题描述】鲁宾逊先生有一只宠物猴，名叫多多。这天，他们两个正沿着乡间小路散步，突然发现路边的告示牌上贴着一张小小的纸条：“欢迎免费品尝我种的花生！——熊字”。鲁宾逊先生和多多都很开心，因为花生正是他们的最爱。在告示牌背后，路边真的有一块花生田，花生植株整齐地排列成矩形网格。有经验的多多一眼就能看出，每棵花生植株下的花生有多少。为了训练多多的算术，鲁宾逊先生说：“你先找出花生最多的植株，去采摘它的花生；然后再找出剩下的植株里花生最多的，去采摘它的花生；依此类推，不过你一定要在我限定的时间内回到路边。”
我们假定多多在每个单位时间内，可以做下列四件事情中的一件：

从路边跳到最靠近路边（即第一行）的某棵花生植株；
从一棵植株跳到前后左右与之相邻的另一棵植株；
采摘一棵植株下的花生；
从最靠近路边（即第一行）的某棵花生植株跳回路边。
现在给定一块花生田的大小和花生的分布，请问在限定时间内，多多最多可以采到多少个花生？注意可能只有部分植株下面长有花生，假设这些植株下的花生个数各不相同。例如在图 2 所示的花生田里，只有位于(2, 5), (3, 7), (4, 2), (5, 4)的植株下长有花生，个数分别为 13, 7, 15, 9。沿着图示的路线，多多在 21 个单位时间内，最多可以采到 37 个花生。

【输入文件】
输入文件 peanuts.in 的第一行包括三个整数，M, N 和 K，用空格隔开；表示花生田的大小为 M * N（1 <= M, N <= 20），多多采花生的限定时间为 K（0 <= K <= 1000）个单位时间。接下来的 M 行，每行包括 N 个非负整数，也用空格隔开；第 i + 1 行的第 j 个整数 Pij（0 <= Pij <= 500）表示花生田里植株(i, j)下花生的数目，0 表示该植株下没有花生。

【输出文件】
输出文件 peanuts.out 包括一行，这一行只包含一个整数，即在限定时间内，多多最多可以采到花生的个数。

【样例输入 1】
6 7 21
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
【样例输出 1】
37

【样例输入 2】
6 7 20
0 0 0 0 0 0 0
0 0 0 0 13 0 0
0 0 0 0 0 0 7
0 15 0 0 0 0 0
0 0 0 9 0 0 0
0 0 0 0 0 0 0
【样例输出 2】
28

【解答】

这道题需要用到二维数组去存储花生的数量，因为二维数组有横纵坐标，方便计算路径的长度。
存好每个植株的数量后，单独把有花生的植株存进一个类数组里面，类成员变量记录了植株的坐标和花生数量。
最后根据题意，将这个类数组按花生数量降序排列。每次都取最大的植株。
因为多多只能沿着矩形边缘走，所以计算路径长度用曼哈顿距离。每次从类数组里取一个植株出来，判断是否可以到达，以及是否有足够时间返回路边。

#include <iostream>
#include <fstream>
#include <math.h>
#include <algorithm>
//用一个二维数组记录所有位置的花生，再用另外一个类记录有花生的位置
//不用数组是因为数组排序之后坐标容易弄乱
class Peanuts_have
{
public:
    int x;
    int y;
    int num;
};
using namespace std;
bool comp(Peanuts_have a, Peanuts_have b)
{
    return a.num > b.num;
}
int main()
{
    ifstream in("peanuts.in", ios::in);
    ofstream out("peanuts.out", ios::out);
    int M, N, K;
    in >> M >> N >> K;
    //    先获得第一行的信息
    int peanuts[M + 1][N + 1];
    //    记录所有的花生
    Peanuts_have is_peanuts[M * N];
    //    记录有花生的点
    int numOfPeanutsPoint = 0;
    //    用这个记录有花生的点的数量
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            in >> peanuts[i][j];
            if (peanuts[i][j] != 0)
            {
                numOfPeanutsPoint++;
                is_peanuts[numOfPeanutsPoint].x = i;
                is_peanuts[numOfPeanutsPoint].y = j;
                is_peanuts[numOfPeanutsPoint].num = peanuts[i][j];
            }
        }
    }
    //    上面已经将花生全都导入到数组中，并且记录了有花生的位置及数量
    //    下面对类数组进行排序，按照从大到小的顺序进行花生位置的遍历，并且需要每次都判断是否超时
    sort(is_peanuts + 1, is_peanuts + numOfPeanutsPoint + 1, comp);
    int start_x = 0;
    int start_y = is_peanuts[1].y;
    int end_x;
    int end_y;
    int length;
    int peanuts_sum = 0;
    for (int i = 1; i <= numOfPeanutsPoint; i++)
    {
        end_x = is_peanuts[i].x;
        end_y = is_peanuts[i].y;
        length = (abs(start_x - end_x) + abs(start_y - end_y));
        if ((length + end_x + 1) <= K)
        {
            K--;
            peanuts_sum += is_peanuts[i].num;
            K -= length;
            start_x = is_peanuts[i].x;
            start_y = is_peanuts[i].y;
        }
        else
            break;
    }
    out << peanuts_sum;
    in.close();
    out.close();
}

第三题：FBI树

【问题描述】我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为 B 串，全“1”串称为 I 串，既含“0”又含“1”的串则称为 F串。 FBI 树是一种二叉树，它的结点类型也包括 F结点，B 结点和 I 结点三种。由一个长度为 2N 的“01”串 S 可以构造出一棵 FBI 树 T，递归的构造方法如下：

T 的根结点为 R，其类型与串 S 的类型相同；
若串 S 的长度大于 1，将串 S 从中间分开，分为等长的左右子串 S1 和 S2；由左子串 S1 构造 R 的左子树 T1，由右子串 S2 构造 R 的右子树 T2。现在给定一个长度为 2N 的“01”串，请用上述构造方法构造出一棵 FBI 树，并输出它的后序遍历序列。

【输入文件】
输入文件 fbi.in 的第一行是一个整数 N（0 <= N <= 10），第二行是一个长度为 2N 的“01” 串。

【输出文件】
输出文件 fbi.out 包括一行，这一行只包含一个字符串，即 FBI 树的后序遍历序列。

【样例输入】
3
10001011

【样例输出】
IBFBBBFIBFIIIFF

【数据规模】
对于 40%的数据，N <= 2；
对于全部的数据，N <= 10。

【解答】

这道题初看没什么头绪，画出图之后，就一目了然了。
使用二分法，递归到每一个叶子结点，然后判断是F、B、I的哪一种节点，将结果直接输出到文件。

FBI树示意图

#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
using namespace std;
// 用递归来做
ifstream in("fbi.in", ios::in);
ofstream out("fbi.out", ios::out);
void FBI_tree(string s, int left, int right)
{
    if (left != right)
    {
        FBI_tree(s, left, (left + right) / 2);
        FBI_tree(s, (left + right) / 2 + 1, right);
        // 二分法
    }
    // 如果相等，意味着该子树下只有一个节点，也就是叶节点
    int one = 0, zero = 0;
    for (int i = left; i <= right; i++)
    {
        if (s[i] == '1')
            one = 1;
        if (s[i] == '0')
            zero = 1;
        // 只要判断字符串里面是否有1或0就行
    }
    if (one == 1 && zero == 1)
        out << 'F';
    if (one != 1 && zero == 1)
        out << 'B';
    if (one == 1 && zero != 1)
        out << 'I';
}
int main()
{
    int N, length;
    string S;
    in >> N;
    in >> S;
    length = pow(2, N);
    FBI_tree(S, 0, (length - 1));
    in.close();
    out.close();
    return 0;
}

第四题：火星人

【问题描述】
人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。
火星人用一种非常简单的方式来表示数字——掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 1，2，3……。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。
一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指——拇指、食指、中指、无名指和小指分别编号为 1，2，3，4 和 5，当它们按正常顺序排列时，形成了 5 位数 12345，当你交换无名指和小指的位置时，会形成 5 位数 12354，当你把五个手指的顺序完全颠倒时，会形成 54321，在所有能够形成的 120 个 5 位数中，12345 最小，它表示 1；12354 第二小，它表示 2；54321 最大，它表示 120。下表展示了只有 3 根手指时能够形成的 6 个 3 位数和它们代表的数字：
三进制数
123
132
213
231
312
321
代表的数字
1
2
3
4
5
6
现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

【输入文件】
输入文件 martian.in包括三行，第一行有一个正整数 N，表示火星人手指的数目（1 <= N <= 10000）。第二行是一个正整数 M，表示要加上去的小整数（1 <= M <= 100）。下一行是 1 到 N 这 N 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

【输出文件】
输出文件 martian.out 只有一行，这一行含有 N 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

【样例输入】
5
3
1 2 3 4 5

【样例输出】
1 2 4 5 3

【数据规模】
对于 30%的数据，N<=15；
对于 60%的数据，N<=50；
对于全部的数据，N<=10000；

【解答】

这道题我晚上用传统方法想了很久，一直做不出来，后来无奈去找了题解，发现只是C++ STL里面一个简单的字典序函数，就可以实现了。我对STL还是不熟悉。

转自CSDN某博主，名字忘记了呜呜

#include<iostream>
#include<algorithm>
#include<fstream>
using namespace std;
int main()
{
    ifstream in("martian.in",ios::in);
    ofstream out("martian.out",ios::out);
    int fingers,number;
    int order[11000];
    in>>fingers>>number;
    for(int i =0;i<fingers;i++)
    {
        in>>order[i];
    }
    while(number--)
    {
        next_permutation(order,order+fingers);
    }
    for(int i =0;i<fingers;i++)
    {
        if(i<(fingers-1))
        out<<order[i]<<' ';
        else if(i==(fingers-1))
        out<<order[i];
    }
    in.close();
    out.close();
    return 0;
}

以上题目其实各大论坛都有很多解析，我的解法也肯定不是最优解。如果本文能带给你一些思考，便十分满足。最近几周学院安排实训，每日往返于实验室和宿舍之间，不亦乐乎，慢慢体会到未来工作的节奏。企业工作和大学课程有某些相似，无论是其中的哪个角色，我们都可以找到摸鱼的时机。摸鱼并不是一件十足的坏事。无鱼可摸，工作的压力会让我们难以喘息。摸鱼太多，进度无法完成，工资会跳水，我们得完蛋。如何恰到好处地摸鱼，是我们需要思考的问题，希望大家心中都有一个正确的答案。

近日一些简单题解

第一题：不高兴的津津

【解答】

第二题：花生采摘

【解答】

第三题：FBI树

【解答】

第四题：火星人

【解答】

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

华南理工大学创维维生素

算法