dd.cpp

这是一道大学生信息学奥林匹克竞赛的试题的解答

#include "iostream.h"
#include "stdio.h"
#include "stdlib.h"

int a[10000000],b[5000000],c[5000000];
int dd[22222];
long int tt[23];
int countnum(int);
void count1(int,int,int,int);
void count2(int,int);
void count3(int);

void  main () 
{int n,m;
	int i;	
    while(1)
	{
		int ttt;
  		scanf("%d",&n);
		if (n==0)
		goto exit11;
	    m=countnum(n);
		printf("m%d n%d ",m,n);
		for(ttt=0;ttt<=n;ttt++)
			printf("t %d ",tt[ttt]);
	 
		for( i=0;i<m;i++)
		dd[i]=c[i]=a[i]=b[i]=0;
		
		count1(0,m,n,1);
		for( i=0;i<2*m;i++)
			printf("a%d ",a[i]); 
		
		count2(n,m);
		for( i=0;i<m;i++)
			printf("b%d ",b[i]);
	
		count3(n);
		for( i=0;i<m;i++)
			printf("c%d ",c[i]);
		printf("m%d n%d ",m,n);
	}
exit11:
	return;
}
////////////
int countnum(int n) 
{
	int i,j, sum=0;int temp=0;
	tt[0]=0;
	for( i=1;i<=n;i++)
	{	
		temp=1;
		for(j=i;j>1;j--)
		temp*=2;
		
		sum+=temp;
	   tt[i]=sum;
	}
	if (n<=0) sum=0;
	return sum;
}
void  count1(int i,int m,int n, int flage)
{
	static int j;
	if(flage) j=0;
	if(n>0)
	{a[j++]=(m+i)/2;a[j++]=n;
	count1(i,(m+i)/2,n-1,0);
	count1((m+i)/2,m,n-1,0);
	}
	else return;
}
void count2(int n,int m)
{
	int j,i,k=0;
	for( i=n;i>0;i--)
	{
		for( j=0;j<m;j++)
		{
			if(a[j*2+1]==i)
			   b[k++]=a[j*2];
		}
	}
}
void  count3(int n)
{
	int h,i,j;
    for (h=1;h<=n;h++) 
	{	
		for(i=countnum(h)-1;i>countnum(h-1)-1;i--)
		{   
			int sum=0;
			for(j=0;j<b[i];j++)
				sum+=dd[j]; 
			if(sum%2)                      //ji shu ou shu
			    c[b[i]]= -1;
			else                           //因地跪顺序的不确定导致次拴法破产
                c[b[i]]= 1;
		}
    	for(i=countnum(h)-1;i>countnum(h-1)-1;i--)
		{
			dd[b[i]]=c[b[i]];
		}
	}
}