A题
题意比较难懂，其实就是查一下他给的k个哪些不是学校的最大值
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e5+10; struct node{ int x,id; bool operator <(const node &t) const{ return x<t.x; } }s[N]; vector<int> num; int mx[N]; int main(){ int n,m,k; cin>>n>>m>>k; int i; for(i=1;i<=n;i++){ cin>>s[i].x; } for(i=1;i<=n;i++){ cin>>s[i].id; mx[s[i].id]=max(mx[s[i].id],s[i].x); } int cnt=0; for(i=1;i<=k;i++){ int x; cin>>x; if(mx[s[x].id]!=s[x].x){ cnt++; } } cout<<cnt<<endl; }
B题
这题我做的时候写了个高复杂度的算法，就是先枚举二维再找
但是其实观察到题目性质，本题每个数都不相同，因此直接桶维护两和，直接对两和出现最多的取max
这是因为每个数都不同，所以加起来相同的两数，一定都是不同的
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=2e5+10; int a[N]; int s[N]; int main(){ ios::sync_with_stdio(false); int n; cin>>n; int i,j; for(i=1;i<=n;i++){ cin>>a[i]; s[a[i]]++; } sort(a+1,a+1+n); int ans=0; for(i=1;i<=n;i++){ for(j=i+1;j<=n;j++){ int cnt=0; int x=a[i]+a[j]; cnt=2; int l=i+1; for(int k=l;k<j;k++){ if(x-a[k]<0) continue; if(a[k]&&s[x-a[k]]) cnt++; } ans=max(ans,cnt/2); } } cout<<ans<<endl; }
C题
这题是一道模拟题，我采用的是方法就是枚举时间点，然后观察所有队列里面的情况，如果已经结束，那么放新的进去，注意判断k>n以及所有的都已经放进去的情况
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e5+10; int a[N]; int id[N]; int s[N],vis[N]; int main(){ ios::sync_with_stdio(false); int n,k; cin>>n>>k; int i; for(i=1;i<=n;i++){ cin>>a[i]; } int cnt=0; int pos=0; for(i=1;i<=k&&i<=n;i++){ s[i]=a[i]; id[i]=i; } pos=i; int ans=0; for(int tim=1;tim<=150000;tim++){ if(cnt==n) break; for(i=1;i<=k&&i<=n;i++){ if(s[i]<=0) continue; int x=(int)(1.0*cnt/n*100+0.50); //cout<<x<<" "<<a[id[i]]-s[i]+1<<endl; if(x==a[id[i]]-s[i]+1){ if(!vis[id[i]]){ vis[id[i]]=1; ans++; } } } for(i=1;i<=k&&i<=n;i++){ s[i]--; if(s[i]==0){ cnt++; if(pos<=n){ id[i]=pos; s[i]=a[pos]; pos++; } } } } cout<<ans<<endl; }
D题
这道题我思考的想法和正解的思路是一样的，我们只要找到一个合法区间，那么就能先删完前面，再删中间，看看总共是否符合情况
但是我忘了一点，虽然暴力是n^2的，但是显然随着左端点的变化，右端点一定至少不会后退，因此使用双指针算法，其实就是线性复杂度，没必要右端点也重来
之后就是用一个桶维护信息比较，注意有个问题，我写的时候又没考虑到，因为s<k，所以会产生，我们枚举的区间不到k长度就已经完成任务，此时只要删前面就行了。
我写的时候遗漏了这个情况，会wa12，因为按照我这种写法，当满足条件的时候，右指针不会再向右移，因此我无法做到把小区间扩展成合法的大区间，其实只要与0取个max即可
关键细节看代码
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=5e5+10; int n,m,k,s; int a[N],b[N]; int sum[N]; int d[N]; int tmp[N]; vector<int> num; int main(){ ios::sync_with_stdio(false); cin>>m>>k>>n>>s; int i,j; for(i=1;i<=m;i++){ cin>>a[i]; } int cnt=0; for(i=1;i<=s;i++){ cin>>b[i]; if(++d[b[i]]==1){ cnt++; } } int r=0; int now=0; for(i=1;i<=m;i++){ while(r<m&&now<cnt){ r++; sum[a[r]]++; if(sum[a[r]]==d[a[r]]){//满足要求的多了一个 now++; } } if(now==cnt){ int l=(i-1)%k; if(((i-1)/k+(m-r)/k)>=(n-1)){ cout<<l+max((r-i+1-k),0)<<endl; int sign=max((r-i+1-k),0); for(j=1;j<=l;j++){ cout<<j<<" "; } for(int x=i;x<=r&&sign;x++){ if(sum[a[x]]>d[a[x]]){ --sum[a[x]]; sign--; cout<<x<<" "; } } return 0; } } if(--sum[a[i]]==d[a[i]]-1) now--; } cout<<-1<<endl; return 0; }
E题
带补
F题
套路题，维护lcs来分两种情况讨论dp更新状态
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e5+10; string s; int f[5050]; int lcs[5050][5050]; int main(){ ios::sync_with_stdio(false); int n,a,b; cin>>n>>a>>b; cin>>s; s=" "+s; for(int i=1;i<=n;++i){ f[i]=f[i-1]+a; for(int j=1;j<i;j++){ if(s[i]==s[j]) lcs[i][j]=lcs[i-1][j-1]+1; if(lcs[i][j]!=0&&i-j>=lcs[i][j]) f[i]=min(f[i],f[i-lcs[i][j]]+b); } } cout<<f[n]<<endl; }