https://codeforces.com/contest/2224/problem/A

A

贪心
因为算是a_i=a_i+a_i+1,所以就是从右侧开始，每一个求可以得到的最大值，最后看有多少个大于0就是最终的结果。
也就是
但是注意不要忘记加上最后一个数的结果

#include<bits/stdc++.h>usingnamespacestd;constintN=2e5+5;#definelllonglongll t;ll n;ll a[N];intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>t;while(t--){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}intcnt=0;for(inti=n-1;i>=1;i--){a[i]=max(a[i]+a[i+1],a[i]);if(a[i]>0)cnt++;}if(a[n]>0)cnt++;cout<<cnt<<"\n";}return0;}

B

数学，贪心
首先分析要求mex与max的求和的最大值。
分析可知max求和要最大时，那么最好就是把最大值放在第一个即可；对于mex求和最大，那么就是尽量从0开始排列连续的数，mex的值应该时从0开始逐渐增长的。
所以可以发现这里max增大对最终结果的影响最大，只需要最大值放在第一个位置，后面所有的Max就都是这个最大值了。对应的mex每次只能增加一个1。因此这里的序列取的是，第一个数为最大值，随后按照尽量从0开始排列，例如对于0，1，2，2，2，3，4应该排列为4,0,1,2,3,2,2。注意相同的数前面应该放1个就可以。
然后就是计算时的问题了，max已经是固定的，为a[n]最大值*n。只需要关注mex就可以。为了简化计算，那么就最开按照把所有数从0开始排列，求出最长连续的初始序列，可以通过简单的数学计算求出当前的mex值—从1开始的等差数列和剩下的值。
随后把最大值放到第一个位置—因为要求的序列相当于是初始序列最大值放到第一位后的结果。由于放到第一个位置，导致其中的mex值出现变化，那么需要减去这个变化多加的mex。这里分为两种情况：1，把数组最大值认为mx。如果这个mex值在初始序列的连续部分中，例如初始序列为0，1，2，3，2，1对应mex序列为1,2,3,4，4，4。变换后的mex序列0，1，2，4，4，4，也就是多加了一个mx大小为3。2，如果mex不再最开始序列中，例如初始序列为0，1，2，3，5，3，对应的mex值为1，2，3，4，4，4，那么多加的值也就是mex的最大值为4，需要减去一个4，对应代码也就是ans-=min(need,mx);

#include<bits/stdc++.h>usingnamespacestd;intconstN=2e5+5;#definelllonglongll n;ll a[N];ll t;intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>t;while(t--){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}sort(a+1,a+n+1);ll ans=0;ll mx=a[n];ll need=0;for(inti=1;i<=n;i++){if(a[i]==need){need++;}}if(need>0){ans=ans+need*(1+need)/2+need*(n-need);}ans-=min(need,mx);ans=ans+mx*n;cout<<ans<<"\n";}return0;}

C

规律，前缀和
首先分析题目，可以发现：对于一个合法序列，应该是任何一个 ）的左侧都有一个 （ 对应，并且在任何一个位置，左侧（ 数量一定大于等于 ）的数量。因为左侧 （ 多的序列，只需在右侧加入 ）就可以把当前序列变为有效序列。但是如果左侧有多余的）那么就无法通过添加变为有效序列。
所以有思路了，代码中就可以把（ 当作1，）当作-1，这个序列是合法序列当且仅当 最后一个位置的前缀和为0。
同时因为这里的有两个序列交换，其实可以看做从两个括号中分别选择，添加到两个已有序列后面，目标就是把这两个序列最后前缀和为0。

#include<bits/stdc++.h>usingnamespacestd;#definelllonglongintN=2e5+5;intt;intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>t;while(t--){intn;string a,b;intca=0;intcb=0;intf=1;cin>>n>>a>>b;for(inti=0;i<n;i++){if(a[i]==b[i]){if(a[i]=='('){ca+=1;cb+=1;}else{ca-=1;cb-=1;}}else{if(ca>cb){ca-=1;cb+=1;}else{ca+=1;cb-=1;}}if(ca<0||cb<0){f=0;break;}}if(f&&ca==0&&cb==0){cout<<"YES\n";}else{cout<<"NO\n";}}return0;}