2016.2.4总结

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)还必须在多边形内,这个也构成了一些半平面
所有这些半平面的交的区域的面积与原多边形的面积比即为答案
------------------------------------------------------------------------------------