round#215 div2

昨晚第一次做cf,结果做了两题就笔记本断电滚粗了。。
A Sereja and Coat Rack 水题
B Sereja and Suffixes 预处理
C Sereja and Algorithm
题意:给出长度<=1e5的字符串s(只含有xyz),给出算法:随意选三个字母长的子串,且要求它不是xzy、yxz、zyx三个中的一个,然后可以随意重排它。直到找不出这样的三字母长的子串,算法结束。对于每个样例,给出m个询问(m<=1e5):l r。问s[l……r]能否在有限步数内终结。
思路:可知如果会终结,则最后的字符串一定是以下情况中的一种:
(1)形如xzyxzy……或者yxzyxz……或者zyxzyx……
(2)只有一个字母或两个字母。
注意第(2)种情况,被坑了。。
所以预处理统计符合条件的长度为i的字符串中x、y、z各自的个数即可(三种情况),然后统计s[l……r]中x、y、z的个数
D:现在还不会。。。。。。。
E Sereja and the Arrangement of Numbers
题意:给出n(n<=2*1e6),m(m<=1e5),给出m个互异的整数。定义数列:a1、a2……an,如果任意两个数ai、aj(ai!=aj)存在pos(1<=pos<=n),a[pos]=ai,a[pos+1]=aj或者a[pos]=aj,a[pos+1]=ai,则称该数列合法。给出的m个数有各自的价值,问组成长度为n的合法数列最多能得到价值。
看了题解才知道是图论,,弱爆了。。
先求出i个不同的数组成合法序列的最小长度。然后对于n只要在这个数组(已经单调)中二分出它的位置pos,pos表示组成长度为n的合法序列最多可以用多少个不同的数。然后将给出的m个数降序排列,取前面pos个。
关键在于求出i个不同的数组成合法序列的最小长度:
方法是可以把i个不同的数看成i个点,两两之间连边形成完全图。有边表示两点相邻。问题变为求最小加多少条边可以使其变成半欧拉图。(因为如果是半欧拉图的话,就可以不重复的遍历所有边,也就是找到了一个序列满足所有相邻关系)。分奇偶讨论,偶数要加n/2-1,因为i为偶数的话,每个点的度数是奇数,最后要补成只有两个奇度点。注意序列长度=边数+1;