跟谁学09.23笔试

一个小时五道编程题目做哭了，一脸懵逼；

1.给定n个区间，求不重复的区间长度；(这个没做出来)

2.输出严格单调递增的子序列长度 ac:46%

#include <iostream>
#include <vector>
using namespace std;
vector <int> compute1(vector<int> &a);
vector <int> compute2(vector<int> &ab,vector<int> &dp);
int main()
{
int len,index;
vector <int> arr;
cin>>len;
arr.resize(len);
for(int i=0;i<len;i++)
cin>>arr[i];
vector <int> d=compute1(arr);
vector <int> res=compute2(arr,d);
for(int i=0;i<res.size();i++)
cout<<res[i]<<" ";
return 0;
}
vector <int> compute1(vector<int> &a){
int n=(int)a.size();
vector <int> dp(n,0);
for(int i=0;i<n;i++){
dp[i]=1;
for(int j=0;j<i;j++){
if(a[j]<a[i]){
dp[i]=max(dp[j]+1,dp[i]);
}
}
}
return dp;
}
vector <int> compute2(vector<int> &b,vector<int> &dp){
int len=0;
int index=0;
for(int i=0;i<dp.size();i++){
if(dp[i]>len){
len=dp[i];
index=i;
}
}
vector <int> l(len,0);
l[--len]=b[index];
for(int i=index;i>=0;i--){
if(b[i]<b[index]&&dp[i]==dp[index]-1){
l[--len]=b[i];
index=i;
}
}
//cout<<l[2];
return l;

}
3. 数组中位数，很简单 ac：1

4.一个偶数分解成两个素数的和，求这两个素数相差最大时的素数，结果从小到大输出 ac：1

#include <iostream>
int sushu(int num){
int flag=1;
for(int i=2;i<=num/2;i++)
if(num%i==0){
flag=0;
break;
}
return flag;
}
using namespace std;

int main()
{
int num;
int max_=-100000;
int i,l,r;
cin>>num;
//cout<<sushu(3);
if(num<4)
cout<<"不存在两个素数的和等于"<<num;
else{
for(int i=2;i<=num;i++)
if(sushu(i)&&sushu(num-i)&&max_<num-i-i){
max_=num-i-i;
l=i;
r=num-i;
}
cout<<l<<" "<<num-l;
}

return 0;
}