over 2 years ago

题目链接:

http://www.lydsy.com/JudgeOnline/problem.php?id=1069
http://www.lydsy.com/JudgeOnline/problem.php?id=1070
http://www.lydsy.com/JudgeOnline/problem.php?id=1071

分析:

最大土地面积

很显然四个点都在凸包上,我们不妨先确定一个点,然后顺时针确定与这个点相邻的四边形的对角线,这样剩下的两个点就可以相当于对角线在凸包上的两个切点,根据旋转卡壳的理论我们可以的时间转出来。。
bzoj1069.cpp

修车

又是一个网络流建模,我开始想的是把一个修理人员拆成个点对应每一个人,但发现搞不定啊。。看题解后才发现,是把每一个修理人员依旧拆成个点,但是这个点分别代表的是倒数第个来参加修理的人,边权直接乘上会影响到的人数就好了。。
bzoj1070.cpp

组队

单调性的好题,我们考虑固定,然后从左往右扫,我们发现题目中的式子,右边的值是在不断增大的,所以我们考虑按从小到大插入答案中,然后减去不符合条件的就可以了。
bzoj1071.cpp

← bzoj1068:[SCOI2007]压缩 替罪羊树:bzoj3065 →
 
comments powered by Disqus