山东大学机试试题合集

🍰🍰🍰高分篇已经涵盖了绝大多数的机试考点，由于临近预推免，各校的机试蜂拥而至，我们接下来先更一些各高校机试题合集，算是对前边学习成果的深入学习，也是对我们代码能力的锻炼。加油！fighting！( •̀ ω •́ )✧

我习惯于在注释中解释算法思路，所以可能没有题解，大家可以直接看代码。

🍩1832 字符串的差

#include<bits/stdc++.h>
using namespace std;
int main()
{string a,b,ans;cin>>a>>b;int lena=a.size(),lenb=b.size(),lb=0;//我们使用一次遍历，如果a和b的当前位置的字符一样，那么这个字符就会被删掉，就不用加入结果字符串了，同时b的当前位置的字符比较完了，要到b的下一个位置继续后续比较；否则就要被加入结果字符串了。for(int i=0;i<lena;i++){if(lb==lenb) break;//这一句要注意，没有的话有25%过不了if(a[i]==b[lb]) lb++;else ans+=a[i];}cout<<ans;return 0;
}

🍩1835 插入乘号🍦

//摘自N诺用户：JohnWang
//这道题目使用动态规划
#include<bits/stdc++.h>
using namespace std;
int dp[11][11]={0}; //dp[i][k]表示前i位数中插入k个乘号的最大值
int a[11][11]={0}; //a[i][j]表示从第i个数字到第j个数字所组成的j-i+1位整数值 int main()
{int n,k,num;string s;cin>>n>>k;cin>>s;for(int i=0;i<n;i++)//初始化数组a的值{num=0;for(int j=i;j<n;j++){num=num*10+(s[j]-'0');a[i][j]=num;}}for(int i=0;i<n;i++) dp[i][0]=a[0][i];//对所有位置来说，前边放置0个乘号的最大值都是数值（0到当前位的）本身for(int i=0;i<n;i++)//遍历所有数字，放置k个乘号{for(int j=1;j<=k;j++){for(int l=0;l<i;l++) dp[i][j]=max(dp[l][j-1]*a[l+1][i],dp[i][j]);//前i位数中插入j个乘号的最大值可能的情况：要么自身就已经是最大值；//要么是前边某个位置往前插入了j-1个乘号，然后我（i）这里再插入一个乘号，此时最大值是前边那个最大值*那个位置到我这里的数值}}cout<<dp[n-1][k]<<endl;return 0;
}

🍩1836 最长递减子序列🍦

#include<bits/stdc++.h>
using namespace std;
int main()
{int n,m,maxlen=1;int a[105],b[105],dp[105];//a记录原始数据，b记录最长递减序列，dp记录到当前位置的最长递减序列长度cin>>n;for(int i=1;i<=n;i++)//输入数据{cin>>a[i];dp[i]=1;}for(int i=1;i<=n;i++)//更新dp{for(int j=i;j>0;j--)if(a[j]>a[i])//如果我的前边有人比我大，那么我就可以放到那个数的后边（+1的由来，1是我）dp[i]=max(dp[j]+1,dp[i]);maxlen=max(maxlen,dp[i]);//每次到一个新位置就更新一次}	m=maxlen;memset(b,0,sizeof(b));for(int i=n;i>0;i--)//倒着遍历一遍，找到各个数并放入b数组{if(dp[i]==m) b[m--]=a[i];for(int j=i+1;j<=n;j++){if(dp[i]==dp[j]&&a[i]>b[dp[i]+1])//如果我后边有人和我序列长度一样长，并且那个位置的数比我小，这表明我所在的序列更可能是一个更长的序列b[dp[i]]=a[i];//b中用到的dp可以直接看做序列中数的下标，这里就是更新序列的数}}for(int i=1;i<=maxlen;i++) cout<<b[i]<<" ";//输出最长递减序列cout<<endl;return 0;
}

🍩1831 简单的分数求和

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;double ans;for(int i=1;i<=n;i++) ans+=1.0/i;cout<<fixed<<setprecision(5)<<ans;return 0;
}

🍩1834 整数序列🍦

直接暴力求，会超内存，能过75%：

#include<bits/stdc++.h>
using namespace std;
int sum[10010]={0};
int main()
{sum[1]=1;for(int i=2;i<10010;i++) sum[i]=sum[i-1]+i;int n;cin>>n;vector<vector<int> > ans;int cnt=0;for(int i=n;i>=1;i--){for(int j=1;j<i;j++){if(sum[i]-sum[j-1]==n) {vector<int> a;for(int k=j;k<=i;k++) a.push_back(k);ans.push_back(a);cnt++;break;}}}if(cnt==0) {cout<<"NONE"<<endl;return 0;}for(int i=cnt-1;i>=0;i--)//这里是为了纠正输出顺序{for(int j=0;j<ans[i].size();j++) cout<<ans[i][j]<<" ";cout<<endl;}	return 0;
}

满分解法是使用二分查找：

#include<bits/stdc++.h>
using namespace std;
int main()
{int n;cin>>n;int flag=0;for(int i=1;i<=n/2;i++)// 枚举a1{ // 二分anlong long l=i+1,r=n/2+1;while(l<r){long long mid=l+r+1>>1;long long x=(i+mid)*(mid-i+1)/2;if(x<=n) l=mid;else r=mid-1;}if((i+r)*(r-i+1)/2==n){for(int j=i;j<=r;j++) cout<<j<<" ";cout<<endl;flag=1;}}if(flag==0) cout<<"NONE"<<endl;return 0;
}

🍩1833 质数的个数🍦

直接暴力会超时，过75%：

#include<bits/stdc++.h>
using namespace std;
bool prime(int x)
{if(x==0||x==1) return false;for(int i=2;i<x;i++){if(x%i==0) return false;}return true;
}int main()
{int n,ans=0;cin>>n;for(int i=1;i<=n;i++){if(prime(i)) ans++;}cout<<ans;return 0;
}

满分代码：

//摘自N诺用户：JohnWang
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e7+5;
vector<long long> prime;
bool isPrime[MAXN];void init() {for(int i = 0;i < MAXN;i++)isPrime[i] = true;for(long long i = 2;i < MAXN;i++) {if(!isPrime[i]) continue;prime.push_back(i);for(long long j = i*i;j < MAXN;j += i) //如果i,j是int型会Runtime Error isPrime[j] = false;}
}int main() {long long n, cnt = 0;cin >> n;init();for(int i = 0;i < prime.size() && prime[i] <= n;i++)cnt++;cout << cnt << endl;return 0;
}

创作不易，点个赞吧~感兴趣的宝子欢迎关注本专栏和我们一起学习机试内容哦~

宝子们学习辛苦啦，休息下，我们下部分再见！👋( •̀ ω •́ )✧ ~

大家还想看哪个学校的机试题目，评论区告诉我~~~