600A
简单题 但有个坑点在于会有空字符串
600B
一道可以用来实验upper_bound的题
600C
挺有趣的一道题。首先考虑怎样的字符串可以通过permutation变成palindrome:条件是至多一个数字出现奇数次。最快的减少出现奇数次数量的数字的方法就是每次找出出现奇数次的两个数a和b,把其中一个改成另外一个数的值,这样a和b的出现次数一加一减,就都变成偶数了。接着再考虑怎么字典序最小。首先关注到如果字符串里的数本来就偏小那么字典序肯定也会更小。因此我们每次选最大和最小的出现奇数次的数,然后把大的改成小的。确定了留下的数字,就直接把一半的数从小到大排序然后再reverse就可以得到palindrome。当然如果字符串长度为奇数中间还会有一个落单的数字。有一个小坑点在于如果最后只剩下一个出现奇数词的数,记得只留下一个放中间,剩余的还是放在左右(我一开始写的时候就把那个数字全放中间了查了很久才发现不对)
D
跳过)
600E
dsu on tree。对于每个点存dominating color的和以及他们出现的次数,以及一个存所有颜色出现数量的map。merge的时候主要就是merge map,把node a向node b合并时一旦有颜色的出现次数正好等于b中dominating color的出现次数,那么证明这个是一个新的dominating color(因为这个color的次数由a和b两边的次数相加得到,次数是正的,所以它在b子树里的时候一定不是dominating color)。如果出现次数超过了b中dominating color的出现次数,那么重新更新dominating color。
600F
大胆猜想最少需要的颜色数量是每个点的degree的最大值。考虑每条边 (u,v),如果u和v最小可以选的颜色是一样的,那直接染那个颜色。如果不一样,设这两个颜色分别为U和V,那么我们先把这个边染成U,接着再把连着v的另一条颜色为U的边改成V,如果还有冲突就继续改,即一直改一条UVUVUV...的链直到不再有冲突。根据二分图不存在奇环的性质,这样一直改下去是不会出现死循环的。
标签:Educational,颜色,color,Codeforces,次数,dominating,字符串,出现,Round From: https://www.cnblogs.com/myrcella/p/17115820.html