• BZOJ 4089:[Sdoi2015]graft(SDOI 2015 Round 2 Day 2)

    BZOJ 4089:[Sdoi2015]graft(SDOI 2015 Round 2 Day 2)

    别人家的神选系列,我只会做这道题QAQ题目描述:给定一颗树,加上k条边,将n个点染色,相邻两点不同,记颜色为i的又ti个,求$$\frac{\sum_{i=1}^{n}\frac{ti}{i}}{1+p\sum_{i=1}^{n}iti}$$(擦擦擦我今天才知道能用Tex公式QAQ害得我以前写的好辛苦QAQ)的最大值。(k<=2)这是分数规划嘛,那么我们就可以二分答案x。然后我们每种颜色的值就变为$\frac{1}{i}-pxi$啦,然后就可以直接上DP啦。dp我们每个点记录3个值:...

    02015年6月18日830二分,树形动规,老的存档
  • SDOI Day2

    SDOI Day2

    今天做了SDOI Day2觉得自己萌萌哒==题目真的有点水,一点编程复杂度都没有T1:星际战争描述:http://www.lydsy.com/JudgeOnline/problem.php?id=3993这道题是这两天最容易的题了吧。。可以发现这是一个二分图,考虑二分答案,那么人们在这段时间的输出伤害就能够确定了,用最大流判断是否所有的机器人护甲值都为0,即可。数据较良心跑得飞快Code:[crayon-5bc75de8551a0067782706/]ViewCode T2:约数个数和描...