HDOJ 3784

￡神魔★判官ぃ 2022-04-10 14:09 163阅读 0赞

# 继续xxx定律 #

**Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 1238 Accepted Submission(s): 341**

Problem Description

当n为3时，我们在验证xxx定律的过程中会得到一个序列，3，5，8，4，2，1，将3称为关键数，5，8，4，2称为覆盖数。现在输入n个数字a\[i\]，根据关键数与覆盖数的理论，我们只需要验证其中部分数就可以确定所有数满足xxx定律，输出输入的n个数中的关键数。如果其中有多个关键数的话按照其输入顺序的逆序输出。

Input

输入数据包含多个用例,每个用例首先包含一个整数n，然后接下来一行有n个整数a\[i\]，其中:  
1<=n<=500  
1<a\[i\]<=1000

Output

请计算并输出数组a中包含的关键数，并按照其输入顺序的逆序输出,每个用例输出占一行。

Sample Input

3 3 8 4 5 3 8 4 7 15 5 3 8 4 15 7 0

Sample Output

3 15 7 3 7 15 3

#include<stdio.h>
    int a[505],vis[505];
    int main()
    {
    	int n,temp;int i,j;int flag;
    	while(scanf("%d",&n),n)
    	{
    		{
    			for(i=1;i<=n;i++)
    				{
    					scanf("%d",a+i);
    					/*
    					默认为关键数
    					*/ 
    					vis[i]=1;
    				}
    			for(i=1;i<=n;i++)
    			{
    				temp=a[i];
    				while(temp!=1)
    				{
    					if(temp&1)
    					{
    						temp=3*temp+1;
    						temp>>=1;
    					}
    					else
    					 	temp>>=1;
    				for(j=1;j<=n;j++)
    				if(temp==a[j])
    					vis[j]=0;
    				}
    			}
    		}
    		flag=1;
    		/*
            若是直接输
            for(i=n;i>=1;i--)
                if(mark[i]==0)
                printf("%d ",num[i]);
            肯定PE，因为最后多输出一个空格
            而且不知道最后一个是谁，不能
            for(i=n;i>=1;i--)
            printf("%d ",);
            printf("%d\n")
    		*/ 
    		for(i=n;i>=1;i--)
    		if(1==vis[i])
    		{
    			if(1==flag)
    			{
    				printf("%d",a[i]);
    				flag=0;
    			}
    			else 
    				printf(" %d",a[i]);
    		}
    		printf("\n"); 				
    	}
    	return 0;
    }