2009
12.15

pku 2104 K-th Number 求某区间第k小数

分类: pku解题报告, 线段树 / 标签: , , , , ,  / 添加回复

学习了网上最常用的解法——归并树。
所谓的归并树并不是什么新奇的东西，顾名思义，其实就是归并排序+线段树。把归并排序过程中的各区间排序后的结果，用线段树储存起来！
对题目给定的区间，只要在线段树中查找组成该区间的各个子区间即可！——logN
关键在于求出某个值在线段树各个子区间中，小于该值的元素个数，还是用到了二分，继续是logN。
由于要求的是该区间的第k小元素，可以对整个排序完的数组进行二分查找，当某元素在该区间中排第k小，并且该元素属于该区间，即为答案。对排序数组进行二分查找，也是logN。
耗时：2500ms+

?View Code C
#include
#define N 100010
struct T
{
	int l,r,mid;
}t[N*4];
int sort[20][N];
int id[20][N];
int key[N],s,e;
int build(int p,int l,int r,int dep)
{
	t[p].l=l;
	t[p].r=r;
	t[p].mid=(l+r)>>1;
	if(l==r)
	{
		sort[dep][l]=key[l];
		id[dep][l]=l;
		return 0;
	}
	build(p<<1,l,t[p].mid,dep+1);
	build((p<<1)+1,t[p].mid+1,r,dep+1);
	int i,j,mid,now;
	mid=t[p].mid;
	i=l;	j=mid+1;	now=l;
	while(i<=mid && j<=r)
	{
		if(sort[dep+1][i]<=r)
		{
			id[dep][now]=id[dep+1][j];
			sort[dep][now++]=sort[dep+1][j++];
		}
	else
		while(i<=mid)
		{
			id[dep][now]=id[dep+1][i];
			sort[dep][now++]=sort[dep+1][i++];
		}
	return 0;
}
int b_search(int left,int right,int v,int dep)
{
	int l,r,m;
	l=left;r=right;
	if(v<=sort[dep][l])
		return 0;
	else if(v>sort[dep][r])
		return (r-l+1);
	while(l>1;
		if(sort[dep][m]>=v && sort[dep][m-1]<=t[p].l && t[p].r<=e)
	{
		return b_search(t[p].l,t[p].r,v,dep);
	}
	else
	{
		if(s>t[p].r || e<<1,v,dep+1)+query((p<<1)+1,v,dep+1);
	}
}
int main()
{
//	freopen("1.txt","r",stdin);
	int n,q,i,j,k,left,right,mid,result,p;
	while(scanf("%d %d",&n,&q)!=EOF)
	{
		for(i=1;i<=n;i++)
			scanf("%d",&key[i]);
		build(1,1,n,1);
		while(q--)
		{
			scanf("%d %d %d",&s,&e,&k);
			left=1;	right=n;
			k--;
			p=0;
			while(left>1;
				result=query(1,sort[1][mid],1);
				if(result==k && id[1][mid]>=s && id[1][mid]<=e)
				{
					p=1;
					printf("%d\n",sort[1][mid]);
					break;
				}
				if(result<=k)
					left=mid;
				else
					right=mid-1;
			}
			if(!p)
				printf("%d\n",sort[1][left]);
 
		}
	}
	return 0;
}
2009
12.08

pku 1177 Picture 矩形并的周长 线段树

分类: pku解题报告, 数据结构 / 标签: 暂无标签 / 添加回复

关键字：节点的测度，节点的独立线段树

?View Code C
#include
#include
 
#include
struct p
{
	int x,s,e,flag;
}a[10100];
struct yy
{
	int id,y,dy;
}index[10100];
struct T
{
	int l,r,m,line,c,l_c,r_c;
}tree[100000];
int map[10100];
int cmp1(const void *a ,const void *b)
{
	return (*(yy *)a).y-(*(yy *)b).y;
}
int cmp2(const void *a,const void *b)
{
	return (*(yy *)a).id-(*(yy *)b).id;
}
int cmp3(const void *a,const void *b)
{
	return (*(p *)a).x-(*(p *)b).x;
}
int build(int p,int left,int right)
{
	tree[p].l=left;
	tree[p].r=right;
	tree[p].l_c=tree[p].r_c=tree[p].c=tree[p].line=tree[p].m=0;
	if(left+1==right)
		return 0;
	build(p<<1,left,(left+right)>>1);
	build((p<<1)+1,(left+right)>>1,right);
	return 0;
}
int update1(int p)//更新m
{
	if(tree[p].c>=1)
	{
		tree[p].m=map[tree[p].r]-map[tree[p].l];
	}
	else
	{
		if(tree[p].l+1==tree[p].r)
			tree[p].m=0;
		else
			tree[p].m=tree[p<<1].m+tree[(p<<1)+1].m;
	}
	return 0;
}
int update2(int p)//更新line
{
	if(tree[p].c>=1)
	{
		tree[p].l_c=tree[p].r_c=tree[p].line=1;
	}
	else
	{
		if(tree[p].l+1==tree[p].r)
			tree[p].l_c=tree[p].r_c=tree[p].line=0;
		else
		{
			tree[p].line=tree[p<<1].line+tree[(p<<1)+1].line-tree[p<<1].r_c*tree[(p<<1)+1].l_c;
			tree[p].l_c=tree[p<<1].l_c;
			tree[p].r_c=tree[(p<<1)+1].r_c;
		}
	}
	return 0;
}
int insert(int p,int left,int right,int v)
{
	if(left<=tree[p].l && tree[p].r<=right)
	{
		tree[p].c+=v;
		update1(p);
		update2(p);
	}
	else
	{
		if(left>=tree[p].r || right <=tree[p].l)
		{
			return 0;
		}
		insert(p<<1,left,right,v);
		insert((p<<1)+1,left,right,v);
		update1(p);
		update2(p);
	}
	return 0;
}
int main()
{
//	freopen("1.txt","r",stdin);
	int n,i,j,k,x1,x2,y1,y2,t,len,num,P,cover;
	while(scanf("%d",&n)!=EOF)
	{
		num=n<<1;
		for(i=0;i
2009
12.06

HDU 1255 覆盖的面积 – 线段树

分类: pku解题报告, 数据结构, 线段树 / 标签: 暂无标签 / 添加回复

题意：求矩形的交的面积！覆盖两次或以上！
将每个矩形的两条纵向边看成两个事件点，遇到左端点，插入该纵向边，遇到右节点，删除该边！
对所有y坐标进行离散化！进行线段树的插入和更新操作！
其实这道题跟求矩形的并的面积类似。不同的是更新每个节点覆盖长度的操作！
我采用cover，once，more这三个变量来维护线段树。
cover：表示该节点被覆盖多少次。
once：表示该节点表示的长度中，被覆盖1次以上的长度。
more：表示该节点表示的长度中，被覆盖2次以上的长度。
插入操作：找到属于当前边范围的节点，cover+=v。v是个标志，表示是插入边或删除边。
更新操作比较复杂。
当前节点被覆盖两次或以上，那么该点的once和more值都是节点表示的长度。
当前节点被覆盖一次，那么once等于节点的长度，而more等于左右子树被覆盖一次以上的长度的和。
当节点没有被覆盖，那么once等于左右子树的once值的和，more等于左右子树more的值的和。
另外还要考虑当前节点是否为单位长度，具体见代码。
更新代码如下：

?View Code C
int update(int p)
{
	if(tree[p].c>1)
	{
		tree[p].once = tree[p].more = map[tree[p].r]-map[tree[p].l];
	}
	else if(tree[p].c==1)
	{
		tree[p].once = map[tree[p].r]-map[tree[p].l];
		if(tree[p].l+1==tree[p].r)
			tree[p].more=0;
		else
			tree[p].more=tree[p<<1].once+tree[(p<<1)+1].once;
	}
	else
	{
		if(tree[p].l+1==tree[p].r)
			tree[p].once=tree[p].more=0;
		else
		{
			tree[p].once=tree[p<<1].once+tree[(p<<1)+1].once;
			tree[p].more=tree[p<<1].more+tree[(p<<1)+1].more;
		}
	}
	return 0;
}

继续阅读全文 >>

2009
12.05

pku 2187 Beauty Contest (步进法)

分类: pku解题报告, 计算几何 / 标签: 暂无标签 / 添加回复

凸包的另一种经典算法！

?View Code C
#include
struct node
{
	int x,y;
}a[50010],b[50010],temp;
int cross(node a,node b,node c)
{
	int x1,x2,y1,y2;
	x1=b.x-a.x;
	x2=c.x-a.x;
	y1=b.y-a.y;
	y2=c.y-a.y;
	return x1*y2-x2*y1;
}
int dis(node a,node b,node c)
{
	int d1,d2;
	d1=(c.x-a.x)*(c.x-a.x)+(c.y-a.y)*(c.y-a.y);
	d2=(b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);
	if(d1>d2)
		return 1;
	else
		return 0;
}
int comp(node a,node b)
{
	if(a.x==b.x && a.y==b.y)
		return 1;
	else
		return 0;
}
int main()
{
//	freopen("1.txt","r",stdin);
	int n,i,j,k,top,c;
	while(scanf("%d",&n)!=EOF)
	{
		scanf("%d %d",&a[0].x,&a[0].y);
		for(i=1;i<0 || (c==0 && dis(b[top],temp,a[i])))
				{
					temp=a[i];
				}
			}
			top++;
			b[top]=temp;
			temp=a[0];
		}while(!comp(b[top],b[0]));
		int max=0;
		for(i=0;imax)
					max=(b[i].x-b[j].x)*(b[i].x-b[j].x)+(b[i].y-b[j].y)*(b[i].y-b[j].y);
			}
		}
		printf("%d\n",max);
	}
	return 0;
}
2009
12.05

pku 1151 Atlantis (求矩形并的面积) 线段树

分类: pku解题报告, 数据结构 / 标签: 暂无标签 / 添加回复

这道题的另一种解法-线段树。
不过花了16ms！还没矩形切割来得快。

?View Code C
#include
#include
#include
struct node
{
	double x;
	int s,e,value;
}line[210];
struct s
{
	double y;
	int dy;
	int id;
}index[210];
struct tree
{
	int l,r,mid,c;
	double m;
}T[1000];
double map[210];
int cmp1(const void *a,const void *b)
{
	return (*(s *)a).y>(*(s *)b).y?1:-1;
}
int cmp2(const void *a,const void *b)
{
	return (*(s *)a).id-(*(s *)b).id;
}
int cmp3(const void *a,const void *b)
{
	return (*(node *)a).x>(*(node *)b).x?1:-1;
}
int build(int p,int left,int right)
{
	T[p].l=left;
	T[p].r=right;
	T[p].mid=(left+right)>>1;
	T[p].m=T[p].c=0;
	if(left+1==right)
		return 0;
	build(p<<1,left,T[p].mid);
	build((p<<1)+1,T[p].mid,right);
	return 0;
}
int update(int p)
{
	if(T[p].c)
	{
		T[p].m=map[T[p].r]-map[T[p].l];
		return 0;
	}
	if(T[p].l+1==T[p].r)
		T[p].m=0;
	else
		T[p].m=T[p<<1].m+T[(p<<1)+1].m;
	return 0;
 
}
int insert(int p,int left,int right,int v)
{
	if(left<=T[p].l && right>=T[p].r)
	{
		T[p].c+=v;
		update(p);
	}
	else
	{
		if(left>=T[p].r || right<=T[p].l)
			return 0;
		insert(p<<1,left,right,v);
		insert((p<<1)+1,left,right,v);
		update(p);
	}
	return 0;
}
int main()
{
//	freopen("1.txt","r",stdin);
	int n,i,j,k,t,num,len,Case=1;
	double x1,y1,x2,y2,area;
	while(scanf("%d",&n)!=EOF && n)
	{
		num=n<<1;
		for(i=0;i
2009
12.02

pku 1151 Atlantis (求矩形并的面积)

分类: pku解题报告, 计算几何 / 标签: , ,  / 添加回复

好久没有1A，感觉太爽了。
题意：给定n个矩形的左上角和右下角。要求所有矩形的面积总和，忽略重合的部分！
思路：对于任意两个矩形，先判断是否相交，如果不相交，则不用进行切割处理。如果相交的话，那么将两矩形的重叠部分切掉，剩余部分按x，y轴切割！
最后将切割后的矩形进行面积统计即可！
参考：国家集训队2004论文集—薛矛：线段树与矩形切割

?View Code C
#include<stdio.h>
struct node
{
	double x1,x2,y1,y2;
}m[105];
node l[1000000];
int p;
int cross(node a,node b)
{
	if(a.x1>=b.x2 || b.x1>=a.x2 || a.y1>=b.y2 || b.y1>=a.y2)
		return 0;
	return 1;
}
double max(double a,double b)
{
	return a>b?a:b;
}
double min(double a,double b)
{
	return a<b?a:b;
}
int add(double x1,double y1,double x2,double y2)
{
	l[p].x1=x1;
	l[p].x2=x2;
	l[p].y1=y1;
	l[p].y2=y2;
	p++;
	return 0;
}
int main()
{
	//freopen("1.txt","r",stdin);
	int n,Case,i,j,k;
	double area,x1,x2,x3,x4,y1,y2,y3,y4,k1,k2,k3,k4;
	Case=1;
	while(scanf("%d",&n)!=EOF)
	{
		if(n==0)
			return 0;
		area=0;
		for(i=0;i<n;i++)
		{
			scanf("%lf %lf %lf %lf",&m[i].x1,&m[i].y1,&m[i].x2,&m[i].y2);
		}
		l[0]=m[0];
		p=1;
		for(i=1;i<n;i++)
		{
			for(j=0;j<p;j++)
			{
				if(cross(l[j],m[i]))
				{
					x1=l[j].x1;
					x2=l[j].x2;
					x3=m[i].x1;
					x4=m[i].x2;
					y1=l[j].y1;
					y2=l[j].y2;
					y3=m[i].y1;
					y4=m[i].y2;
					k1=max(x1,x3);
					k2=min(x2,x4);
					if(x1<k1)
						add(x1,y1,k1,y2);
					if(x2>k2)
						add(k2,y1,x2,y2);
					k3=max(y1,y3);
					k4=min(y2,y4);
					if(y1<k3)
						add(k1,y1,k2,k3);
					if(y2>k4)
						add(k1,k4,k2,y2);
					l[j]=l[p-1];
					p--;
				}
			}
			l[p++]=m[i];
 
		}
		for(i=0;i<p;i++)
		{
			area+=(l[i].x2-l[i].x1)*(l[i].y2-l[i].y1);
		}
		printf("Test case #%d\nTotal explored area: %.2lf\n\n",Case++,area);
 
 
	}
	return 0;
}
2009
12.02

pku 2482 Stars in Your Window

分类: pku解题报告 / 标签: ,  / 添加回复

题意：给出二维坐标上n个星星的坐标（x，y）还有亮度。问：用一个w*h的方框，通过平移，在框内的星星的亮度总和是最大的！
X轴: 每个x处理作两个事件点( x, v ), ( x + w, -v ), v插入对应线段, -v删除该线段
Y轴：每个坐标y也处理为两个事件点，所以有线段( y, y+h ) , 离散化为 (s, e)
事件点的概念可以参考李睿的论文！
所以要做的就是统计线段覆盖的最大值！用到了线段树。
由于给定数据范围为：
0< =x，y<2^31
1<=W，H<=1000000
而事件点x+w或y+h，使用int有可能溢出而WA，为此我贡献了30+次WA。
至此，终于把这道优美的题目给AC了……

继续阅读全文 >>

2009
11.28

PKU 1375 Intervals

分类: 计算几何 / 标签:  / 添加回复

假设发光点位置是x0.
那么对于每个圆，要考虑圆心位置是在x0的左边还是右边。
对于圆心在左侧的，需要考虑这个圆是否跨越了x=x0这条直线。
对于圆心在右侧的，同样要考虑跨越。
因为在左右两边的计算方法不同。
最近真是没状态……哎！
代码：

?View Code C
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct node
{
	double s,e;
}list[505];
int cmp(const void *a,const void *b)
{
 
	if((*(node *)a).s==(*(node *)b).s)
		return (*(node *)a).e>(*(node *)b).e?1:-1;
	else
		return (*(node *)a).s>(*(node *)b).s?1:-1;
}
int main()
{
//	freopen("Intervals.in","r",stdin);
//	freopen("2.txt","w",stdout);
	int n,i,j,k;
	double x0,y0,x,y,r,dis,A,B;
	while(scanf("%d",&n)!=EOF && n)
	{
		scanf("%lf %lf",&x0,&y0);
		for(i=0;i<n;i++)
		{
			scanf("%lf %lf %lf",&x,&y,&r);
			dis=sqrt((double)((x-x0)*(x-x0)+(y-y0)*(y-y0)));
			A=asin(r/dis);
			B=asin(fabs(x-x0)/dis);
			if(x<=x0)
			{
				list[i].s=x0-y0*tan(A+B);
				if(x+r<=x0)
				{
					list[i].e=x0-y0*tan(B-A);
				}
				else
				{
					list[i].e=x0+y0*tan(A-B);
				}
			}
			else
			{
				list[i].e=x0+y0*tan(A+B);
				if(x-r>=x0)
				{
					list[i].s=x0+y0*tan(B-A);
				}
				else
				{
					list[i].s=x0-y0*tan(A-B);
				}
			}
		}
		qsort(list,n,sizeof(node),cmp);
		double min=list[0].s;
		double max=list[0].e;
		for(i=1;i<n;i++)
		{
			if(list[i].s<=max)
			{
				max=max>list[i].e?max:list[i].e;
			}
			else
			{
				printf("%.2lf %.2lf\n",min,max);
				min=list[i].s;
				max=list[i].e;
			}
		}
		printf("%.2lf %.2lf\n\n",min,max);
	}
	return 0;
}
2009
11.13

pku 2780 Linearity

分类: pku解题报告, 计算几何 / 标签: 暂无标签 / 添加回复

题意：给定n个点 n< =1000。
要求最多有多少个点在同一直线上。
据说这道题可以暴力，用n^3复杂度ac。
不过这样子ac，似乎没什么意义。

我用的方法是：对于任意两个点。用gcd(xi-xj,yi-yj)求出两个点之间，有多少个坐标是整数的点。然后检查这些点是否出现在给定的点里面。
耗时：641ms。

继续阅读全文 >>

2009
11.12

pku 2362 Square (dfs)

分类: pku解题报告 / 标签: ,  / 添加回复

dfs判断木棒是否可组成四根长度为总长度/4的木棒。
如果总长度不能取余4，则输出no。
如果某根木棒长度大于总长度/4，也输出no。
将木棒长度排序。每次从头往后找，如果找到某根木棒长度大于目前剩余长度，则回溯。
代码：

?View Code C
 
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
bool flag;
int use[22],n,s[22],length;
int cmp(const void *a,const void *b)
{
	return *(int *)a-*(int *)b;
}
int dfs(int num,int len,int loc)
{
	if((num==0 &&  len==length) || flag)
	{
		flag=true;
		return 0;
	}
	int i,j,k;
	for(i=loc;i<n;i++)
	{
		if(!use[i])
		{
			if(s[i]==len)
			{
				use[i]=true;
				dfs(num-1,length,0);
				use[i]=false;
			}
			else if(s[i]<len)
			{
				use[i]=true;
				dfs(num,len-s[i],i+1);
				use[i]=false;
			}
			else
				return 0;
		}
	}
	return 0;
}
int main()
{
//	freopen("1.txt","r",stdin);
	int kase,i,j,k,len,max;
	scanf("%d",&kase);
	while(kase--)
	{
		flag=false;
		len=max=0;
		scanf("%d",&n);
		for(i=0;i<n;i++)
		{
			scanf("%d",&s[i]);
			if(s[i]>max)
				max=s[i];
			len+=s[i];
		}
		if(len%4)
		{
			printf("no\n");
			continue;
		}
		else
			length=len/4;
		if(max>length)
		{
			printf("no\n");
			continue;
		}
		qsort(s,n,sizeof(int),cmp);
		memset(use,false,sizeof(use));
		dfs(4,length,0);
		if(flag)
			printf("yes\n");
		else
			printf("no\n");
	}
	return 0;
}
« 前一页