山东大学机试试题合集
🍰🍰🍰高分篇已经涵盖了绝大多数的机试考点，由于临近预推免，各校的机试蜂拥而至，我们接下来先更一些各高校机试题合集，算是对前边学习成果的深入学习，也是对我们代码能力的锻炼。加油！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
{
// 二分an
long 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;
}创作不易，点个赞吧~感兴趣的宝子欢迎关注本专栏和我们一起学习机试内容哦~
宝子们学习辛苦啦，休息下，我们下部分再见！👋( •̀ ω •́ )✧ ~
大家还想看哪个学校的机试题目，评论区告诉我~~~