[USACO Jan07]考试Schul解题报告

题目


分析

这道题比较有意思。

首先,我们不用t和p来表示分数,我们用(x,y),代表满分为x的卷子得了y分。这样更加直观:把一份卷子视作向量,那么它的“分数率”也就是其斜率。最终的分数率自然就是所有向量之和的斜率。

先考虑一个问题:假如对某个给定的d,现在已经按老师的方法确定了最终的分数率G,那么我们能否改变略去的d份试卷,使得分数率高于G呢?

这时我们可以采用在一类二分答案+网络流/最短路题里常用的思路:对每一份试卷i,算出pi=yi-G*xi(我们把pi称作(xi,yi)的G-截距)。那么,如果我们能够挑出N-d份试卷,使得其pi之和大于零,那就意味着把这些试卷加一块的分数率大于G。

于是更进一步地,若老师选中的试卷中的最小pi(记为worst_in[d])小于老师略去的试卷中的最大pi(记为best_out[d]),就意味着对于当前的d,Bessie可以得到一个更高的分数率。

这样就有了一个O(N^2)的算法:枚举每一个d,计算出G。然后据此计算出worst_in[d]和best_out[d],把二者比一比,若worst_in[d]

但这还远远不够。怎么办呢?



不妨以best_out为例。在这里我们试图算出分数率最小的d份卷子中,最大的pi。可以发现,过这d份卷子在直角坐标系中的对应点做斜率为G的直线束,其中最靠上那条直线的截距就是这个“最大的pi”。若形象地描述,可以想象我们拿斜率为G的直线从y轴正方向无穷远处向下移动,碰到的第一个点就是那个pi最大的点。

这很像一个凸包模型,而事实也的确如此。我们不妨将求best_out的模型用几何语言描述:

①我们按照极角逆时针序,不断往平面上添加点(极角逆时针序也就是斜率升序,也就是分数率从小到大排序)。

②在每一个点处,都有一个G,我们试图找出当前点集中的G-截距最大点。

③在处理的过程中,G不断变大(可以想象,我们不断在老师选中的试卷中扔掉分数率最小的那个,则剩下的分数率自然越来越大)。

可以发现,那个G-截距最大点一定位于当前点集的上凸线上。

那么,怎么维护上凸线呢?按极角序加点并不能线性地维护上凸线(想到Graham没……它维护的是整个点集的凸包)。当然你可以写一个神奇的数据结构或者CDQ分治啥的,当然我们有更简单的方法——

大力出奇迹,新加点时,直接删掉x坐标大于等于它的所有点!这样就变成了一个从左向右加点,维护上凸线的模型。

为什么这么做是对的呢?

假设当前的情形是这样的:



其中O是原点,P是新添加的点,蓝色折线是上凸线,黑色直线垂直于x轴。

(ps:这个上凸线其实画的不科学,不要在意这些细节,意会即可)

取横坐标大于等于P点的C点。我们需要证明:无论在现在还是未来,P点的G-截距都比C点的G-截距大。

设P(x1,y1),C(x2,y2),k=y1/x1.

显然y2/x2
∴y1-kx1=0, y2-kx2<0
∴y1-kx1>y2-kx2, y2-y1
我们来看总分数率G。

G有一个性质:对于当前的d,G一定大于d号点(也就是P)的斜率。原因很简单:G是所有比d斜率大的点加起来的斜率,自然大于d的斜率了。

结合③,我们可以得到:当前的G大于P的斜率k,而且以后的G也一定大于k。

而对于G>k,y2-y1

直观地看,当前的G比红线大,以后还会更大,那么斜率为G的直线截到的最上点一定不可能是C、D。

但是,直接把凸线上P右边那些点删去之后,剩余的凸线可能并非P左边那些点形成的凸线——中间的点可能之前被删去,这里没有加上。然而这个其实并没有问题,因为我们可以发现,如果一个点之前已从凸线上删去,那么它无论何时都不会成为答案。

综上,每次新加P时,维护这个上凸线的方法就是:

1)从上凸线的右侧删去x坐标大于等于P的点。

2)从上凸线的右侧删去加上P后不再在凸线上的点。

3)不断从上凸线右侧删点,直到G-截距不再下降,这时上凸线的最右点也就是G-截距最大点。其G-截距也就是当前的best_out[d]。



再来看worst_in。

其模型是:

①按极角序从高到低(分数率从大到小)加点。

②每次找G-截距最小点。
③G不断减小。

而维护凸线的方法就是:从右到左加点,维护下凸线(顺便说一句,USACO官方题解中是非常别扭地从上到下加点,维护右凸线……其实是一样的)。即每次删去所有x坐标>=P的点。

此法的正确性证明其实和best_out大为不同。画个图:



P是新加点,竖直黑色虚线垂直于x轴,A是被删掉的点。

设P(x1,y1),A(x2,y2),k=y1/x1,那么显然k=y1/x1

∴y1-kx1=0
∴y1-y2

而x1-x2>0(注意,证明依赖于这一点,而那个右凸线的方法实际是由y1-y2>0推出x1-x2>0),所以若将来某个G’使得A的G’-截距小于P的G’-截距,那么一定有G’

这里又回到G的性质了:当我们枚举到d时,G一定不小于d+1号点的斜率。

那么,如果将来G’

但这时,观察上式可以发现,必有y3-G’x3<0

直观上,若将来A比P优,那么G’至多是红色虚线的斜率,这个斜率必然小于P的斜率,因此必定有个比P斜率还要小的点B,其G’-截距优于A(拿着红色虚线卡一卡,就会发现必然先碰到B)。

为了避免读者可能的迷惑,我又画了一个斜率比P大的点T。显然,当G’>k时,T就可能优于P了(比如绿色虚线就是先卡到T再卡到P的),因而上述论证不再成立。你可以直观地意识到,“证明依赖于x1-x2>0”的含义。

因此每次新加P时维护下凸线的方法就是:

1)从下凸线左侧删去x坐标小于等于P的点。

2)从下凸线左侧删去加上P后不再在凸线上的点。

3)不断从下凸线左侧删点,直到G-截距不再上升,这时下凸线的最左点也就是G-截距最小点。其G-截距就是当前的worst_in[d+1](d+1是因为按照老师的算法略去了d个点,留下的第一个点是d+1)。



最后,每一个best_out[d]>worst_in[d+1]的d都是答案。


代码

#include
#include
#include
#include
#include
#include
using namespace std;
const int SIZEN=50010;
class Point{
public:
	double x,y;
	Point(double _x=0,double _y=0){
		x=_x;
		y=_y;
	}
};
void print(const Point &p){
	cout<<"("<0;
}
double calc(const Point &a,double m){
	return a.y-m*a.x;
}
int N;
Point P[SIZEN];
double ratio[SIZEN];
double best_out[SIZEN],worst_in[SIZEN];
Point H[SIZEN];
void work(void){
	sort(P+1,P+1+N,cmp_angle);
	Point now(0,0);
	for(int i=N;i>=1;i--){
		now=now+P[i];
		ratio[i]=now.y/now.x;
	}
	int tot=0;
	for(int i=1;i=1&&H[tot-1].x>=P[i].x) tot--;//滤掉右边的
		while(tot>=2&&dir_area(H[tot-2],H[tot-1],P[i])>=0) tot--;//滤掉不在上凸线上的
		H[tot++]=P[i];//上凸线新加点
		while(tot>=2&&calc(H[tot-1],ratio[i+1])<=calc(H[tot-2],ratio[i+1])) tot--;//滤掉不被当前斜率卡住的
		best_out[i]=calc(H[tot-1],ratio[i+1]);
	}
	tot=0;
	for(int i=N;i>=1;i--){
		while(tot>=1&&H[tot-1].x<=P[i].x) tot--;//滤掉左边的
		while(tot>=2&&dir_area(H[tot-2],P[i],H[tot-1])<=0) tot--;//滤掉不在下凸线上的
		H[tot++]=P[i];//下凸线新加点
		while(tot>=2&&calc(H[tot-1],ratio[i])>=calc(H[tot-2],ratio[i])) tot--;//滤掉不被当前斜率卡住的
		worst_in[i]=calc(H[tot-1],ratio[i]);
	}
	vector ans;
	for(int i=1;i

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注