校内场-提高组 ZYZSC-S-Round 2官方题解付费观看A 降水rain原题链接D - Rain Flows into Dams分析场切了。但是最后一个样例那个样子不是显然的A t C o d e r AtCoderAtCoder风格吗正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN100005;intn;inta[N];intsum;signedmain(){// freopen(rain.in, r, stdin);// freopen(rain.out, w, stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;intsum00,sum10;for(inti1;in;i){cina[i];suma[i];a[i]a[i]*2;if(i%20){sum0a[i];}else{sum1a[i];}}for(inti1;in;i){if(i%20){coutsum0-sum ;sum0-a[i];sum1a[i];}else{coutsum1-sum ;sum1-a[i];sum0a[i];}}}B 括号序列bracket原题链接B 括号序列bracket分析这个真没盒到原。不过我大概花了不到一个小时就写出来了吧……就是你观察到只有合法的序列可以进行操作所以你可以判到-1的分。然后你维护一个每个位置前面(和)的个数减一下取个max \maxmax然后拿总长度减去max × 2 \max\times2max×2就行了。因为你已经保证了序列合法。正解#includebits/stdc.husingnamespacestd;constintN3000005;string s;intn;boolvis[20];intpre_up[N],pre_down[N];intsuf_up[N],suf_down[N];inttot0,tot1;voidinit(){for(inti0;in;i){if(s[i](){tot0;pre_up[i]pre_up[max(i-1,0)]1;pre_down[i]pre_down[max(i-1,0)];}if(s[i])){tot1;pre_up[i]pre_up[max(i-1,0)];pre_down[i]pre_down[max(i-1,0)]1;}}}boolcheck1(string t){stackintstk;for(inti0;i(int)t.length();i){if(t[i](){stk.push(i);}if(t[i])){if(stk.empty())returnfalse;stk.pop();}}if(stk.empty())returntrue;returnfalse;}boolcheck2(string t){intmt.length();if(!check1(t))returnfalse;for(inti0,jm-1;ij;i,j--){if(t[i]!(||t[j]!)){returnfalse;}}returntrue;}intans;voiddfs(intp){if(pn){string tmp1,tmp2;intcnt0;for(inti0;in;i){if(vis[i]true){// not keeptmp1s[i];}else{// keeptmp2s[i];cnt;}}if(check1(tmp1)check2(tmp2)){ansmax(ans,cnt);}return;}vis[p]true;dfs(p1);vis[p]false;dfs(p1);}signedmain(){freopen(bracket.in,r,stdin);freopen(bracket.out,w,stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cins;ns.length();if(!check1(s)){cout-1;return0;}if(n16){//(((())(()))(()))dfs(1);coutn-ans;return0;}// vectorint up, down;// for (int i 0, cnt0 0, cnt1 0; i n; i){// if (s[i] (){// if (cnt1 ! 0){// down.push_back(cnt1);// cnt1 0;// }// cnt0;// }// if (s[i] )){// if (cnt0 ! 0){// up.push_back(cnt0);// cnt0 0;// }// cnt1;// }// }init();intmx0;for(inti0;in;i){mxmax(pre_up[i]-pre_down[i],mx);}coutn-mx*2;}打完前两个出去跑操了因为坐着也没事干跑了跑步把后两题的暴力想了一下。C 树tree原题链接D. Tree Elimination分析*2900某教练竟然评蓝还有人类吗感觉lz要成为 胖头鱼 了然后菊花是简单的不过没有什么启发性。然后链的问题在于我看出来了一个从前面两个转的DP然后没有看出来斐波那契数列不过击球手上物理课之前提醒我了。感觉之前的代码交上去也有分不知道。然后链给予了我们丰富的思考我们的DP似乎终于有用了。我还是有一定实力的因为我看到了这个DP状态的一部分但是在一颗标准的树上这个还是困难的少了一些东西。D 冒泡排序二合一sort原题链接冒泡排序二合一sort分析没有盒到原我也不是很想补不如去学个分块之类的东西争取下次序列问题多拿一点。
校内场-提高组 ZYZSC-S-Round 2官方题解付费观看A 降水rain原题链接D - Rain Flows into Dams分析场切了。但是最后一个样例那个样子不是显然的A t C o d e r AtCoderAtCoder风格吗正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN100005;intn;inta[N];intsum;signedmain(){// freopen(rain.in, r, stdin);// freopen(rain.out, w, stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;intsum00,sum10;for(inti1;in;i){cina[i];suma[i];a[i]a[i]*2;if(i%20){sum0a[i];}else{sum1a[i];}}for(inti1;in;i){if(i%20){coutsum0-sum ;sum0-a[i];sum1a[i];}else{coutsum1-sum ;sum1-a[i];sum0a[i];}}}B 括号序列bracket原题链接B 括号序列bracket分析这个真没盒到原。不过我大概花了不到一个小时就写出来了吧……就是你观察到只有合法的序列可以进行操作所以你可以判到-1的分。然后你维护一个每个位置前面(和)的个数减一下取个max \maxmax然后拿总长度减去max × 2 \max\times2max×2就行了。因为你已经保证了序列合法。正解#includebits/stdc.husingnamespacestd;constintN3000005;string s;intn;boolvis[20];intpre_up[N],pre_down[N];intsuf_up[N],suf_down[N];inttot0,tot1;voidinit(){for(inti0;in;i){if(s[i](){tot0;pre_up[i]pre_up[max(i-1,0)]1;pre_down[i]pre_down[max(i-1,0)];}if(s[i])){tot1;pre_up[i]pre_up[max(i-1,0)];pre_down[i]pre_down[max(i-1,0)]1;}}}boolcheck1(string t){stackintstk;for(inti0;i(int)t.length();i){if(t[i](){stk.push(i);}if(t[i])){if(stk.empty())returnfalse;stk.pop();}}if(stk.empty())returntrue;returnfalse;}boolcheck2(string t){intmt.length();if(!check1(t))returnfalse;for(inti0,jm-1;ij;i,j--){if(t[i]!(||t[j]!)){returnfalse;}}returntrue;}intans;voiddfs(intp){if(pn){string tmp1,tmp2;intcnt0;for(inti0;in;i){if(vis[i]true){// not keeptmp1s[i];}else{// keeptmp2s[i];cnt;}}if(check1(tmp1)check2(tmp2)){ansmax(ans,cnt);}return;}vis[p]true;dfs(p1);vis[p]false;dfs(p1);}signedmain(){freopen(bracket.in,r,stdin);freopen(bracket.out,w,stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cins;ns.length();if(!check1(s)){cout-1;return0;}if(n16){//(((())(()))(()))dfs(1);coutn-ans;return0;}// vectorint up, down;// for (int i 0, cnt0 0, cnt1 0; i n; i){// if (s[i] (){// if (cnt1 ! 0){// down.push_back(cnt1);// cnt1 0;// }// cnt0;// }// if (s[i] )){// if (cnt0 ! 0){// up.push_back(cnt0);// cnt0 0;// }// cnt1;// }// }init();intmx0;for(inti0;in;i){mxmax(pre_up[i]-pre_down[i],mx);}coutn-mx*2;}打完前两个出去跑操了因为坐着也没事干跑了跑步把后两题的暴力想了一下。C 树tree原题链接D. Tree Elimination分析*2900某教练竟然评蓝还有人类吗感觉lz要成为 胖头鱼 了然后菊花是简单的不过没有什么启发性。然后链的问题在于我看出来了一个从前面两个转的DP然后没有看出来斐波那契数列不过击球手上物理课之前提醒我了。感觉之前的代码交上去也有分不知道。然后链给予了我们丰富的思考我们的DP似乎终于有用了。我还是有一定实力的因为我看到了这个DP状态的一部分但是在一颗标准的树上这个还是困难的少了一些东西。D 冒泡排序二合一sort原题链接冒泡排序二合一sort分析没有盒到原我也不是很想补不如去学个分块之类的东西争取下次序列问题多拿一点。
