杭电计算机2013年硕士研究生复试详解

不念不忘少年蓝@ 2022-05-29 03:06 248阅读 0赞

# **题目一：** #

简要描述：输入一个数，代表要检测的例子的个数，每个例子中：  
输入两个时间（格式HH:MM:SS），前面时间减去后面时间，输出在时钟上显示的时间，格式一样，如果是以为数字的前面补零。  
思路：  
这道题有个知识盲区，在输出格式上进行控制，如果不满足两位就补0。我们可以用printf函数来实现该功能。  
1、用h1,m1,s1…等来存储这两个时间。  
2、s1-s2的时候，如果够减，就用s3保存结果，如果不够减，就s3=s1+60-s2,秒针就向分针借走一位。然后分针m1–;  
3、m1-m2的时候同第二步。  
4、h1-h2的时候，如果够减就将结果保存到h3中，不够减就优先+24然后再减。

#include<stdio.h>
    #include<string.h>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    int main(){
        int n;
        cin>>n;
        while(n--){
            int hh1,mm1,ss1;
            int hh2,mm2,ss2;
            scanf("%d:%d:%d",&hh1,&mm1,&ss1);
            scanf("%d:%d:%d",&hh2,&mm2,&ss2);
            int hdiff=hh1-hh2;
            int mdiff=mm1-mm2;
            int sdiff=ss1-ss2;
            if(sdiff<0){
                sdiff=sdiff+60;
                mdiff--;
            } 
            if(mdiff<0){
                mdiff+=60;
                hdiff--;
            }
            if(hdiff<0)
                hdiff+=24;
            printf("%02d:%02d:%02d",hdiff,mdiff,sdiff);//%02d用来控制输出格式。 
        }
    
        return 0;
    }

# **题目二：** #

简要描述：一个活动有N个人参加，一个主持人和N-1个普通参加者，其中所有的人都认识主持人，主持人也认识所有的人，主持人要求N-1个参加者说出他们在参加者中所认识的人数，如果A认识B，则B认识A，所以最少是会认识一个人，就是主持人，他们说出了自己所认识的人数后，需要判断他们中有没有人说谎。  
输入：  
第一行是N，N=0表示结束  
第二行是N-1个数字  
输出：  
Lie absolutely 或者 Maybe truth  
7  
1 2 4 5 5 3

9  
3 7 7 7 7 5 6 6  
两个测试例子中第一个是Lie absolutely，第二个是Maybe truth  
**思路：**根据题意，我们把这个想成一幅图，每个人都是一个点，最开始每个点都和中心点（主持人有连线），接下来，每个人都开始说，自己有几根连线（也就是自己认识多少人），我们把所有人（除主持人）的连线都切除，那么如果没有人撒谎的话，最后应该每个人都只有一条连接主持人的线。同时，我们并不知道谁连着谁，所以我们在切线的时候，优先斩断线多的点。  
1、sort排序，将认识人的多少对其进行排序  
2、遍历数组（数组中存储的有除了主持人以外，其他的所有人说的话）  
3、每经过一个人，这个人如果认识n个人，那么就把他后面的n-1个人的数据都-1，然后把该人的数据置为1，这样就能够做到切断所有除主持人以外的线。  
4、全部切完之后，如果除了主持人以外所有的人都只有一条线，那么就说明有可能没人说谎，如果存在有人和谁都没有连接线，说明这些人当中有人说谎。  
**举例分析一下：**  
输入N个数，再输入N-1个数  
9  
3 7 7 7 7 5 6 6

先把这N-1个数字按从大到小排序  
7 7 7 7 6 6 5 3  
第一个人认识了7个人，除了主持人还剩6个，就当是认识最靠近他后面的6个。  
这样，除去第一个人，后面认识的人就都减少了一个，变成了：

7 6 6 6 5 5 4 3  
再次排序  
从第二个人，除了主持人和第一个，应该认识5个人，就当是认识最靠近他后面的5个  
这样，除去这个人，后面认识的人就都减少了一个，变成了  
7 6 5 5 4 4 3 3

排序，相减，重复下去

如果最后出现了0，就说明有人说谎  
如果排序后，当前认识的人和其后面的人数都是1了，那一个人都是主持人，也是Maybe truth

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    using namespace std; 
    bool cmp(int a,int b){
        return a>b;
    }
    int main(){
        int n;
        int a[101];
        while(cin>>n){
            for(int i=0;i<n-1;i++)//以此输入每个人认识的关系 
                cin>>a[i]; 
            for(int i=0;i<n-1;i++ ){
       //开始截断每个点的关系 
                sort(a+i,a+n-1,cmp);
                if(a[n-2]==0){
       //如果边最小的节点失去和主持人的联系 
                    cout<<"Lie absolutely"<<endl;
                    break;
                }
                else if(a[i]==1){
                    //因为已经排过序了，当前节点为1意味着后面的所有节点都是1，这种情况是可能的。 
                    cout<<"Maybe truth " <<endl;
                    break;
                }
                for(int j=1;j<a[i];j++)//如果判断不出来，就开始斩断联系。 
                    a[i+j]--;//后面的点斩断一条线。 
                a[i]=1;//将当前节点斩断联系，只留一条到主持人的路线。 
            }
        }
        return 0;
    }