蒟蒻的Codeforces Round #379 (Div. 2)颓废记

vp了一场,中间被队友叫去填表格耽误了一些时间,E没时间想了,后来看看题解自己推了推感觉还有可能拯救一下?

A. Anton and Danik(模拟)

B. Anton and Digits(模拟)

C. Anton and Making Potions(二分+贪心)

看了半天的题面才明白在说啥。。。枚举第一种操作的选择(可能不需要第一种操作,所以加一个花费为0的来代替),同时因为第二种操作,可以把一些药水直接做好,而且相关的c,d数组都是非递减的。我们肯定贪心的选择转换最多的且满足花费限制的。这个可以二分找到,因为满足限制的花费最多的操作肯定满足转换的最多。

D. Anton and Chess(模拟)

忘记开long long wa了一次。因为棋子是无法跳过障碍的格子攻击国王的。所以我们就维护国王八个方向离它最近的棋子的相关属性。最后check一下就好了。

E. Anton and Tree(缩点+树的直径)

首先缩点后,我们可以得到一棵黑白相间的树(黑色节点相连的一定是白色节点,白色同理)。然后我们求出树的直径dis,然后取直径中点的染色(dis+1)/2即可。我们可以这样想,如果直径上的节点数是奇数,那么你每次染色,可以让直径上的有两个点变的同色。如果偶数的话,最后一次只让一个节点变得同色,但还是那个公式。。。而又因为是直径,所以直径上挂的枝叶也会跟着变的同色,而且不会超过直径的染色次数,否则就不是直径了。觉得抽象,画个图模拟一下就好了。

我是用并查集缩点,然后两次dfs求直径。。写的有点丑。复杂度是O(n),但可能常数较大。。。

F. Anton and School(数学)

F题考察出了我上学期数字逻辑没怎么学好(废话只考了75) ,clearY一眼秒了。我还是看了题解才发现这个性质: .感觉就是个加法器的实现啊。

然后设,那么.我们把所有的求和得到:

那么,那么每一个都可以算出来了。现在我们只需要检验我们计算出的是否合法即可,其实我们不需要n^2检验,而是可以直接按位检验。因为如果当前数,那么在二进制下的为1的位置一定是中为1的位置。至于这个位置上有几个1我们可以预处理出来。的处理同理。那么这样的话复杂度O(nlog(1e9))。

总结:A,B煞笔题,C题一开始想错了一个贪心的地方,好在后来想明白了。D题因为C题一直WA有点慌了,细节没处理好(比如long long)。E题在补的时候也有一点问题,就是重新建图的时候一开始连边错了,居然还过了样例。F题其实如果长成这样大家都可以看出来了吧:.

发表评论

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