2022团体程序设计天梯赛 L2题解_团队设计天梯赛题目及答案大全

L2-041 插松枝  题目链接

题目描述

人造松枝加工场的工人需要将各种尺寸的塑料松针插到松枝干上，做成大大小小的松枝。他们的工作流程（并不）是这样的：

• 每人手边有一只小盒子，初始状态为空。
• 每人面前有用不完的松枝干和一个推送器，每次推送一片随机型号的松针片。
• 工人首先捡起一根空的松枝干，从小盒子里摸出最上面的一片松针 —— 如果小盒子是空的，就从推送器上取一片松针。将这片松针插到枝干的最下面。
• 工人在插后面的松针时，需要保证，每一步插到一根非空松枝干上的松针片，不能比前一步插上的松针片大。如果小盒子中最上面的松针满足要求，就取之插好；否则去推送器上取一片。如果推送器上拿到的仍然不满足要求，就把拿到的这片堆放到小盒子里，继续去推送器上取下一片。注意这里假设小盒子里的松针片是按放入的顺序堆叠起来的，工人每次只能取出最上面（即最后放入）的一片。
• 当下列三种情况之一发生时，工人会结束手里的松枝制作，开始做下一个：

（1）小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。

（2）小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。

（3）手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。

现在给定推送器上顺序传过来的 N 片松针的大小，以及小盒子和松枝的容量，请你编写程序自动列出每根成品松枝的信息。

输入格式：

输入在第一行中给出 3 个正整数：N（≤103），为推送器上松针片的数量；M（≤20）为小盒子能存放的松针片的最大数量；K（≤5）为一根松枝干上能插的松针片的最大数量。

随后一行给出 N 个不超过 100 的正整数，为推送器上顺序推出的松针片的大小。

输出格式：

每支松枝成品的信息占一行，顺序给出自底向上每片松针的大小。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：
8 3 4
20 25 15 18 20 18 8 5
输出样例：
20 15
20 18 18 8
25 5

分析：模拟题，按照题意往下写就行，麻烦的是判断太多，我的起手思路是根据succ数组中有无树叶开始，因为题目里虽然说每次起手都从小盒子里拿，但是如果succ中有树叶，不需要考虑小盒子里的树叶，因为小盒子里的top树叶就是上一次不满足条件才放进去的，所以直接从传送带上拿就可以，之后再展开判断就可以，题目思路很多这只是我的一种想法，大佬看看就行。

然后报段错误是访问了空的queue或者stack，例如直接访问queue.front()这样就会报错，解决方案是在前面加判断非空

while（!queue.empty() ）queue.front();

AC代码

#include<bits/stdc++.h>
using namespace std;
 
stack<int>box;
vector<int>succ;
queue<int>con;
int n,m,k,i;
 
void coutt()
{
    for( i =0; i<succ.size()-1; i++)
        cout<<succ[i]<<" ";
    cout<<succ[i]<<endl;
    succ.clear();
}
 
int main()
{
    cin>>n>>m>>k;
    int mark=0;
    while(n--)
    {
        int x;
        cin>>x;
        con.push(x);
    }
    while(!con.empty())
    {
        //小盒子已经满了，但推送器上取到的松针仍然不满足要求。此时将手中的松枝放到成品篮里，推送器上取到的松针压回推送器，开始下一根松枝的制作。
        if(!box.empty()&&!succ.empty())
            if(box.size()==m&&box.top()>succ.back()&&con.front()>succ.back())
                coutt();
 
        if(succ.size()==k)//手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。
            coutt();
 
        if(succ.empty())
        {
            if(box.empty())
            {//box里面没树叶，从传送带上拿;
                succ.push_back(con.front());
                con.pop();
            }
            else
            {//box里有值,循环从box里取树叶;
                while(1)
                {
                    if(succ.size()==k)
                    {
                        coutt();break;
                    }
                    if(!succ.empty())
                    {//如果succ不为空
                        if(succ.back()>=box.top())
                        {
                            succ.push_back(box.top());
                            box.pop();
 
                        }
                        else//box里的不满足退出循环，从传输带上取树叶;
                            break;
                    }
                    else
                    {//如果succ为空;
                        succ.push_back(box.top());
                        box.pop();
                    }
                    if(box.size()==0)//连续从box里面取值，防止取空;
                        break;
                }
            }
        }
        else
        {//不为空的时候，不用考虑从box里取值；直接从传送带上取;
            if(succ.back()>=con.front())
            {
                succ.push_back(con.front());
                con.pop();
            }
            else
            {
                box.push(con.front());
                con.pop();
            }
        }
    }
    //小盒子中最上面的松针不满足要求，但推送器上已经没有松针了。此时将手中的松枝放到成品篮里，开始下一根松枝的制作。
    if(succ.size()>0&&!box.empty())
        coutt();
    //清空box
    while(!box.empty())
    {
        if(succ.size()==k)//手中的松枝干上已经插满了松针，将之放到成品篮里，开始下一根松枝的制作。
            coutt();
        if(succ.empty())
        {
            succ.push_back(box.top());
            box.pop();
        }
        else
        {
            if(succ.back()>=box.top())
            {
                succ.push_back(box.top());
                box.pop();
            }
            else
                coutt();
        }
    }
    //输出最后一个
    if(succ.size()>0)
        coutt();
    return 0;
}
 
 

L2-042 老板的作息表 题目链接

题目描述：

新浪微博上有人发了某老板的作息时间表，表示其每天 4:30 就起床了。但立刻有眼尖的网友问：这时间表不完整啊，早上九点到下午一点干啥了？

本题就请你编写程序，检查任意一张时间表，找出其中没写出来的时间段。

输入格式：

输入第一行给出一个正整数 N，为作息表上列出的时间段的个数。随后 N 行，每行给出一个时间段，格式为：

hh:mm:ss - hh:mm:ss

其中 hh、mm、ss 分别是两位数表示的小时、分钟、秒。第一个时间是开始时间，第二个是结束时间。题目保证所有时间都在一天之内（即从 00:00:00 到 23:59:59）；每个区间间隔至少 1 秒；并且任意两个给出的时间区间最多只在一个端点有重合，没有区间重叠的情况。

输出格式：

按照时间顺序列出时间表中没有出现的区间，每个区间占一行，格式与输入相同。题目保证至少存在一个区间需要输出。

输入样例：
8
13:00:00 - 18:00:00
00:00:00 - 01:00:05
08:00:00 - 09:00:00
07:10:59 - 08:00:00
01:00:05 - 04:30:00
06:30:00 - 07:10:58
05:30:00 - 06:30:00
18:00:00 - 19:00:00
输出样例：
04:30:00 - 05:30:00
07:10:58 - 07:10:59
09:00:00 - 13:00:00
19:00:00 - 23:59:59

分析：简单的结构体排序，根据每段前面的时间排序，n的范围，如果是开一个结构体数组的话需要计算一下最坏的情况是多大，24*60*60=86400（题目已经说了是最小间隔是1秒），这里建议开一个vector<struct> 不需要考虑存不下的情况； 坑点是排完序之后还需要判断第一个的第一个时间是不是00:00:00，最后一个的第二个时间是不是23:59:59，在循环前后特判一下就可解决；

AC代码

#include<bits/stdc++.h>
 
using namespace std;
 
struct in
{
    string s1,s2;
}frontt;
int n;
vector <struct in>ans;
 
int cmp(struct in a,struct in b)
{
    return a.s1<b.s1;
}
 
int main()
{
    cin>>n;
    while(n--)
    {
        cin>>frontt.s1;
        scanf(" - ");
        cin>>frontt.s2;
        ans.push_back(frontt);
    }
    sort(ans.begin(),ans.end(),cmp);
 
    if(ans[0].s1!="00:00:00")
        cout<<"00:00:00"<<" - "<<ans[0].s1<<endl;
 
    for(int k=1;k<ans.size();k++)
        if(ans[k].s1!=ans[k-1].s2)
            cout<<ans[k-1].s2<<" - "<<ans[k].s1<<endl;
 
    if(ans[ans.size()-1].s2!="23:59:59")
        cout<<ans[ans.size()-1].s2<<" - "<<"23:59:59"<<endl;
    return 0;
}

L2-043 龙龙送外卖 题目链接

题目描述：

龙龙是“饱了呀”外卖软件的注册骑手，负责送帕特小区的外卖。帕特小区的构造非常特别，都是双向道路且没有构成环 —— 你可以简单地认为小区的路构成了一棵树，根结点是外卖站，树上的结点就是要送餐的地址。

每到中午 12 点，帕特小区就进入了点餐高峰。一开始，只有一两个地方点外卖，龙龙简单就送好了；但随着大数据的分析，龙龙被派了更多的单子，也就送得越来越累……

看着一大堆订单，龙龙想知道，从外卖站出发，访问所有点了外卖的地方至少一次（这样才能把外卖送到）所需的最短路程的距离到底是多少？每次新增一个点外卖的地址，他就想估算一遍整体工作量，这样他就可以搞明白新增一个地址给他带来了多少负担。

输入格式：

输入第一行是两个数 N 和 M (2≤N≤105, 1≤M≤105)，分别对应树上节点的个数（包括外卖站），以及新增的送餐地址的个数。

接下来首先是一行 N 个数，第 i 个数表示第 i 个点的双亲节点的编号。节点编号从 1 到 N，外卖站的双亲编号定义为 −1。

接下来有 M 行，每行给出一个新增的送餐地点的编号 Xi​。保证送餐地点中不会有外卖站，但地点有可能会重复。

为了方便计算，我们可以假设龙龙一开始一个地址的外卖都不用送，两个相邻的地点之间的路径长度统一设为 1，且从外卖站出发可以访问到所有地点。

注意：所有送餐地址可以按任意顺序访问，且完成送餐后无需返回外卖站。

输出格式：

对于每个新增的地点，在一行内输出题目需要求的最短路程的距离。

输入样例:
7 4
-1 1 1 1 2 2 3
5
6
2
4
输出样例:
2
4
4
6

分析：范围10^5不能直接dfs去找最短路，时间超限，也不能直接从根节点往下找符合条件的节点集合，（这道题卡时间卡的很严），所以这道题的思路是从下往上找，找到根节点返回，记录所有经过的节点数，最后的答案是：节点数*2-max(节点深度)，时间优化是在递归回溯的时候把深度记录，下次在访问到的时候就不用往下继续去找。

AC代码

#include<bits/stdc++.h>
using namespace std;
 
set<int>sett;
int n,m;
int deep[100001]= {0};
int fa[100001];
int maxx;
 
void findd(int x)
{
    if(sett.find(x)!=sett.end())//遇到之前走过的点就不往下走了
    {
        deep[x]=deep[ fa[x] ]+1;//记录深度
        return ;
    }
    sett.insert(x);//记录经过节点数，去重
    if(fa[x]==-1)
    {
        deep[ x ]=1;
        return ;
    }
    else
    {
        findd( fa[x] );
        deep[x]=deep[ fa[x] ]+1;//回溯的时候记录深度
    }
}
 
int main()
{
    cin>>n>>m;
    deep[1]=1;
    for(int i=1; i<=n; i++)
    {
        int x;
        cin>>x;
        fa[i]=x;
    }
    while(m--)
    {
        int x;
        cin>>x;
        findd(x);
        maxx=max(maxx,deep[x]-1);
        cout<<(sett.size()-1)*2-maxx<<endl;
    }
    return 0;
}

L2-044 大众情人

待补……