2018年天梯赛第一次训练赛-白红宇

2018年天梯赛第一次训练赛

阅读量：7045 次

发布时间：2019-06-28

本文共 12203 字，大约阅读时间需要 40 分钟。

7-1 列出连通集（25 分）

给定一个有

输入格式:

输入第1行给出2个整数

输出格式:

按照"{

输入样例:

8 60 70 12 04 12 43 5

输出样例:

{ 0 1 4 2 7 }{ 3 5 }{ 6 }{ 0 1 2 7 4 }{ 3 5 }{ 6 }

这个题目就是裸的dfs和bfs，

dfs就是加点判断是否合法继续dfs，bfs把点加进去判断合法直到队列为空

#include
        
         using namespace std;int a[15][15],vis[15],n,e;void dfs(int x){    vis[x]=1;    cout<<" "<

Q; Q.push(X),vis[X]=1; while(!Q.empty()) { int x=Q.front(); Q.pop(); cout<<" "<

>n>>e; for(int i=0,u,v; i

>u>>v,a[u][v]=1,a[v][u]=1; for(int i=0; i

7-2 六度空间（30 分）

“六度空间”理论又称作“六度分隔（Six Degrees of Separation）”理论。这个理论可以通俗地阐述为：“你和任何一个陌生人之间所间隔的人不会超过六个，也就是说，最多通过五个人你就能够认识任何一个陌生人。”如图1所示。

图1 六度空间示意图

“六度空间”理论虽然得到广泛的认同，并且正在得到越来越多的应用。但是数十年来，试图验证这个理论始终是许多社会学家努力追求的目标。然而由于历史的原因，这样的研究具有太大的局限性和困难。随着当代人的联络主要依赖于电话、短信、微信以及因特网上即时通信等工具，能够体现社交网络关系的一手数据已经逐渐使得“六度空间”理论的验证成为可能。

假如给你一个社交网络图，请你对每个节点计算符合“六度空间”理论的结点占结点总数的百分比。

输入格式:

输入第1行给出两个正整数，分别表示社交网络图的结点数

输出格式:

对每个结点输出与该结点距离不超过6的结点数占结点总数的百分比，精确到小数点后2位。每个结节点输出一行，格式为“结点编号:（空格）百分比%”。

输入样例:

10 91 22 33 44 55 66 77 88 99 10

输出样例:

1: 70.00%2: 80.00%3: 90.00%4: 100.00%5: 100.00%6: 100.00%7: 100.00%8: 90.00%9: 80.00%10: 70.00%

没有优化完全瞎写就一个样例没过 我的方法是去dfs这个图，搜到他现在在6个以内，和上一个题目代码差不多

#include
           
            using namespace std;const int N=1e4+5;vector
            
             V[N];int vis[N],num,n,m;void dfs(int X,int f){    if(f>6)return;    vis[X]=1,num++;    for(auto E:V[X])    if(!vis[E])dfs(E,f+1);    vis[X]=0;}int main(){    ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    cin>>n>>m;    for(int i=0,u,v;i
             
              >u>>v,V[u].push_back(v),V[v].push_back(u);    for(int i=1;i<=n;i++)    {        printf("%d: ",i);        num=0;        dfs(i,0);        printf("%.2f%%\n",num*100./n);    }}

7-3 哈利·波特的考试（25 分）

哈利·波特要考试了，他需要你的帮助。这门课学的是用魔咒将一种动物变成另一种动物的本事。例如将猫变成老鼠的魔咒是haha，将老鼠变成鱼的魔咒是hehe等等。反方向变化的魔咒就是简单地将原来的魔咒倒过来念，例如ahah可以将老鼠变成猫。另外，如果想把猫变成鱼，可以通过念一个直接魔咒lalala，也可以将猫变老鼠、老鼠变鱼的魔咒连起来念：hahahehe。

现在哈利·波特的手里有一本教材，里面列出了所有的变形魔咒和能变的动物。老师允许他自己带一只动物去考场，要考察他把这只动物变成任意一只指定动物的本事。于是他来问你：带什么动物去可以让最难变的那种动物（即该动物变为哈利·波特自己带去的动物所需要的魔咒最长）需要的魔咒最短？例如：如果只有猫、鼠、鱼，则显然哈利·波特应该带鼠去，因为鼠变成另外两种动物都只需要念4个字符；而如果带猫去，则至少需要念6个字符才能把猫变成鱼；同理，带鱼去也不是最好的选择。

输入格式:

输入说明：输入第1行给出两个正整数

输出格式:

输出哈利·波特应该带去考场的动物的编号、以及最长的变形魔咒的长度，中间以空格分隔。如果只带1只动物是不可能完成所有变形要求的，则输出0。如果有若干只动物都可以备选，则输出编号最小的那只。

输入样例:

6 113 4 701 2 15 4 502 6 505 6 601 3 704 6 603 6 805 1 1002 4 605 2 80

输出样例:

4 70

这个题目我并没有读懂题，只知道是个图，不联通的话输出0，那就先写一个判断联通的代码，看来没有理解错

然后就去观察数据，100很小，那很可能是Floyd，一看数据就是输出一个顶点内最大的最短路了

#include
              
               using namespace std;const int INF=0x3f3f3f3f;const int N=105;int a[N][N],vis[N],tot,n,m;void dfs(int x){    vis[x]=1;    for(int i=1;i<=n;i++)    {        if(a[x][i]!=INF&&!vis[i])        dfs(i);    }}int main(){    cin>>n>>m;    memset(a,INF,sizeof a);    for(int i=1;i<=n;i++)a[i][i]=0;    for(int i=0,u,v,w;i
               
                >u>>v>>w,a[u][v]=a[v][u]=w;    dfs(1);    int f=0;    for(int i=1;i<=n;i++)if(!vis[i])f=1;    if(f)printf("0");    else    {        for(int k=1;k<=n;k++)            for(int i=1;i<=n;i++)            for(int j=1;j<=n;j++)            a[i][j]=min(a[i][j],a[i][k]+a[k][j]);        int ans=INF,maf=0;        for(int i=1;i<=n;i++)        if(*max_element(a[i]+1,a[i]+n+1)

7-4 统计工龄（20 分）

给定公司

输入格式:

输入首先给出正整数

输出格式:

按工龄的递增顺序输出每个工龄的员工个数，格式为：“工龄:人数”。每项占一行。如果人数为0则不输出该项。

输入样例:

810 2 0 5 7 2 5 2

输出样例:

0:12:35:27:110:1

还要排序，直接就是map了

#include
                 
                  using namespace std;map
                  
                   M;int main(){   int n;   cin>>n;   for(int i=0,x;i
                   
                    >x,M[x]++;   for(auto X:M)   {       cout<
                    
                     <<":"<
                     
                      <<"\n";   }}

7-5 电话聊天狂人（25 分）

给定大量手机用户通话记录，找出其中通话次数最多的聊天狂人。

输入格式:

输入首先给出正整数

输出格式:

在一行中给出聊天狂人的手机号码及其通话次数，其间以空格分隔。如果这样的人不唯一，则输出狂人中最小的号码及其通话次数，并且附加给出并列狂人的人数。

输入样例:

413005711862 1358862583213505711862 1308862583213588625832 1808792583215005713862 13588625832

输出样例:

13588625832 3

又是一个map的题目，不过如果这样的人不唯一，还要输出其通话次数，那就统计一下好了

#include
                    
                     using namespace std;typedef long long ll;map
                     
                      M;ll s,t;int main(){    int n;    cin>>n;    for(int i=0;i
                      
                       >s>>t,M[s]++,M[t]++;    int f=1,ma=0;    for(auto X:M)    {        if(X.second==ma)f++;        else if(X.second>ma)s=X.first,ma=X.second,f=1;    }    cout<
                       <<" "<

7-6 查找书籍（20 分）

给定n本书的名称和定价，本题要求编写程序，查找并输出其中定价最高和最低的书的名称和定价。

输入格式:

输入第一行给出正整数n（

输出格式:

在一行中按照“价格, 书名”的格式先后输出价格最高和最低的书。价格保留2位小数。

输入样例:

3Programming in C21.5Programming in VB18.5Programming in Delphi25.0

输出样例:

25.00, Programming in Delphi18.50, Programming in VB

分别去标记最大价值和最小价值的书，两次getline去掉多余的换行符

#include
                       
                        using namespace std;int main(){   int n;   cin>>n;   string mis,mas,x;   double ma=0,mi=1e8,p;   for(int i=0;i
                        
                         >p;       if(p>ma)mas=x,ma=p;       if(p

7-7 计算火车运行时间（15 分）

本题要求根据火车的出发时间和达到时间，编写程序计算整个旅途所用的时间。

输入格式：

输入在一行中给出2个4位正整数，其间以空格分隔，分别表示火车的出发时间和到达时间。每个时间的格式为2位小时数（00-23）和2位分钟数（00-59），假设出发和到达在同一天内。

输出格式：

在一行输出该旅途所用的时间，格式为“hh:mm”，其中hh为2位小时数、mm为2位分钟数。

输入样例：

1201 1530

输出样例：

03:29

依旧是一个进制转换的问题，先把时间转换为一天的第几分钟，统计这个时间的差，然后转换为60进制

#include
                          
                           using namespace std;int main(){   int n,m;   cin>>n>>m;   int m1=n%100,h1=n/100,m2=m%100,h2=m/100;   int c=h2*60+m2-h1*60-m1;   printf("%02d:%02d",c/60,c%60);}

7-8 三天打鱼两天晒网（15 分）

中国有句俗语叫“三天打鱼两天晒网”。假设某人从某天起，开始“三天打鱼两天晒网”，问这个人在以后的第N天中是“打鱼”还是“晒网”？

输入格式：

输入在一行中给出一个不超过1000的正整数N。

输出格式：

在一行中输出此人在第N天中是“Fishing”（即“打鱼”）还是“Drying”（即“晒网”），并且输出“in day N”。

输入样例1：

输出样例1：

Fishing in day 103

输入样例2：

输出样例2：

Drying in day 34

5天是一个周期的，直接算

#include
                             
                              using namespace std;typedef long long ll;int main(){    int n;    cin>>n;    int c=n%5;    if(c>0&&c<4)cout<<"Fishing in day "<

7-9 查找整数（10 分）

本题要求从输入的N个整数中查找给定的X。如果找到，输出X的位置（从0开始数）；如果没有找到，输出“Not Found”。

输入格式：

输入在第一行中给出两个正整数N（

输出格式：

在一行中输出X的位置，或者“Not Found”。

输入样例1：

5 73 5 7 1 9

输出样例1：

输入样例2：

5 73 5 8 1 9

输出样例2：

Not Found

用一个变量去标记这个数的位置

#include
                                
                                 using namespace std;typedef long long ll;int main(){    ll n,X,x,f=-1;    cin>>n>>X;    for(int i=0;i
                                 
                                  >x;        if(X==x)f=i;    }    if(f!=-1)    cout<

7-10 有理数比较（10 分）

本题要求编写程序，比较两个有理数的大小。

输入格式：

输入在一行中按照“a1/b1 a2/b2”的格式给出两个分数形式的有理数，其中分子和分母全是整形范围内的正整数。

输出格式：

在一行中按照“a1/b1 关系符 a2/b2”的格式输出两个有理数的关系。其中“

输入样例1：

1/2 3/4

输出样例1：

1/2 < 3/4

输入样例2：

6/8 3/4

输出样例2：

6/8 = 3/4

分数a/b和c/d比较可以直接对角相乘，就是ad和bc的大小

#include
                                   
                                    using namespace std;typedef long long ll;int main(){    int a,b,c,d;    scanf("%d/%d%d/%d",&a,&b,&c,&d);    cout<
                                    <<"/"<<<" ";    if(a*d>b*c)        cout<<">";    else if(a*d==b*c)        cout<<"=";    else cout<<"<";    cout<<" "<
                                      
                                       <<"/"<

7-11 Windows消息队列（25 分）

消息队列是Windows系统的基础。对于每个进程，系统维护一个消息队列。如果在进程中有特定事件发生，如点击鼠标、文字改变等，系统将把这个消息加到队列当中。同时，如果队列不是空的，这一进程循环地从队列中按照优先级获取消息。请注意优先级值低意味着优先级高。请编辑程序模拟消息队列，将消息加到队列中以及从队列中获取消息。

输入格式:

输入首先给出正整数N（

输出格式:

对于每个GET指令，在一行中输出消息队列中优先级最高的消息的名称和参数。如果消息队列中没有消息，输出EMPTY QUEUE!。对于PUT指令则没有输出。

输入样例:

9PUT msg1 5PUT msg2 4GETPUT msg3 2PUT msg4 4GETGETGETGET

输出样例:

msg2msg3msg4msg1EMPTY QUEUE!

优先队列，但是需要关输入输出流

#include
                                      
                                       using namespace std;struct T{    string s;    int f;    friend bool operator <(T a,T b)    {        return a.f>b.f;    }} X;priority_queue
                                       
                                        Q;int main(){    ios::sync_with_stdio(false);    cin.tie(0),cout.tie(0);    int n,f;    cin>>n;    for(int i=0; i
                                        
                                         >s;        if(s[0]=='P')        {            cin>>X.s>>X.f;            Q.push(X);        }        else        {            if(Q.empty())            {                cout<<"EMPTY QUEUE!\n";            }            else            {                X=Q.top();                Q.pop();                cout<
                                         
                                          <<"\n";            }        }    }}

7-12 地下迷宫探索（30 分）

地道战是在抗日战争时期，在华北平原上抗日军民利用地道打击日本侵略者的作战方式。地道网是房连房、街连街、村连村的地下工事，如下图所示。

我们在回顾前辈们艰苦卓绝的战争生活的同时，真心钦佩他们的聪明才智。在现在和平发展的年代，对多数人来说，探索地下通道或许只是一种娱乐或者益智的游戏。本实验案例以探索地下通道迷宫作为内容。

假设有一个地下通道迷宫，它的通道都是直的，而通道所有交叉点（包括通道的端点）上都有一盏灯和一个开关。请问你如何从某个起点开始在迷宫中点亮所有的灯并回到起点？

输入格式:

输入第一行给出三个正整数，分别表示地下迷宫的节点数

输出格式:

若可以点亮所有节点的灯，则输出从

由于深度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以节点小编号优先的次序访问（点灯）。在点亮所有可以点亮的灯后，以原路返回的方式回到起点。

输入样例1:

6 8 11 22 33 44 55 66 43 61 5

输出样例1:

1 2 3 4 5 6 5 4 3 2 1

输入样例2:

6 6 61 21 32 35 46 56 4

输出样例2:

6 4 5 4 6 0

dfs这个图，标记路

最后判断一下连通性

#include
                                         
                                          using namespace std;const int N=1005;int a[N][N],vis[N],tot,path[N+N],n,m,s;void dfs(int x){    for(int i=1;i<=n;i++)    {        if(a[x][i]&&!vis[i])        {            vis[i]=1;            path[tot++]=i;            dfs(i);            path[tot++]=x;        }    }}int main(){    cin>>n>>m>>s;    for(int i=0,u,v;i
                                          
                                           >u>>v,a[u][v]=a[v][u]=1;    path[tot++]=s,vis[s]=1;    dfs(s);    printf("%d",path[0]);    for(int i=1;i

7-13 I Love GPLT（5 分）

这道超级简单的题目没有任何输入。

你只需要把这句很重要的话 —— I Love GPLT ——竖着输出就可以了。

所谓“竖着输出”，是指每个字符占一行（包括空格），即每行只能有1个字符和回车。

输出裸题

#include
                                            
                                             using namespace std;int main(){    cout<<"I\n \nL\no\nv\ne\n \nG\nP\nL\nT\n";}

7-14 验证手机号（5 分）

某系统在新用户注册时必须输入手机号，为了提高系统效率，防止输错手机号，需要对手机号进行验证。验证规则为：（1）长度为11位（2）由数字0~9组成（3）必须是1开头以上3个条件同时满足，则验证通过，否则为不通过。

输入格式:

在一行中一个字符串，长度不超过20个字符。

输出格式:

如果验证通过则输出yes，否则输出no。

输入样例:

13812345678

输出样例:

yes

if裸题，假设成立

#include
                                               
                                                using namespace std;int main(){    string s;    int f=1;    cin>>s;    if(s[0]!='1')f=0;    if(s.length()!=11)f=0;    for(int i=0;s[i];i++)        if(s[i]<'0'||s[i]>'9')f=0;    printf("%s",f?"yes":"no");}