[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<<"("<

题意

分析

代码

发表回复 取消回复

发表回复取消回复