首页 > ACM题库 > HDU-杭电 > HDU 3784-继续xxx定律[解题报告]HOJ
2015
04-11

HDU 3784-继续xxx定律[解题报告]HOJ

继续xxx定律

问题描述 :

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

输入:

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

输出:

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

样例输入:

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

样例输出:

3
15 7 3
7 15 3

解题思路:

1、先把输入的数据全部当做关键数,并求其覆盖数,如果其覆盖数在数组内,标记。

2、最后倒序输出没有标记的数即可。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int N=1100;
int main()
{
    int n,a[N],f[N],i,j;
    while(scanf("%d",&n),n)
    {
        memset(a,0,sizeof(a));
        memset(f,0,sizeof(f));
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            f[a[i]]=1;          //初始化标记 
        }
        for(i=0;i<n;i++)
        {
            if(f[a[i]]==0)    //如果已经存在不必再求,节省时间 
            continue;
            else
            j=a[i];
            while(j>1)
            {
                if(j%2==1)
                {
                    j=(j*3+1)/2;
                }
                else
                j=j/2;
                if(j<N)
                {
                    f[j]=0;    //将覆盖数标记 
                }
                
            }
            
        }j=0;
        for(i=n-1;i>=0;i--)
        {
            if(f[a[i]]&&j==1)
            printf(" %d",a[i]);       //倒序输出没有被标记的数,注意格式、 
            if(f[a[i]]&&j==0)
            {
                printf("%d",a[i]);
                j=1;
            }
            
        }
        printf("\n");
    }
    return 0; 
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/u014118737/article/details/38666087


  1. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.