Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

谁能帮我找条错误数据啊，我自测得好像是对的啊，一直RA(写的比较差)

Posted by javvy at 2010-08-05 13:23:44 on Problem 1184

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

class Node
{
     public :
	     int n;
	     int biao;
	     int count;
	     Node* next;
	     Node(int a)
	     {
	      	      n = a;
	      	      biao = 0;
	      	      count = 0;
	      	      next = NULL;
		}
		
		Node(int a,int b,int c)
		{
		 	 n = a;
		 	 biao = b;
		 	 count = c;
		 	 next = NULL;
			 }
		
		Node()
		{
		 	n = 0;
		 	biao = 0;
		 	count = 0;
		 	next = NULL;
			}
		
	bool equals(Node b)
	{
	     if(this->n!=b.n)
   		 return false;
	     else if(this->biao!=b.biao)
	     	  return false;
             return true;		 
	}	      
};

class Hash
{	
     public:     	  
      Node table[2200];
      
      Hash()
      {
       	  for(int i=0;i<2200;i++)
		 table[i] = Node(-2);  	       
      }
      
      void add(Node &s)
      {
       	  int addr = hash(s);
       	  Node* temp = &table[addr];
	if(temp->n==0)
		table[addr] = s;      
	else{	       
		   while(temp->next!=NULL)
		   {
			  temp = temp->next;
		   
			}
	        Node* tt = new Node(s.n,s.biao,s.count);
		temp->next = tt;
		temp->next->next = NULL;
	    }
       } 
       int hash(Node a)
       {
  	  int re = 0;
       	  int b = a.n;
       	  int i = 1;
	  while(a.n>0)
	  {
   	   	re = re + (a.n%10)*i;
		a.n = a.n/10;
		i++;        
	    } 	    
       	   return re*(a.biao+1)+b/1000;	    
	}
		    
		    
 	Node find(Node s)
	 {  
	    int addr = hash(s);
	    Node* p = &table[addr];
	    while(p!=NULL)
	    {	
	     	if(s.equals(*p))
	    		return *p;		
       		p = p ->next;	
			    }		       
	    return Node(-1);				    
			    }
			    
	void del(Node &s)
	{
 	     int addr = hash(s);
 	     Node* p = &table[addr];
 	     Node* q = table[addr].next;
 	     
 	     if((*p).equals(s))
 	     {
		     if(p->next==NULL)
		     	{
			   p->n =0;	      
			}
			else
			{
			   table[addr] = *(table[addr].next); 
			}	      
             }	     
 	     else{		     
	 	     while(p->next!=NULL)
	 	     {	
    			 Node* current = p->next;
		      	if(s.equals(*(p->next)))
		    	{	
				Node* q = p->next->next;
				current = p->next;
			 	p->next = q;
			}		
	       		p = current;
		}	   
	    }
	 }	    
};


void toArray(int a,int b[])
{
     for(int i=5;i>=0;i--)
     {
      	     b[i] = a%10;
	     a = a/10;
     }     		 
}

int toNum(int b[])
{	
     int a = 0;	
     for(int i=0;i<6;i++)
     {
      	  a = a*10 +b[i];        
     }	
     return a;     	         	       
} 
class Memo
{
      public:
      	  int a[10];
	  int top;
	  Memo()
	  {
	   	for(int i=0;i<10;i++)
		   	a[i]=-1;
		top = 0;	  
		  }
	 bool find(int n)
      	  {
	       	 for(int i=0;i<top;i++)
	       {
	       	       if(a[i]==n)
	       	       		   return 1;
	       }
	       	return 0;
	}
		  	  
	  void insert(int n)
	  {	
	      if(!this->find(n))
	            a[top++] = n;	       		  
	  }   		      	  
      	 bool allMore(int n)
	 {
	      for(int i=0;i<top;i++)
	      {
	       	      if(n<=a[i])
	       	      		 return 0;
		      } 
		return 1;      		 
	 }
	  bool allLess(int n)
	 {
	      for(int i=0;i<top;i++)
	      {
	       	      if(n>=a[i])
	       	      		 return 0;
		      } 
		return 1;      		 
	 }	
};

Node done(Node s,int c)
{
     	       int s1[6];
     	       for(int i=0;i<6;i++)
     	       {
	       	     s1[i] = 0;  
		       }
     	       toArray(s.n,s1);
		if(c==0){
			int temp = s1[0];
			s1[0] = s1[s.biao];
			s1[s.biao] = temp;
		}
		else if(c==1){
			int temp = s1[5];
			s1[5] = s1[s.biao];
			s1[s.biao] = temp;
		}
		else if(c==2){
			if(s1[s.biao]>=9);
			else	
			
				s1[s.biao] ++;
				
		}
		else if(c==3){
			if(s1[s.biao]<=0);
			else
			
				s1[s.biao] --;
				
		}
		else if(c==4){
			if(s.biao==0);
			else s.biao--;
		}
		else if(c==5){
			if(s.biao==5);
			else s.biao++;
		}
		s.n = toNum(s1);
		return s;
	}
	
	bool check(queue<int> a,int biao)
	{
	     while(a.size()!=0)
	     {
	      	if(a.front()==biao)
		      return true;
		 a.pop();
		 }
		 return false;	 	     		      
				      	     		      
	}
	
	Node find(queue<Node> mq,Node a)
	{
 	     while(mq.size()!=0)
 	     {
	       if((mq.front()).equals(a))
	       		return mq.front();
		mq.pop();   			
	     }
	     Node ceng(-1);
	     return ceng;
	}

int search(Node a,Node b)
{
    	if(a.n==b.n&&a.biao==b.biao)
	    return 0;	
        queue<Node>  q1;
	queue<Node>  q2;
	Node ceng(-1);
	q1.push(a);
	q1.push(ceng);
	q2.push(b);
	q2.push(ceng);
	Node ew1 ;
	Node ew2 ;
	int count1 = 0;
	int count2 = 0;
	Hash t1;
	Hash t2;
	t1.add(a);
	t2.add(b);
	Memo memo1;
	Memo memo2;
	int array1[6] ;
	int array2[6] ;
	for(int i=0;i<6;i++)
	{
	 	array1[i] = 0;
		 array2[i] = 0;	
		}
	toArray(a.n,array1);
	
	toArray(b.n,array2);
	
	for(int i=0;i<6;i++)
	{
	 	memo1.insert(array1[i]);	
	 	memo2.insert(array2[i]);
		}
	
	while(true)
	{
                if(q1.size()!=0){
	 	   ew1 = q1.front();
		    q1.pop();	       	       		          
		    if(ew1.equals(ceng))
		    {
		     	q1.push(ceng);
		     	count1++;
			 ew1 = q1.front();
			 q1.pop();	
                	}
                	 
                	 
        	for(int i=0;i<6;i++)
        	{			 		 
			int s11[6];
			toArray(ew1.n,s11);
			
			if(!memo2.find(s11[ew1.biao])&&(i==0||i==1||i==4||i==5))
				continue;						
			if(memo2.allMore(s11[ew1.biao])&&i==2)
				continue;
			if(memo2.allLess(s11[ew1.biao])&&i==3)
				continue;
							      
			Node ew = ew1;
			ew = done(ew,i);
			
			Node temp = t2.find(ew);
			if(!temp.equals(ceng)){
					  
				return ew.count + temp.count + 1;
			}
		
			if(ew.equals(t1.find(ew)))
				continue;	      	      
			
			ew.count = count1 + 1;
	
			q1.push(ew);
	 		t1.add(ew);
		 	
		}
		}		
		
		if(q2.size()!=0){		
            ew2 = q2.front();
	    q2.pop();   
	    if(ew2.equals(ceng))
	    {
	     	q2.push(ceng);
	     	count2++;
		 ew2 = q2.front();
		 q2.pop();		
        	}
        
		for(int i=0;i<6;i++)
		{	       				
			int s22[6];
			toArray(ew2.n,s22);
			
			if(!memo1.find(s22[ew2.biao])&&(i==0||i==1||i==4||i==5))
				continue;
			if(memo1.allMore(s22[ew2.biao])&&i==2)
				continue;
			if(memo1.allLess(s22[ew2.biao])&&i==3)
				continue;
				
			Node ew = ew2;						
			ew = done(ew,i);
				
		
			Node temp = t1.find(ew);
			if(!temp.equals(ceng)){
				return ew.count + temp.count + 1;
			}	
		
			if(ew.equals(t2.find(ew)))
			 	continue;		
					
			ew.count = count2 + 1;
	
			q2.push(ew);
			t2.add(ew);			 	
		}		
			
			}   
	}     
         
}

int main()
{ 
    int a,b;
     while ( cin >> a >> b){
    

    Node s1(a);
    Node s2(b);
    int count = search(a,b);
   
    for(int i=1;i<6;i++)
    {
     	 s2 = Node(b,i,0);
     	 
	 int count1 = search(a,s2);
	 if(count>count1)
	 	count = count1;   	        
    }
    
    cout<<count<<endl;
}

    return 0;
}

Followed by:

Re:谁能帮我找条错误数据啊，我自测得好像是对的啊，一直RA(写的比较差) (21) 66xzx 2012-03-27 22:13:02

Post your reply here:

User ID:
Password:
Title:

Content:

> #include <cstdlib>
> #include <iostream>
> #include <queue>
> 
> using namespace std;
> 
> class Node
> {
>      public :
> 	     int n;
> 	     int biao;
> 	     int count;
> 	     Node* next;
> 	     Node(int a)
> 	     {
> 	      	      n = a;
> 	      	      biao = 0;
> 	      	      count = 0;
> 	      	      next = NULL;
> 		}
> 		
> 		Node(int a,int b,int c)
> 		{
> 		 	 n = a;
> 		 	 biao = b;
> 		 	 count = c;
> 		 	 next = NULL;
> 			 }
> 		
> 		Node()
> 		{
> 		 	n = 0;
> 		 	biao = 0;
> 		 	count = 0;
> 		 	next = NULL;
> 			}
> 		
> 	bool equals(Node b)
> 	{
> 	     if(this->n!=b.n)
>    		 return false;
> 	     else if(this->biao!=b.biao)
> 	     	  return false;
>              return true;		 
> 	}	      
> };
> 
> class Hash
> {	
>      public:     	  
>       Node table[2200];
>       
>       Hash()
>       {
>        	  for(int i=0;i<2200;i++)
> 		 table[i] = Node(-2);  	       
>       }
>       
>       void add(Node &s)
>       {
>        	  int addr = hash(s);
>        	  Node* temp = &table[addr];
> 	if(temp->n==0)
> 		table[addr] = s;      
> 	else{	       
> 		   while(temp->next!=NULL)
> 		   {
> 			  temp = temp->next;
> 		   
> 			}
> 	        Node* tt = new Node(s.n,s.biao,s.count);
> 		temp->next = tt;
> 		temp->next->next = NULL;
> 	    }
>        } 
>        int hash(Node a)
>        {
>   	  int re = 0;
>        	  int b = a.n;
>        	  int i = 1;
> 	  while(a.n>0)
> 	  {
>    	   	re = re + (a.n%10)*i;
> 		a.n = a.n/10;
> 		i++;        
> 	    } 	    
>        	   return re*(a.biao+1)+b/1000;	    
> 	}
> 		    
> 		    
>  	Node find(Node s)
> 	 {  
> 	    int addr = hash(s);
> 	    Node* p = &table[addr];
> 	    while(p!=NULL)
> 	    {	
> 	     	if(s.equals(*p))
> 	    		return *p;		
>        		p = p ->next;	
> 			    }		       
> 	    return Node(-1);				    
> 			    }
> 			    
> 	void del(Node &s)
> 	{
>  	     int addr = hash(s);
>  	     Node* p = &table[addr];
>  	     Node* q = table[addr].next;
>  	     
>  	     if((*p).equals(s))
>  	     {
> 		     if(p->next==NULL)
> 		     	{
> 			   p->n =0;	      
> 			}
> 			else
> 			{
> 			   table[addr] = *(table[addr].next); 
> 			}	      
>              }	     
>  	     else{		     
> 	 	     while(p->next!=NULL)
> 	 	     {	
>     			 Node* current = p->next;
> 		      	if(s.equals(*(p->next)))
> 		    	{	
> 				Node* q = p->next->next;
> 				current = p->next;
> 			 	p->next = q;
> 			}		
> 	       		p = current;
> 		}	   
> 	    }
> 	 }	    
> };
> 
> 
> void toArray(int a,int b[])
> {
>      for(int i=5;i>=0;i--)
>      {
>       	     b[i] = a%10;
> 	     a = a/10;
>      }     		 
> }
> 
> int toNum(int b[])
> {	
>      int a = 0;	
>      for(int i=0;i<6;i++)
>      {
>       	  a = a*10 +b[i];        
>      }	
>      return a;     	         	       
> } 
> class Memo
> {
>       public:
>       	  int a[10];
> 	  int top;
> 	  Memo()
> 	  {
> 	   	for(int i=0;i<10;i++)
> 		   	a[i]=-1;
> 		top = 0;	  
> 		  }
> 	 bool find(int n)
>       	  {
> 	       	 for(int i=0;i<top;i++)
> 	       {
> 	       	       if(a[i]==n)
> 	       	       		   return 1;
> 	       }
> 	       	return 0;
> 	}
> 		  	  
> 	  void insert(int n)
> 	  {	
> 	      if(!this->find(n))
> 	            a[top++] = n;	       		  
> 	  }   		      	  
>       	 bool allMore(int n)
> 	 {
> 	      for(int i=0;i<top;i++)
> 	      {
> 	       	      if(n<=a[i])
> 	       	      		 return 0;
> 		      } 
> 		return 1;      		 
> 	 }
> 	  bool allLess(int n)
> 	 {
> 	      for(int i=0;i<top;i++)
> 	      {
> 	       	      if(n>=a[i])
> 	       	      		 return 0;
> 		      } 
> 		return 1;      		 
> 	 }	
> };
> 
> Node done(Node s,int c)
> {
>      	       int s1[6];
>      	       for(int i=0;i<6;i++)
>      	       {
> 	       	     s1[i] = 0;  
> 		       }
>      	       toArray(s.n,s1);
> 		if(c==0){
> 			int temp = s1[0];
> 			s1[0] = s1[s.biao];
> 			s1[s.biao] = temp;
> 		}
> 		else if(c==1){
> 			int temp = s1[5];
> 			s1[5] = s1[s.biao];
> 			s1[s.biao] = temp;
> 		}
> 		else if(c==2){
> 			if(s1[s.biao]>=9);
> 			else	
> 			
> 				s1[s.biao] ++;
> 				
> 		}
> 		else if(c==3){
> 			if(s1[s.biao]<=0);
> 			else
> 			
> 				s1[s.biao] --;
> 				
> 		}
> 		else if(c==4){
> 			if(s.biao==0);
> 			else s.biao--;
> 		}
> 		else if(c==5){
> 			if(s.biao==5);
> 			else s.biao++;
> 		}
> 		s.n = toNum(s1);
> 		return s;
> 	}
> 	
> 	bool check(queue<int> a,int biao)
> 	{
> 	     while(a.size()!=0)
> 	     {
> 	      	if(a.front()==biao)
> 		      return true;
> 		 a.pop();
> 		 }
> 		 return false;	 	     		      
> 				      	     		      
> 	}
> 	
> 	Node find(queue<Node> mq,Node a)
> 	{
>  	     while(mq.size()!=0)
>  	     {
> 	       if((mq.front()).equals(a))
> 	       		return mq.front();
> 		mq.pop();   			
> 	     }
> 	     Node ceng(-1);
> 	     return ceng;
> 	}
> 
> int search(Node a,Node b)
> {
>     	if(a.n==b.n&&a.biao==b.biao)
> 	    return 0;	
>         queue<Node>  q1;
> 	queue<Node>  q2;
> 	Node ceng(-1);
> 	q1.push(a);
> 	q1.push(ceng);
> 	q2.push(b);
> 	q2.push(ceng);
> 	Node ew1 ;
> 	Node ew2 ;
> 	int count1 = 0;
> 	int count2 = 0;
> 	Hash t1;
> 	Hash t2;
> 	t1.add(a);
> 	t2.add(b);
> 	Memo memo1;
> 	Memo memo2;
> 	int array1[6] ;
> 	int array2[6] ;
> 	for(int i=0;i<6;i++)
> 	{
> 	 	array1[i] = 0;
> 		 array2[i] = 0;	
> 		}
> 	toArray(a.n,array1);
> 	
> 	toArray(b.n,array2);
> 	
> 	for(int i=0;i<6;i++)
> 	{
> 	 	memo1.insert(array1[i]);	
> 	 	memo2.insert(array2[i]);
> 		}
> 	
> 	while(true)
> 	{
>                 if(q1.size()!=0){
> 	 	   ew1 = q1.front();
> 		    q1.pop();	       	       		          
> 		    if(ew1.equals(ceng))
> 		    {
> 		     	q1.push(ceng);
> 		     	count1++;
> 			 ew1 = q1.front();
> 			 q1.pop();	
>                 	}
>                 	 
>                 	 
>         	for(int i=0;i<6;i++)
>         	{			 		 
> 			int s11[6];
> 			toArray(ew1.n,s11);
> 			
> 			if(!memo2.find(s11[ew1.biao])&&(i==0||i==1||i==4||i==5))
> 				continue;						
> 			if(memo2.allMore(s11[ew1.biao])&&i==2)
> 				continue;
> 			if(memo2.allLess(s11[ew1.biao])&&i==3)
> 				continue;
> 							      
> 			Node ew = ew1;
> 			ew = done(ew,i);
> 			
> 			Node temp = t2.find(ew);
> 			if(!temp.equals(ceng)){
> 					  
> 				return ew.count + temp.count + 1;
> 			}
> 		
> 			if(ew.equals(t1.find(ew)))
> 				continue;	      	      
> 			
> 			ew.count = count1 + 1;
> 	
> 			q1.push(ew);
> 	 		t1.add(ew);
> 		 	
> 		}
> 		}		
> 		
> 		if(q2.size()!=0){		
>             ew2 = q2.front();
> 	    q2.pop();   
> 	    if(ew2.equals(ceng))
> 	    {
> 	     	q2.push(ceng);
> 	     	count2++;
> 		 ew2 = q2.front();
> 		 q2.pop();		
>         	}
>         
> 		for(int i=0;i<6;i++)
> 		{	       				
> 			int s22[6];
> 			toArray(ew2.n,s22);
> 			
> 			if(!memo1.find(s22[ew2.biao])&&(i==0||i==1||i==4||i==5))
> 				continue;
> 			if(memo1.allMore(s22[ew2.biao])&&i==2)
> 				continue;
> 			if(memo1.allLess(s22[ew2.biao])&&i==3)
> 				continue;
> 				
> 			Node ew = ew2;						
> 			ew = done(ew,i);
> 				
> 		
> 			Node temp = t1.find(ew);
> 			if(!temp.equals(ceng)){
> 				return ew.count + temp.count + 1;
> 			}	
> 		
> 			if(ew.equals(t2.find(ew)))
> 			 	continue;		
> 					
> 			ew.count = count2 + 1;
> 	
> 			q2.push(ew);
> 			t2.add(ew);			 	
> 		}		
> 			
> 			}   
> 	}     
>          
> }
> 
> int main()
> { 
>     int a,b;
>      while ( cin >> a >> b){
>     
> 
>     Node s1(a);
>     Node s2(b);
>     int count = search(a,b);
>    
>     for(int i=1;i<6;i++)
>     {
>      	 s2 = Node(b,i,0);
>      	 
> 	 int count1 = search(a,s2);
> 	 if(count>count1)
> 	 	count = count1;   	        
>     }
>     
>     cout<<count<<endl;
> }
> 
>     return 0;
> }

Home Page Go Back To top