前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >浙江大学计算机与软件学院2019年保研上机模拟练习

浙江大学计算机与软件学院2019年保研上机模拟练习

作者头像
glm233
发布2020-10-30 10:30:54
3730
发布2020-10-30 10:30:54
举报
文章被收录于专栏:glm的全栈学习之路

浙江大学计算机与软件学院2019年保研上机模拟练习

7-1 Happy Numbers (20分)

A happy number is defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits in base-ten, and repeat the process until the number either equals 1 (where it will stay), or it loops endlessly in a cycle that does not include 1. Those numbers for which this process ends in 1 are happy numbers and the number of iterations is called the degree of happiness, while those that do not end in 1 are unhappy numbers (or sad numbers). (Quoted from Wikipedia)

For example, 19 is happy since we obtain 82 after the first iteration, 68 after the second iteration, 100 after the third iteration, and finally 1. Hence the degree of happiness of 19 is 4.

On the other hand, 29 is sad since we obtain 85, 89, 145, 42, 20, 4, 16, 37, 58, and back to 89, then fall into an endless loop. In this case, 89 is the first loop number for 29.

Now your job is to tell if any given number is happy or not.

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then N lines follow, each contains a positive integer (no more than 104) to be tested.

Output Specification:

For each given number, output in a line its degree of happiness if it is happy, or the first loop number if it is sad.

Sample Input:

代码语言:javascript
复制
3
19
29
1

Sample Output:

代码语言:javascript
复制
4
89
0
代码语言:javascript
复制
//
//  main.cpp
//  7-1 Happy Numbers (20分)
//
//  Created by apple on 2020/10/26.
//

#include<bits/stdc++.h>
using namespace std;
int n;
int f(int x)
{
    int sum=0;
    while(x)
    {
        sum+=(x%10)*(x%10);
        x/=10;
    }
    return sum;
}
int main(int argc, const char * argv[]) {
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        if(x==1)
        {
            cout<<0<<endl;
            continue;
        }
        set<int>t;
        t.insert(x);
        int cnt=0;
        while(1)
        {
            int k=f(x);
            if(t.find(k)==t.end())
            {
                t.insert(k);
                x=k;
                cnt++;
            }
            else
            {
                cout<<k<<endl;
                break;
            }
            x=k;
            if(k==1)
            {
                cout<<cnt<<endl;
                break;
            }
        }
    }
    return 0;
}
/*
3
19
29
1
*/

7-2 Zigzag Sequence (25分)

This time your job is to output a sequence of N positive integers in a zigzag format with width M in non-decreasing order. A zigzag format is to fill in the first row with M numbers from left to right, then the second row from right to left, and so on and so forth. For example, a zigzag format with width 5 for numbers 1 to 13 is the following:

代码语言:javascript
复制
1 2 3 4 5
10 9 8 7 6
11 12 13

Input Specification:

Each input file contains one test case. For each case, the first line gives 2 positive integers N and M. Then the next line contains N positive integers as the original sequence. All the numbers are no more than 104. The numbers in a line are separated by spaces.

Output Specification:

For each test case, output the sequence in the zigzag format with width M in non-decreasing order. There must be exactly 1 space between two adjacent numbers, and no extra space at the beginning or the end of each line.

Sample Input 1:

代码语言:javascript
复制
14 5
37 76 98 20 98 76 42 53 99 95 60 81 58 93

Sample Output 1:

代码语言:javascript
复制
20 37 42 53 58
93 81 76 76 60
95 98 98 99

Sample Input 2:

代码语言:javascript
复制
15 4
96 37 76 98 20 98 76 42 53 99 95 60 81 58 93

Sample Output 2:

代码语言:javascript
复制
20 37 42 53
76 76 60 58
81 93 95 96
99 98 98
代码语言:javascript
复制
//
//  main.cpp
//  7-2 Zigzag Sequence (25分)
//
//  Created by apple on 2020/10/26.
//

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int>v;
int main(int argc, const char * argv[]) {
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        int x;
        cin>>x;
        v.push_back(x);
    }
    sort(v.begin(),v.end());
    int cntt=0;
    for(int i=0;i<v.size();i+=m)
    {
        vector<int>tep;
        if(i+m-1>v.size())
        {
            for(int j=i;j<v.size();j++)
            {
                tep.push_back(v[j]);
            }
        }
        else
        {
            for(int j=i;j<v.size();j++)
            {
                tep.push_back(v[j]);
                if(tep.size()==m)break;
            }
        }
        if(cntt%2)reverse(tep.begin(), tep.end());
        //cout<<tep.size()<<endl;
        for(int i=0;i<tep.size();i++)
        {
            i==tep.size()-1?cout<<tep[i]<<endl:cout<<tep[i]<<" ";
        }
        cntt++;
    }
    return 0;
}
/*
14 5
37 76 98 20 98 76 42 53 99 95 60 81 58 93
20 37 42 53 58
93 81 76 76 60
95 98 98 99
*/

7-3 Is It An AVL Tree (25分)

In computer science, an AVL tree (Georgy Adelson-Velsky and Evgenii Landis’ tree, named after the inventors) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. (Quoted from wikipedia)

For each given binary search tree, you are supposed to tell if it is an AVL tree.

Input Specification:

Each input file contains several test cases. The first line gives a positive integer K (≤10) which is the total number of cases. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary search tree. The second line gives the preorder traversal sequence of the tree with all the keys being distinct. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in a line “Yes” if the given tree is an AVL tree, or “No” if not.

Sample Input:

代码语言:javascript
复制
3
7
50 40 36 48 46 62 77
8
50 40 36 48 46 62 77 88
6
50 40 36 48 46 62

Sample Output:

代码语言:javascript
复制
Yes
No
No
代码语言:javascript
复制
//
//  main.cpp
//  7-3 Is It An AVL Tree (25分)
//
//  Created by apple on 2020/10/26.
//

#include<bits/stdc++.h>
using namespace std;
int n;
struct node
{
    int data;
    node *left,*right;
    node(int d): data(d),left(NULL),right(NULL){}
};
inline int geth(node *p)
{
    if(!p)return 0;
    return max(geth(p->left),geth(p->right))+1;
}
inline bool judge(node *p)
{
    if(!p)return true;
    if(abs(geth(p->left)-geth(p->right))>1)return false;
    return judge(p->left)&&judge(p->right);
}
inline node* build(node* p,int val)
{
    if(!p)return new node(val);
    if(val>p->data)
    {
        p->right=build(p->right, val);
        return p;
    }
    if(val<p->data)
    {
        p->left=build(p->left, val);
        return p;
    }
    return p;
}
int main(int argc, const char * argv[]) {
    cin>>n;
    for(int i=0;i<n;i++)
    {
        node *p=NULL;
        int k;
        cin>>k;
        for(int j=0;j<k;j++)
        {
            int x;
            cin>>x;
            p=build(p,x);
        }
        judge(p)?cout<<"Yes"<<endl:cout<<"No"<<endl;
    }
    return 0;
}
/*
3
7
50 40 36 48 46 62 77
8
50 40 36 48 46 62 77 88
6
50 40 36 48 46 62
Yes
No
No
*/

7-4 Index of Popularity (30分)

The index of popularity (IP) of someone in his/her circle of friends is defined to be the number of friends he/she has in that circle. Now you are supposed to list the members in any given friend circle with top 3 IP’s.

Input Specification:

Each input file contains one test case. Each case starts with a line containing 2 positive integers N and M (both no more than 105), which are the total number of people and the number of friend relations, respectively. Hence the people here are numbered from 1 to N.

Then M lines follow, each contains the indices of a pair of friends, separated by a space. It is assumed that if A is a friend of B, then B is a friend of A.

Then several queries follow, each occupies a line. For each line of query, K (3≤KN), the total number of members in this friend circle is given first, with K indices of members follow. It is guaranteed that all the indices in a circle are distinct.

The input ends when K is zero, and this case must NOT be processed.

Output Specification:

For each query, print in a line the members with top 3 indices of popularity in descending order of their IP’s. If there is a tie, output the one with the smaller number. The numbers must be separated by exactly 1 space, and there must be no extra space at the beginning or the end of the line.

Sample Input:

代码语言:javascript
复制
8 10
2 1
1 3
1 4
1 5
5 8
3 5
2 3
6 3
4 6
3 4
7 8 1 2 3 4 6 5
4 1 3 5 2
4 8 7 4 2
0

Sample Output:

代码语言:javascript
复制
3 1 4
1 3 2
2 4 7
代码语言:javascript
复制
//
//  main.cpp
//  7-4 Index of Popularity (30分)
//
//  Created by apple on 2020/10/26.
//

#include <bits/stdc++.h>
using namespace std;
vector<pair<int,int>>edg;
int n,m,vis[100005];
inline bool cmp(const pair<int,int>&a, const pair<int,int>&b)
{
    if(a.second==b.second)return a.first<b.first;
    return a.second>b.second;
}
int main(int argc, const char * argv[]) {
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        edg.push_back(make_pair(a, b));
    }
    while(1)
    {
        memset(vis, 0, sizeof(vis));
        int k;
        cin>>k;
        if(!k)break;
        map<int,int>q;
        for(int i=0;i<k;i++)
        {
            int x;
            cin>>x;
            vis[x]=1;
            q[x]=0;
        }
        vector<pair<int, int>>ans;
        for(int i=0;i<edg.size();i++)
        {
            int x=edg[i].first,y=edg[i].second;
            if(vis[x]&&vis[y])
            {
                q[x]++,q[y]++;
            }
        }
        for(auto it:q)
        {
            ans.push_back(make_pair(it.first, it.second));
        }
        sort(ans.begin(),ans.end(),cmp);
        cout<<ans[0].first<<" "<<ans[1].first<<" "<<ans[2].first<<endl;
    }
    return 0;
}
/*
8 10
2 1
1 3
1 4
1 5
5 8
3 5
2 3
6 3
4 6
3 4
7 8 1 2 3 4 6 5
4 1 3 5 2
4 8 7 4 2
0
*/

总体来说这套题都简单,注意第三题的套路,建树、然后查询高度、比较是一道需要记下来的模版题,其他都是很常规的题目

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/10/26 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Input Specification:
  • Output Specification:
  • Sample Input:
  • Sample Output:
  • Input Specification:
  • Output Specification:
  • Sample Input 1:
  • Sample Output 1:
  • Sample Input 2:
  • Sample Output 2:
  • Input Specification:
  • Output Specification:
  • Sample Input:
  • Sample Output:
  • Input Specification:
  • Output Specification:
  • Sample Input:
  • Sample Output:
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档