2016.2.4总结
_THIS_IS_START_OF_ARTICLE_
_THIS_IS_END_OF_ARTICLE_
SCOI2015..
做过的题。。。
------------------------------------------------------------------------------------
T1:
二分答案+最大流验证
有个很坑的地方是要求第k大而不会是第k小...因此一开始先令k=n-k
边(u,v,a[u][v])∈E(1<=u<=n , 1 <=v<=m)
二分答案mid
断开大于mid的边，看是否有至少k个匹配
------------------------------------------------------------------------------------
T2:
首先倍长一下原序列拆环
如果只是从某一个人开始，那么应该每次贪心的选在他的区间里右端点最远的，而因为区间没有包含关系，因此右端点最远意味着左端点最远，因此预处理出每个人的决策，即在他的区间内离他最远的点
把每个人的决策看做是他的father，得到一棵树
于是就是要求对于每一个人(l,r)，求他的祖先中右端点>=l+m的最深点u，这个人的答案就是这个这个人的深度和u的深度的差
倍增即可
------------------------------------------------------------------------------------
T3:
设小凸坐的点为p(x,y)
预处理出p和每条边围成的三角形面积S△ki，用向量积得到一个二元一次多项式
列出不等式:S△ki>=S△k1(i>=2)
化简后成y>=kx+b的形式，这是一个半平面
另外(x,y)还必须在多边形内，这个也构成了一些半平面
所有这些半平面的交的区域的面积与原多边形的面积比即为答案
------------------------------------------------------------------------------------
评论 (0)
