吉林大学考研复试题目（牛客网）
- 2019 年 10 月 8 日
- 筆記
吉林大学考研复试题目（牛客网）
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("%dn",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; } }
