小红书2020校招测试开发后端笔试题卷三

 //完全背包求组合数

#include <iostream>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
int value[300];
// vector<int>vis;
// vector<int>vis1;
map<vector<int>,int>mp;
// set<vector<int>>se;
int num=0;
int res=0;
int a[1000];int dp[50000];
int main() {int n;scanf("%d",&n);getchar();char c=getchar();while(c!=']'){scanf("%d",&value[num++]);c=getchar();}dp[0]=1;//求组和，完全背包for(int i=0;i<num;i++){for(int j=value[i];j<=n;j++){dp[j]+=dp[j-value[i]];}}printf("%d\n",dp[n]);return 0;}
// 64 位输出请用 printf("%lld")

 

#include <iostream>
#include<stack>
using namespace std;
string res;
stack<char>kuo;
int main() {string s;cin>>s;int id=0;for(int i=0;i<s.length();i++){if(s[i]=='('){kuo.push('(');id=1;}else if(s[i]==')'){kuo.pop();}// if(id==1)// {//     while(s[i]!=')'){//         i++;//     }//     id=0;// }else if(kuo.empty()){if(s[i]!='<'){res.push_back(s[i]);}else{if(res.size()>0){res.pop_back();}}}}cout<<res<<endl;return 0;}
// 64 位输出请用 printf("%lld")

 

#include <iostream>
using namespace std;
int dp[1005];
int num[1005];
int a[1005];
int main() {//dp[i]表示从前i篇笔记获得的最大点赞数int n;scanf("%d",&n);dp[0]=0;for(int i=0;i<n;i++){scanf("%d",&a[i]);}dp[0]=a[0];num[0]=1;for(int i=1;i<n;i++){dp[i]=max(dp[i-1],dp[i-2]+a[i]);//如果不选第i个if(dp[i-2]+a[i]>dp[i-1])num[i]=num[i-2]+1;else if(dp[i-2]+a[i]==dp[i-1]){num[i]=min(num[i-1],num[i-2]+1);}else{num[i]=num[i-1];}}int max_value=dp[n-1];printf("%d %d\n",dp[n-1],num[n-1]);return 0;
}
// 64 位输出请用 printf("%lld")

题解：贪心维护第一个值的升序，然后对第二个值用LIS(二分+dp),不然会爆，注意第一个值>=,第二个值要严格递增，要不然过不了

#include <iostream>
#include<queue>
#include<string.h>
#include<algorithm>
using namespace std;
struct Node{int x;int h;
}node[1000004];bool cmp(Node a,Node b)
{if(a.x<b.x ){return true;}else if(a.x==b.x){return a.h<=b.h;}else{return  false;}}
int dp[1000005];int binary_search(int r,int val)
{int l=1;while(l<=r){int mid=(l+r)/2;if(dp[mid]<val){l=mid+1;}else{r=mid-1;}}return l;
}
int main() {int N;scanf("%d",&N);for(int i=0;i<N;i++){scanf("%d%d",&node[i].x,&node[i].h);}sort(node,node+N,cmp);int res=1;memset(dp,0x3f3f3f3f,sizeof(dp));dp[1]=node[0].h;for(int i=1;i<N;i++){if(node[i].h>dp[res]){dp[++res]=node[i].h;}else{dp[binary_search(res,node[i].h)]=node[i].h;}// printf("%d %d\n",node[i].x,node[i].h);}printf("%d\n",res);return 0;}
// 64 位输出请用 printf("%lld")