专栏首页算法与数据结构吉林大学考研复试题目(牛客网)

吉林大学考研复试题目(牛客网)

吉林大学考研复试题目(牛客网)

1.字符串的反码

题目描述

​ 一个二进制数,将其每一位取反,称之为这个数的反码。下面我们定义一个字符的反码。如果这是一个小写字符,则它和字符'a’的距离与它的反码和字符'z’的距离相同;如果是一个大写字符,则它和字符'A’的距离与它的反码和字符'Z’的距离相同;如果不是上面两种情况,它的反码就是它自身。 举几个例子,'a’的反码是'z’;'c’的反码是'x’;'W’的反码是'D’;'1’的反码还是'1’;'

('的反码还是')

'。 一个字符串的反码定义为其所有字符的反码。我们的任务就是计算出给定字符串的反码。

输入描述:

    输入每行都是一个字符串,字符串长度不超过 80 个字符。如果输入只有!,表示输入结束,不需要处理。

输出描述:

对于输入的每个字符串,输出其反码,每个数据占一行。

示例1

输入

复制

Hello 
JLU-CCST-2011 
!

输出

复制

Svool 
QOF-XXHG-2011

分析:简单的数位运算

#include<iostream>
#include<string>
using namespace std;
int main()
{
    string s;
    while(cin>>s){
        if(s[0]=='!'){
            break;
        }
        else{
            //正常输入
            int len = s.length();
            string ansstr="";
            for(int i = 0; i < len;i++ ){
                if(s[i]>='a'&&s[i]<='z'){
                    ansstr += 'z' - (s[i]-'a');

                }else if(s[i]>='A'&&s[i]<='Z')
                {
                    ansstr += 'Z' - (s[i]-'A');
                }
                else{
                    ansstr+=s[i];
                }
            }
            cout<<ansstr<<endl;
        }
    }
}

2.三角形的边

题目描述

给定三个已知长度的边,确定是否能够构成一个三角形,这是一个简单的几何问题。我们都知道,这要求两边之和大于第三边。实际上,并不需要检验所有三种可能,只需要计算最短的两个边长之和是否大于最大那个就可以了。 这次的问题就是:给出三个正整数,计算最小的数加上次小的数与最大的数之差。

输入描述:

每一行包括三个数据a, b, c,并且都是正整数,均小于10000。

输出描述:

对于输入的每一行,在单独一行内输出结果s。s=min(a,b,c)+mid(a,b,c)-max(a,b,c)。上式中,min为最小值,mid为中间值,max为最大值。

示例1

输入

复制

1 2 3

输出

复制

0

题目分析:简单排序

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
int main()
{
    vector<int> num;
    int a,b,c;
    while(cin>>a>>b>>c){
        //输入
        num.push_back(a);
        num.push_back(b);
        num.push_back(c);
        sort(num.begin(),num.end());
        int ans = num[0] + num[1] - num[2];
        cout<<ans<<endl;
        num.clear();
    }
}

3.怪异的洗牌

题目描述

对于一副扑克牌,我们有多种不同的洗牌方式。一种方法是从中间某个位置分成两半,然后相交换,我们称之为移位(shift)。比如原来的次序是123456,从第4个位置交换,结果就是561234。这个方式其实就是数组的循环移位,为了多次进行这个操作,必须使用一种尽可能快的方法来编程实现。在本题目中,还引入另外一种洗牌方式,就是把前一半(如果总数是奇数,就是(n-1)/2)牌翻转过来,这种操作称之为翻转(flip)。在前面shift操作的结果上进行flip,结果就是165234。当然,如果是实际的扑克牌,直接翻转会造成正反面混在一起的,我们就不管那么多了。 给定n张牌,初始次序为从1到n,经过若干次的shift和flip操作后,结果会是什么样?

输入描述:

输入包括多组测试数据,每组数据的第一行包括两个数 n和k。n表示牌的数目,1<n<1000,k表示下面要进行的操作数量。随后的k行,每行一个整数x,1<=x<=n,表示从第几个位置开始移位。在每一次shift操作后都接一个flip操作。

输出描述:

对于输入的每组数据,计算经过给定的k次shift和flip操作后,各个位置的数值。并按次序在一行上输出所有牌张的值,每个数值(不包括最后一个)后面有一个空格。

示例1

输入

复制

6 1
4

输出

复制

1 6 5 2 3 4
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n,k;
vector<int> num;
void shift(int pos)
{
    reverse(num.begin(),num.begin()+pos);
    reverse(num.begin()+pos,num.end());
    reverse(num.begin(),num.end());
    //多次反转 实现移位效果
}
void filp()
{
    reverse(num.begin(),num.begin()+num.size()/2);
}
int main()
{
    while(~scanf("%d%d",&n,&k))
    {
        num.clear();
        for(int i=1;i<=n;i++)
        {
            num.push_back(i);
        }
        while(k--)
        {
            int pos;
            scanf("%d",&pos);
            shift(pos);
            filp();
        }
        for(int i=0;i<n;i++){
            cout<<num[i]<<" ";
        }
    }
}

4.连通图

题目描述

​ 给定一个无向图和其中的所有边,判断这个图是否所有顶点都是连通的。

输入描述:

    每组数据的第一行是两个整数 n 和 m(0<=n<=1000)。n 表示图的顶点数目,m 表示图中边的数目。随后有 m 行数据,每行有两个值 x 和 y(0<x, y <=n),表示顶点 x 和 y 相连,顶点的编号从 1 开始计算。输入不保证这些边是否重复。

输出描述:

    对于每组输入数据,如果所有顶点都是连通的,输出"YES",否则输出"NO"。

示例1

输入

复制

4 3
1 2
2 3
3 2
3 2
1 2
2 3

输出

复制

NO
YES
#include<bits/stdc++.h>//并查集解决
using namespace std;
const int maxn = 1010;
int maps[maxn][maxn];
int n,m;
int father[maxn];
int findfather(int x){
    return x==father[x]?x:findfather(father[x]);
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        
            memset(maps,0,sizeof(maps));
            for(int i=1;i<=n;i++){
                father[i] = i;
            }
            while(m--){
                int a,b;
                scanf("%d%d",&a,&b);
                int fa = findfather(a);
                int fb = findfather(b);
                if(fa <= fb){
                    father[b] = fa;
                }else{
                    father[a] = fb;
                }
            }
            int counts = 0;
            for(int i=1;i<=n;i++){
                if(father[i] == i){
                    counts++;
                }
            }
            if(counts > 1){
                cout<<"NO"<<endl;
            }else{
                cout<<"YES"<<endl;
            }
        
    }
}

5.排列与二进制

题目描述

在组合数学中,我们学过排列数。从n个不同元素中取出m(m<=n)个元素的所有排列的个数,叫做从n中取m的排列数,记为p(n, m)。具体计算方法为p(n, m)=n(n-1)(n-2)……(n-m+1)= n!/(n-m)! (规定0!=1).当n和m不是很小时,这个排列数是比较大的数值,比如 p(10,5)=30240。如果用二进制表示为p(10,5)=30240=( 111011000100000)b,也就是说,最后面有5个零。我们的问题就是,给定一个排列数,算出其二进制表示的后面有多少个连续的零。

输入描述:

输入包含多组测试数据,每组测试数据一行。
每行两个整数,n和m,0<m<=n<=10000,n=0标志输入结束,该组数据不用处理。

输出描述:

对于每个输入,输出排列数p(n, m)的二进制表示后面有多少个连续的零。每个输出放在一行。

示例1

输入

复制

10 5
6 1
0 0

输出

复制

5
1

解析:

判断末尾几个连续的 0 就是判断可以连续/2的次数

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int n,m;
    int ans = 0;
    int sum = 1;
    while(~scanf("%d%d",&n,&m)&&n!=0)
    {
        for(int i=n-m+1;i<=n;i++)
        {
            sum*=i;
            while(sum%2==0&&sum!=0)
            {
                sum/=2;
                ans++;
            }
        }
        cout<<ans<<endl;
    }
}

6.平方因子

题目描述

给定一个数n,判定它是否有一个不为1的完全平方数因子。也就是说,是否存在某个k,k>1,使得k*k能够整除n。

输入描述:

每行一个整数n,1<n<10000

输出描述:

对于每一个输入的整数,在单独的一行输出结果,如果有不为1的完全平方数因子,则输出Yes,否则输出No。请注意大小写。

示例1

输入

复制

15

输出

复制

No

解析:使用个数值筛

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int numShell[1010];//数值
void init()
{
    for(int i=2;i<=33;i++){
        numShell[i] = i*i;
    }
}
int main()
{
    init();
    int n;
    scanf("%d",&n);
    int i;
    for(i=2;i<=32;i++){
        if(n%numShell[i] == 0){
            cout<<"Yes"<<endl;
            break;
        }
    }
    if(i==33){
        cout<<"No"<<endl;
    }
}

7.数字之和

题目描述

对于给定的正整数 n,计算其十进制形式下所有位置数字之和,并计算其平方的各位数字之和。

输入描述:

每行输入数据包括一个正整数n(0<n<40000)

输出描述:

对于每个输入数据,计算其各位数字之和,以及其平方值的数字之和,输出在一行中,之间用一个空格分隔,但行末不要有空格。

示例1

输入

复制

4
12
97
39999

输出

复制

4 7
3 9
16 22
39 36
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    LL n;
    while(~scanf("%lld",&n)){
        int firstans = 0;
        int secondans = 0;
        LL tmp = n;
        while(tmp){
            firstans+=(tmp%10);
            tmp/=10;
        }
        LL stmp = n*n;
        while(stmp){
            secondans+=(stmp%10);
            stmp/=10;
        }
        cout<<firstans<<" "<<secondans<<endl;
    }
}

7.搬水果

题目描述

​ 在一个果园里,小明已经将所有的水果打了下来,并按水果的不同种类分成了若干堆,小明决定把所有的水果合成一堆。每一次合并,小明可以把两堆水果合并到一起,消耗的体力等于两堆水果的重量之和。当然经过 n‐1 次合并之后,就变成一堆了。小明在合并水果时总共消耗的体力等于每次合并所耗体力之和。 假定每个水果重量都为 1,并且已知水果的种类数和每种水果的数目,你的任务是设计出合并的次序方案,使小明耗费的体力最少,并输出这个最小的体力耗费值。例如有 3 种水果,数目依次为 1,2,9。可以先将 1,2 堆合并,新堆数目为3,耗费体力为 3。然后将新堆与原先的第三堆合并得到新的堆,耗费体力为 12。所以小明总共耗费体力=3+12=15,可以证明 15 为最小的体力耗费值。

输入描述:

    每组数据输入包括两行,第一行是一个整数 n(1<=n<=10000),表示水果的种类数。第二行包含 n 个整数,用空格分隔,第 i 个整数(1<=ai<=1000)是第 i 种水果的数目。

输出描述:

对于每组输入,输出一个整数并换行,这个值也就是最小的体力耗费值。输入数据保证这个值小于 2^31。

示例1

输入

复制

3
9 1 2

输出

复制

15

解析:本质就是huffman树

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
priority_queue<int,vector<int>,greater<int>> Q; //升序优先队列实现最小堆
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        if(n==0)break;
        while(!Q.empty())Q.pop();
        for(int i=0;i<n;++i)
        {
            int x;
            scanf("%d",&x);
            Q.push(x);
        }
        int ans=0;
        while(Q.size()>1){
            int a=Q.top();
            Q.pop();
            int b=Q.top();
            Q.pop();
            ans+=a+b;
            Q.push(a+b);
        }
        printf("%d\n",ans);
    }
    return 0;
}

8.堆栈的使用

分析 模拟题

题目描述

​ 堆栈是一种基本的数据结构。堆栈具有两种基本操作方式,push 和 pop。Push一个值会将其压入栈顶,而 pop 则会将栈顶的值弹出。现在我们就来验证一下堆栈的使用。

输入描述:

     对于每组测试数据,第一行是一个正整数 n,0<n<=10000(n=0 结束)。而后的 n 行,每行的第一个字符可能是'P’或者'O’或者'A’;如果是'P’,后面还会跟着一个整数,表示把这个数据压入堆栈;如果是'O’,表示将栈顶的值 pop 出来,如果堆栈中没有元素时,忽略本次操作;如果是'A’,表示询问当前栈顶的值,如果当时栈为空,则输出'E'。堆栈开始为空。

输出描述:

    对于每组测试数据,根据其中的命令字符来处理堆栈;并对所有的'A’操作,输出当时栈顶的值,每个占据一行,如果当时栈为空,则输出'E’。当每组测试数据完成后,输出一个空行。

示例1

输入

复制

3
A
P 5
A
4
P 3
P 6
O 
A

输出

复制

E
5

3
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
    int n;
    while(~scanf("%d",&n)&&n!=0){
        stack<int> tmp;
        while(!tmp.empty()) tmp.pop();
        char ch;
        for(int i=0;i<n;i++){
            cin>>ch;
            if(ch=='A'){
                if(tmp.empty()){
                    cout<<"E"<<endl;
                }else{
                    cout<<tmp.top()<<endl;
                }
            }else if(ch=='P'){
                int t;
                cin>>t;
                tmp.push(t);
            }else if(ch=='O'){
                if(!tmp.empty())
                tmp.pop();
            }
        }
        cout<<endl;
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 拓扑排序 HDU - 5695

    众所周知,度度熊喜欢各类体育活动。  今天,它终于当上了梦寐以求的体育课老师。第一次课上,它发现一个有趣的事情。在上课之前,所有同学要排成一列, 假设最开始每...

    Kindear
  • 数据结构 图

    1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

    Kindear
  • PTA 7-1 畅通工程之局部最小花费问题(35 分)

    7-1 畅通工程之局部最小花费问题(35 分) 某地区经过对城镇交通状况的调查,得到现有城镇间快速道路的统计数据,并提出“畅通工程”的目标:使整个地区任何两个城...

    Kindear
  • 蓝桥杯-2017年省赛C++B组题6-最大公共子串

    比如:”abcdkkk” 和 “baabcdadabc“, 可以找到的最长的公共子串是”abcd“,所以最大公共子串长度为4。

    Debug客栈
  • 【2020HBU天梯赛训练】7-50 部落

    在一个社区里,每个人都有自己的小圈子,还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里,于是要请你统计一下,在一个给定社区中,到底有多少个互不...

    韩旭051
  • 【每日算法Day 77】LeetCode 第 181 场周赛题解

    https://leetcode-cn.com/contest/weekly-contest-181

    godweiyang
  • poj----1330Nearest Common Ancestors(简单LCA)

    题目连接  http://poj.org/problem?id=1330 就是构建一棵树,然后问你两个节点之间最近的公共父节点是谁? 代码: 1 /*Sour...

    Gxjun
  • 查找二叉树

    【问题描述】 已知一棵二叉树用邻接表结构存储,中序查找二叉树中值为x的结点,并指出是第几个结点。例:如图二叉树的数据文件的数据格式如下 7 15 5 2 3 1...

    attack
  • 105. 从前序与中序遍历序列构造二叉树

    前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树:

    祝你万事顺利
  • P3834 【模板】可持久化线段树 1(主席树) (多次查询第k大或第k小)

    用户2965768

扫码关注云+社区

领取腾讯云代金券