牛客周赛Round137总结

这次比赛比上一次有进步，做对三道半、

前三题就不用说了

看题吧

A,B,C:

#include<bits/stdc++.h> using namespace std; int main() { int n; cin>>n; int a=n/3600; int b=n%3600/60; int c=n%60; cout<<a<<' '<<b<<' '<<c<<endl; return 0; }

#include<bits/stdc++.h> using namespace std; int main() { int t; cin>>t; while(t--) { string str=""; bool flag=false; int n; cin>>n; string s; cin>>s; for(int i=0;i<n;i++) { //cout<<str<<endl; if(s[i]>='a'&&s[i]<='z') { if(flag==false)str+=s[i]; else str=s[i]+str; } else if(s[i]=='!') { if(flag)flag=false; else flag=true; } else { if(!str.size())continue; if(flag)str.erase(str.begin()); else str.erase(str.size()-1); } } if(str.size()==0)cout<<"Empty"<<endl; else cout<<str<<endl; } return 0; }

#include<bits/stdc++.h> using namespace std; const int N=2e5+10; int n,a[N],t; int main() { cin>>t; while(t--) { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]; } sort(a+1,a+1+n); int last=1; int res=1; for(int i=2;i<=n;i++) { if(a[i]-a[last]>=res) { res++; last=i; } } cout<<res<<endl; } return 0; }

好的，现在咱们重点看看D题吧：

这个题我当时只是暴力骗了一些分（一个点。。）：

首先要明白一点，这个是可用前缀和的（我也不知道为什么，反正试了一下就是能用），

然后我们就可以用dp来解这个题，f[i]表示要把1~i都涂成红色需要的最少代价

我们首先遍历i,表示右端点，j表示左端点，可以得到状态转移方程：f[i]=min(f[i],f[j-1]+s[i]^s[j-1]);

你是不是以为这样就可以了？大错特错！！

要注意的是，同一片区域是可以反复被涂的，所以，j要反着遍历，在遍历过程中所谓的f[j-1]都要取最小值，记为m，这也是比较巧妙的一点，看代码吧：

#include<bits/stdc++.h> using namespace std; const int N=5e3+10; typedef long long LL; LL b[N]; LL a[N]; LL f[N]; int t,n; int main() { cin>>t; while(t--) { cin>>n; memset(f,1e18,sizeof f); f[0]=0; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1;i<=n;i++)b[i]=b[i-1]^a[i]; for(int i=1;i<=n;i++) { f[i]=f[i-1]+a[i]; LL mn=1e18; for(int j=i;j>=1;j--) { mn=min(mn,f[j-1]); f[i]=min(f[i],mn+(b[i]^b[j-1])); } } cout<<f[n]<<endl; } return 0; }

E题：

这个人题也不难，主要是推公式，可以吧凝聚力转化为：M-m-（r-l）根据贪心思想，两个端点同时为最大值和最小值时凝聚力最大，可能是ar最大，al最小，也可能相反，所以要分类讨论：

当ar最大时，凝聚力可以变为：ar-r-(al-l),可以设新数组b[i]=a[i]-i,后面的项减去前面的项的最小值，就是一个res。

当然，那么当al最大时，al+l-(ar+r),b[i]=a[i]+i,前面的最大值减去后面的项，可以能到另一个res，两个res取max就是最终的答案了，看代码吧：

#include<bits/stdc++.h> using namespace std; typedef long long LL; const int N=2e5+10; int a[N]; LL b[N]; int n,t; int main() { cin>>t; while(t--) { cin>>n; LL m=1e18; LL res=0; for(int i=1;i<=n;i++) { cin>>a[i]; b[i]=a[i]-i; m=min(m,b[i]); res=max(res,b[i]-m); } m=-1e18; for(int i=1;i<=n;i++) { b[i]=a[i]+i; m=max(m,b[i]); res=max(res,m-b[i]); } cout<<res<<endl; } return 0; }

至于F题就不是我能做的了，希望各位大佬积极补充，提建议