noj 1010 二叉树.txt

ACM资料大集合

#include <stdlib.h>
#include <stdio.h>

//爱德蒙斯卡普 二叉树
//所建的树为：(节点号/num值)
//         1/10
//    2/5        7/4
//  3/2  5/2    8/2   10/1
// 4/1  6/1    9/1  
#define NMAX 5000
typedef struct point
{
	int root;
	int num;//包括自己和子树的点个数
	int has;//是否存在
}point;

point tree[2*NMAX];
int flag;


void print()
{
	int i;
	for(i=1;i<=16;i++)
	{
		printf("(%d %d %d)",tree[i].root,tree[i].num,tree[i].has);
		if(i==1||i==3||i==7||i==15) printf("\n");
	}
}
void build(int p,int n,int r)
{
	tree[p].root=r;
	tree[p].num=n;
	tree[p].has=1;
//	printf("p=%d\n",p);
	if(n>1)
	{
		build(2*p,n/2,r+1);//n=2,只要构造左子树即可
		if(n>2) build(2*p+1,n-1-n/2,r+1+n/2);//n>2,构造右子树
	}
}

void update(int p)
{	//自底而上对tree[].num值维护
	while(p>=1)
	{
		tree[p].num--;
		p/=2;
	}
}

int cal(int now,int beg,int num)
{
//	printf("now=%d beg=%d num=%d\n",now,beg,num);
	if((now+beg)%num==0) return num;
	else return (now+beg)%num;
}

void del(int p,int r,int s)
{
//	printf("p=%d r=%d s=%d\n",p,r,s);
	if(r==1 && tree[p].has==1) 
	{	//删除的就是这点
		flag=s;
		tree[p].has=0;
		update(p);//维护工作
	}
	else
	{
		if(r<=tree[2*p].num+tree[p].has)//删除的点在左子树
			del(2*p,r-tree[p].has,s+tree[p].has);		
		else//删除的点在右子树
			del(2*p+1,r-tree[p].has-tree[2*p].num,s+tree[p].has+tree[2*p].num);
	}
}

int main()
{
	int i,num,knum;
	while(scanf("%d%d",&num,&knum)!=EOF)
	{
		for(i=1;i<=2*num;i++) tree[i].has=0;
		build(1,num,1);
//		print();
		flag=0;//全局变量，上一次删除过程中跳过的点，也就是本次删除一开始要跳过的点
		for(i=1;i<num;i++)
		{
//			printf("flag=%d\n",flag);
			del(1,cal(knum,flag,tree[1].num),0);
//			print();
//			system("pause");
		}
		for(i=1;i<=2*num;i++) if(tree[i].has==1) printf("%d\n",tree[i].root);
	}
//	system("pause");
	return 0;
}