codeforces round #584 题解(超详细)(看完就会)

或许B话很多也能成为优点(
看完必不可能不会,如果还是不会,博主我1v1给您远程语音讲题(所以点进来吧呜呜呜

A. Paint the Numbers

先排序,然后O(n^2)除去所有数的倍数。

B. Koala and Lights

总周期=每个灯的周期的最小公倍数。而每个灯的周期是2*a[i],在a<=5的情况下,最大的可能是2,4,6,8,10的公倍数:120。
一定会在125次模拟之内变得和初始状态完全相同,所以只需要在总周期次数之内找最大值。
事实上因为n只有100,我就枚举到1000次了,一定会出答案的(逃

C. Paint the Digits

题意就是把所有的数字染成颜色1或颜色2,保证1,2序列都是递增的,且如果把1序列和2序列合并起来(1在2的前面),这个序列也是递增的。
那么1序列的最大值必须<=2序列的最小值,因为序列的每个数字都是从0~9,所以我们可以枚举这个中间值。
策略如下:
假设当前枚举到的是x,那就把全序列里所有比x小的数字染成1。
再从序列最后向前找,在找到第一个<x的数字之前,把所有=x的数字都染成1。
其它的染成2。
然后检查1,2序列是否为递增,如果符合条件就更新答案,否则不更新。
如果没有找到合法的染色方式,输出’-‘。

D. Cow and Snacks

最好的策略一定是让更多的牛尽可能吃到1个零食。我们可以把每对有一个共同爱好的牛连在一起。
先说结论:每个连通块里一定会有一头牛吃了两个,而对于这整个连通块的牛来说,一定会有一种方式能够让他们全都满意。
所以其实只需要枚举每一头牛,判断当前这头牛能不能吃到零食,如果不能吃到,就把答案++;如果能吃到,就把对应的零食删去。
对于“零食是否能吃”的判断,可以使用并查集:如果两个零食在两个不同的集合,就能吃;否则就不能吃了。

在理解上述方案的时候,有几种情况值得讨论一下

    • 对于吃了两个零食的牛,合并到同一集合就代表着吃掉了两个;
    • 对于只能吃一个零食的牛,能吃的那个零食A的祖先是自己,另一个零食的祖先属于另一个集合;
    • 这种情况比较特殊,举个例子:
      第一头牛吃A,B
      第二头牛吃C,D
      第三头牛吃B,C
      我们可以通过1,3,2的顺序使得所有牛都满意,但是在上述策略中,最后一只牛实际上没有零食可吃。这里可以发现策略依然适用:A,B并入了一个集合,C,D并入了一个集合,但是B,C依然不属于同一集合!但凡不在同一集合的零食,总会有一种策略可以让吃这两种零食的牛满足。
    • 如果两个零食都在同一集合,就不能满足了。

此处推荐一波黄学长的另一个思路:计算连通块的贡献。传送门:「CF1209X」Codeforces Round #584

QAQ小个站流量太太太小了 以后也会认真更题解的 求收藏求推荐求加友链呜呜呜

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注