首页 > 其他分享 >#0032. Educational Codeforces Round 2

#0032. Educational Codeforces Round 2

时间:2023-02-13 11:55:59浏览次数:48  
标签:Educational 颜色 color Codeforces 次数 dominating 字符串 出现 Round

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

相关文章

  • Codeforces Round #852 (Div. 2)
    A.YetAnotherPromotion题意:买土豆,一种卖a元一公斤,买m公斤送一公斤;一种卖b元一公斤。求买n公斤土豆最少花多少钱。解:完全没有思考,把a*n,b*n,买尽可能多m倍数的土豆剩......
  • Codeforces Round #851 (Div. 2)-F. XOR, Tree, and Queries-树、异或、并查集
    题目:https://codeforces.com/contest/1788/problem/F题解:(首先他和线性基没什么瓜系)想这个问题大概可以分成几个部分:1、很自然地考虑记\(p_x\)表示从根节点走到x路径......
  • Codeforces Round #851 (Div. 2) D
    链接:https://codeforces.com/contest/1788/problem/D题意:数轴上有n个点,每个点会以相同的v向最近的点移动(若左右距离相等则向左),两点相遇则暂停,问最终数轴上剩下的点数即为......
  • Codeforces Round #547 (Div. 3) F2. Same Sum Blocks (贪心——最多不重叠区间数量
    题目https://codeforces.com/problemset/problem/1141/F2题意忽略;给出一个数组,求和相等的,不重叠子串的最大数量,并输出(题目有点绕)思路先求出数组前缀和,然后找出......
  • Codeforces Round #851 (Div. 2) A-E
    比赛链接A题意给一串只包含\(1,2\)的数,找到最小的\(k\)使得\(\prod_{i=1}^ka_i=\prod_{i=k+1}^na_i\)。题解知识点:枚举。因为只有\(1,2\),所以考虑左右两......
  • Codeforces Round #541 (Div. 2) D - Gourmet choice 差分约束
    观察到n+m最多才2000个点,正解也不是差分约束但是它能跑:)建图比较平凡不记述难得的是用链式前向星T了,改vector过了  T9的话是加了随机化优化,cin读入,链式前向星存边......
  • Codeforces Round #851 (Div. 2)
    A.OneandTwo比较两边\(2\)的个数即可。#include<bits/stdc++.h>usingnamespacestd;intn,T,prefix[1111],suffix[1111],ans,a[1111];intmain(){sc......
  • Codeforces Round #472 D - Riverside Curio 差分约束
    正解据说是贪心+dp可惜我这个人没什么脑子:)(遇到了能用差分约束也能用dp+贪心的第二题了,真是神奇假设有一组合法的sum就能逆推出di,因为ai+di+1=sumi最小化Σdi就是最小......
  • 2.10 Codeforces Round #851 (Div. 2)
    A-OneandTwo题意给出长度为n的序列a,a中元素是1或2找到一个k使a1*a2*a3*....*ak=ak+1*ak+2*ak+3*...*an思路统计序列中有多少个2,若是奇数个2,则......
  • Codeforces Round #851 (Div. 2) 题解
    CodeforcesRound#851(Div.2)题解A.OneandTwo取\(\log_2\),变成加号,前缀和枚举\(s[i]=\dfrac{s[n]}{2}\)。B.SumofTwoNumbers对于每一位,如果是偶数则平均......