吉林大學考研複試題目（牛客網）
- 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; } }
