CF1079div2

https://codeforces.com/contest/2224/problem/AA贪心因为算是a_ia_ia_i1,所以就是从右侧开始每一个求可以得到的最大值最后看有多少个大于0就是最终的结果。也就是但是注意不要忘记加上最后一个数的结果#includebits/stdc.husingnamespacestd;constintN2e55;#definelllonglongll t;ll n;ll a[N];intmain(){ios::sync_with_stdio(0);cin.tie(0);cint;while(t--){cinn;for(inti1;in;i){cina[i];}intcnt0;for(intin-1;i1;i--){a[i]max(a[i]a[i1],a[i]);if(a[i]0)cnt;}if(a[n]0)cnt;coutcnt\n;}return0;}B数学贪心首先分析要求mex与max的求和的最大值。分析可知max求和要最大时那么最好就是把最大值放在第一个即可对于mex求和最大那么就是尽量从0开始排列连续的数mex的值应该时从0开始逐渐增长的。所以可以发现这里max增大对最终结果的影响最大只需要最大值放在第一个位置后面所有的Max就都是这个最大值了。对应的mex每次只能增加一个1。因此这里的序列取的是第一个数为最大值随后按照尽量从0开始排列例如对于0122234应该排列为4,0,1,2,3,2,2。注意相同的数前面应该放1个就可以。然后就是计算时的问题了max已经是固定的为a[n]最大值*n。只需要关注mex就可以。为了简化计算那么就最开按照把所有数从0开始排列求出最长连续的初始序列可以通过简单的数学计算求出当前的mex值—从1开始的等差数列和剩下的值。随后把最大值放到第一个位置—因为要求的序列相当于是初始序列最大值放到第一位后的结果。由于放到第一个位置导致其中的mex值出现变化那么需要减去这个变化多加的mex。这里分为两种情况1把数组最大值认为mx。如果这个mex值在初始序列的连续部分中例如初始序列为012321对应mex序列为1,2,3,444。变换后的mex序列012444也就是多加了一个mx大小为3。2如果mex不再最开始序列中例如初始序列为012353对应的mex值为123444那么多加的值也就是mex的最大值为4需要减去一个4对应代码也就是ans-min(need,mx);#includebits/stdc.husingnamespacestd;intconstN2e55;#definelllonglongll n;ll a[N];ll t;intmain(){ios::sync_with_stdio(0);cin.tie(0);cint;while(t--){cinn;for(inti1;in;i){cina[i];}sort(a1,an1);ll ans0;ll mxa[n];ll need0;for(inti1;in;i){if(a[i]need){need;}}if(need0){ansansneed*(1need)/2need*(n-need);}ans-min(need,mx);ansansmx*n;coutans\n;}return0;}C规律前缀和首先分析题目可以发现对于一个合法序列应该是任何一个 的左侧都有一个 对应并且在任何一个位置左侧 数量一定大于等于 的数量。因为左侧 多的序列只需在右侧加入 就可以把当前序列变为有效序列。但是如果左侧有多余的那么就无法通过添加变为有效序列。所以有思路了代码中就可以把 当作1当作-1这个序列是合法序列当且仅当 最后一个位置的前缀和为0。同时因为这里的有两个序列交换其实可以看做从两个括号中分别选择添加到两个已有序列后面目标就是把这两个序列最后前缀和为0。#includebits/stdc.husingnamespacestd;#definelllonglongintN2e55;intt;intmain(){ios::sync_with_stdio(0);cin.tie(0);cint;while(t--){intn;string a,b;intca0;intcb0;intf1;cinnab;for(inti0;in;i){if(a[i]b[i]){if(a[i](){ca1;cb1;}else{ca-1;cb-1;}}else{if(cacb){ca-1;cb1;}else{ca1;cb-1;}}if(ca0||cb0){f0;break;}}if(fca0cb0){coutYES\n;}else{coutNO\n;}}return0;}