m113

2019-11-13 来源: hzoi_lsc 发布在  https://www.cnblogs.com/hzoi-lsc/p/11850895.html

今天的比赛很有感触,所以来写一下题解:

T1可以发现一些规律是:面积扩大的速度显然比周长扩大的速度快,然后就可以枚举周长来看能为成的面积,其实最优的情况一定是六边型的情况,通过手膜我们可以发现对于边长是c的六边型,每增加一个周长,也就是增加6次就会变成c+1的六边型,这其中的六次增加每次所围成的面积的增加量分别是c-1,c,c,c,c,c+1,具体的画一下图就可以看出来了!

然而考试的时候我并没有画图,我来大概的说一下考试的思路,其实如果不想看可以直接看下一道T2,可以自动跳过,反正也不是啥正解,而且WA了

考试的时候我就想一定是六边型的情况是最优的,但是我是枚举中间的最长的那个的长度,然后就会发现这其中就是一个多峰函数(注意不严谨,打表发现会出现断崖式下降的情况,反正对拍的时候三分锅了!)然后我就通过找到最优的中间值来求解这个问题,但是我少考虑了一种极其sb的情况就是n==3的时候,会发现,我只会构造类6边形的的图形,所以锅了(此时发现$n==3$锅了的时候是距考试结束还有4分钟的时候,心态已经没了!)

正解就是上面说的,我的代码打的比较鬼畜!

T2 其实自己觉得挺大神的,大佬勿喷!

T2我们把它建出来边就会发现他是一棵内向基环树:就是这样的一棵树

然而在题目的部分测试环境中,会因为其中有不优的边而变成一棵数,那么我们想一下一个点会不会被取的情况:其实对于一棵树来说我们都可以取到,(注意又是不严格的,准确的说是除了叶子节点都能取到)因为要取他只会取他的父亲,但是他本身的数量并不改变,对于树的情况就直接硬搞就可以了(然而我太弱了,考试的时候硬搞都写错了!)

那么对于一棵基环树我们应该咋办能!套路式的断掉一条环上的边,那么我们究竟断哪条边呢?

我们可以对于一棵基环树如果环上的边小于树上的边,那么这个边一定不优,就可以断掉这条边,从而变成一棵树,然后就可以硬搞了,

对于没有这种情况的,就要找环上的边与树上的边的权值差最小的边,然后干掉他!

这样做显然是对的!

至于实现,我们不妨维护每一个点的最大的和次大的儿子,然后直接dfs,就这样就可以了;维护最大和次大的思路还是没有想到!

T3 鸽鸽鸽咕咕咕!

相关文章