Poj练习

Published: by Creative Commons Licence

  • Tags:

POJ3692

题意

有G个女生和B个男生,女生互相认识,男生互相认识,部分男生和女生相互认识。问最多能找到多少人,使得这些人都相互认识。

题解

问题实际上求的是二分图的最大团。

POJ2060

题意

有n个订单,我们可以派出车辆去接这些订单。每个订单都有一个截止时间,接客地点,目标地点。一个车辆送客完成后可以去接下一个订单。要求每个订单,都必须有车辆去接。问最少需要多少车辆。

题解

问题实际求的是不相交最小路径覆盖。

POJ3155

裸题,要求计算最大密度子图。

POJ2987

题目要求我们找这样一个闭合图,图的总权最大且顶点数尽可能少。对于每一个顶点u,我们可以将顶点u的权重修正为w(u)*10000-1,这样找到的闭合图中不仅总权最大,而且顶点也最少。

POJ3335

题意:

判断多边形的核是否存在。

题解:

利用半平面交算多边形的核,如果核存在,则至少会有3条边组成。

POJ3525

题意:

寻找多边形中距离边缘最远的点。

题解:

二分可能的距离d,之后将多边形的边按照垂线移动d距离,判断新的多边形是否存在。

POJ3384

题意:

寻找两个点,点距离边缘距离必须超过r,且两个点尽可能远。

题解:

首先将多边形的边按照垂线移动r距离。之后留下的多边形一定是凸包,在凸包上找最远的两个点,这两个点一定是凸包的顶点。可以利用旋转卡壳或暴力计算。

POJ1755

题意:

给出一组ai,bi,ci。对于每个i,判断是否存在三个正数x,y,z,使得对所有$j\neq i$满足$a_ix+b_iy+c_iz < a_jx+b_jy,c_jz$,

题解:

首先三元不好计算,我们可以始终认为z被设置为1,换言之我们将z的赋值作为比较的标准。我们对每个i进行独立计算,将不等式转换为

这是一组不等式,可以让我们想到可以用线性规划来解决。但是由于只有两个变量,我们可以将每个不等式转换为一个半平面,之后判断这些半平面是否形成了一个有效的多边形。

POJ2540

题意:

见链接http://poj.org/problem?id=2540

题解:

与当前位置p和上一次位置p'等距离的点一定落在线段pp'的中垂线上。知道这一点之后可以不断剔除一半的平面就可以了,半平面交算法。

POJ1755

题意

http://poj.org/problem?id=1755

题解

这个问题可以用半平面交来解决。但是对于,铁人四项,铁人五项,半平面交就没办法了。这里可以使用扩展性更好的线性规划来解决。

记$x_i$表示第$i$个比赛的长度。很显然第$j$个人花费的时间为$x_1/v_j+x_2/u_j+x_3/w_j$。之后建立线性规划方程:

这里可以转换成对偶形式来加速。

之后只有当对偶形式有无有穷解的时候,原形式无解。对偶形式无解时原形式无有穷解。

POJ2774

题意

http://poj.org/problem?id=2774

题解

神级模板题。还有更裸的吗,后缀数组、后缀自动机、后缀树啥的,都来一波。

POJ2104

题意

http://poj.org/problem?id=2104

题解

有持久化线段树的$O(n\log_2n)$的在线做法。这里介绍的是整体二分的做法。

首先将元素按照大小进行排序。之后进行二分。当调用二分的时候,我们二分元素,将元素集合分成两部分,之后将左边的元素全部加入到BIT中(BIT中第i元素代表的是第i个元素是否加入,加入为1,否则为0)。之后遍历请求,对于请求q,按照q查询区间中的元素数目与k的关系,将查询也分成两部分。之后重复调用整体二分过程,同时退出函数的时候需要清除这次调用带来的影响。时间复杂度为$O((n+m)(\log_2n)^2)$。