Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:给组数据吧!一直WA,不知道为什么

Posted by huicpc27 at 2005-08-26 15:13:55 on Problem 1767
In Reply To:给组数据吧!一直WA,不知道为什么 Posted by:wiltord at 2004-08-15 08:34:46
> 我也不知道为什么我的也是老WA
#include<iostream.h>
class Bin
{
	public: 
		int A[32];
		int length;
		int p1;
		int p_0;
}a1,a2;

int main()
{
	//还要讨论N(t)=0和4的特殊情况
	//还要讨论N(t)为最大值的情况
	void init();
	void ToBinary(long a);
	void first100();
	void first0();
	void change();
	long compute();
	long a;
	int i;
	while(cin>>a)
	{
		init();
	if(a==0) cout<<0<<endl;
	else 
	if(a==4) cout<<4<<endl;
	else 
	{
	ToBinary(a);
	
	/*i=a1.length-1;
	while(i>=0)
	{
		cout<<a1.A[i];
		i--;
	}*/
	//cout<<endl<<a1.length;
	first100();
	first0();
	//cout<<endl<<a1.p1<<" "<<a1.p_0;
	if(a1.p_0==-1)//最大的情况
	{
		for(i=2;i<=a1.length-1;i=i+2)
			a2.A[i]=1;
	}
	else change();
	/*cout<<endl;
	i=a1.length-1;
	while(i>=0)
	{
		cout<<a2.A[i];
		i--;
	}*/
	cout<<compute()<<endl;
	
	}
	}//end while
	return 0;
}



void ToBinary(long a)//转换成二进制
{
	int i=0;
	int b;
	while(a>1)
	{
		b=a%2;
		a1.A[i]=b;
		i++;
		a=(a-b)/2;
	}
    a1.A[i]=1;
	a1.length=i+1;
}
void first100()//从右边找起 找到第一个100,并表示这个100中1的位置
{
	int i;
	for(i=0;i<=a1.length-1-2;i++)
		if(a1.A[i]==0&&a1.A[i+1]==0&&a1.A[i+2]==1)
		{
			a1.p1=i+2;
			return;
		}
}
void first0()//寻找第一个100后第一个0,并记录位置
{
	int i;
	for(i=a1.p1+1;i<=a1.length-1;i++)
		if(a1.A[i]==0)
		{
			a1.p_0=i;
			return;
		}
		a1.p_0=-1;//如果找不到 则赋为-1

}
void change()//将第一个100和第一个100后第一个0交换位置 得到偏序关系下的下一棵树
{
	int i;
	for(i=0;i<=a1.p1-3;i++)
		a2.A[i]=a1.A[i];
	a2.A[a1.p1-2]=0;
	for(i=a1.p1+1;i<=a1.p_0-1;i++)
		a2.A[i-2]=a1.A[i];
	a2.A[a1.p_0]=1;
	a2.A[a1.p_0-1]=0;
	a2.A[a1.p_0-1]=0;
	for(i=a1.p_0+1;i<=a1.length-1;i++)
		a2.A[i]=a1.A[i];

}
long compute()
{
	int i;
	long sum=0;
	long mul=1;
	for(i=0;i<=a1.length-1;i++)
	{
		sum=sum+a2.A[i]*mul;
		if(i<=a1.length-2) mul=2*mul;
	}
	return sum;
}
void init()
{
	int i;
	for(i=1;i<=31;i++)
		a1.A[i]=a2.A[i]=0;
	a1.length=0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator