牛客周赛Round137总结
这次比赛比上一次有进步做对三道半、前三题就不用说了看题吧A,B,C:#includebits/stdc.h using namespace std; int main() { int n; cinn; int an/3600; int bn%3600/60; int cn%60; couta b cendl; return 0; }#includebits/stdc.h using namespace std; int main() { int t; cint; while(t--) { string str; bool flagfalse; int n; cinn; string s; cins; for(int i0;in;i) { //coutstrendl; if(s[i]as[i]z) { if(flagfalse)strs[i]; else strs[i]str; } else if(s[i]!) { if(flag)flagfalse; else flagtrue; } else { if(!str.size())continue; if(flag)str.erase(str.begin()); else str.erase(str.size()-1); } } if(str.size()0)coutEmptyendl; else coutstrendl; } return 0; }#includebits/stdc.h using namespace std; const int N2e510; int n,a[N],t; int main() { cint; while(t--) { cinn; for(int i1;in;i) { cina[i]; } sort(a1,a1n); int last1; int res1; for(int i2;in;i) { if(a[i]-a[last]res) { res; lasti; } } coutresendl; } 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这也是比较巧妙的一点看代码吧#includebits/stdc.h using namespace std; const int N5e310; typedef long long LL; LL b[N]; LL a[N]; LL f[N]; int t,n; int main() { cint; while(t--) { cinn; memset(f,1e18,sizeof f); f[0]0; for(int i1;in;i)cina[i]; for(int i1;in;i)b[i]b[i-1]^a[i]; for(int i1;in;i) { f[i]f[i-1]a[i]; LL mn1e18; for(int ji;j1;j--) { mnmin(mn,f[j-1]); f[i]min(f[i],mn(b[i]^b[j-1])); } } coutf[n]endl; } return 0; }E题这个人题也不难主要是推公式可以吧凝聚力转化为M-m-r-l根据贪心思想两个端点同时为最大值和最小值时凝聚力最大可能是ar最大al最小也可能相反所以要分类讨论当ar最大时凝聚力可以变为ar-r-(al-l),可以设新数组b[i]a[i]-i,后面的项减去前面的项的最小值就是一个res。当然那么当al最大时all-(arr),b[i]a[i]i,前面的最大值减去后面的项可以能到另一个res两个res取max就是最终的答案了看代码吧#includebits/stdc.h using namespace std; typedef long long LL; const int N2e510; int a[N]; LL b[N]; int n,t; int main() { cint; while(t--) { cinn; LL m1e18; LL res0; for(int i1;in;i) { cina[i]; b[i]a[i]-i; mmin(m,b[i]); resmax(res,b[i]-m); } m-1e18; for(int i1;in;i) { b[i]a[i]i; mmax(m,b[i]); resmax(res,m-b[i]); } coutresendl; } return 0; }至于F题就不是我能做的了希望各位大佬积极补充提建议
