[CF 249D]Donkey and Start解题报告

题意

第一象限上有n<=10^5个点。以分数的形式给定两个斜率k1和k2(这样可以表示tan90°的情况)。保证对应倾斜角在[0°,90°]内。从原点开始,从我们所在的点作两条斜率分别为k1和k2的射线,并在射线所夹区域内部(不含射线上)选一个点,并继续这样做下去,直到无点可选。问途中最多经过多少个点。

像这样:



它的坐标是x轴往左,y轴往上……我估计这么做的原因是为了迷惑你……

分析

这道题的关键是很明显的:假设过原点,斜率为k1和k2的单位向量分别为v1和v2,那我们就以(v1,v2)为基底建立一组新的坐标系。而在新的坐标系中,规则就变成了:下一步只能选择x和y坐标均严格大于当前点的点。

换言之,将所有点按x坐标为第一关键字,y坐标为第二关键字排序后,我们要求的也就是从原点出发的最长上升序列。当然需要注意,该序列中的x坐标也必须单调上升。

所以按照求LIS的经典方法,用一个树状数组维护即可。

代码

#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int SIZEN=100010;
class BIT{
public:
	int n;
	int s[SIZEN];
	#define lowbit(x) ((x)&(-x))
	void clear(int _n){
		n=_n;
		memset(s,0,sizeof(s));
	}
	void modify(int x,int t){
		for(;x<=n;x+=lowbit(x)) s[x]=max(s[x],t);
	}
	int pref_max(int x){
		int ans=0;
		for(;x;x-=lowbit(x)) ans=max(ans,s[x]);
		return ans;
	}
};
class Point{
public:
	LL x,y;
	int id;
};
void print(const Point &p){
	cout<<"("<

发表评论

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