国际大学生程序设计竞赛例题_5.18最长数列

1,题意
给出n个数,让你利用这些书构造出一个最长的生成序列.
要求序列是一个等差数列或等比数列或等幂数列
2,解答
3,代码

#include <iostream>
#include <map>
using namespace std;

typedef long long LL;

map<LL,int> m; //保存元素
LL d[100]; //输入序列
int cnt;//测试数
int n;//元素个数
int ans;//记录序列长度

bool in_range(LL a,int k) //检查a^k是否在[-2^31 2^31)之间
{
    LL ret=1;
    while(k--)
    {
        ret*=a;
        if(ret>0x7fffffff||-ret>0x8fffffff)
            return false;
    }
    return true;
}

LL power(LL a,int k) //求a^k
{
    LL ret=1;
    while(k--) ret*=a;
    return ret;
}

void findNum(LL a,int k,int st)
{
    int l=0; //记录当前长度
    switch(st)
    {
    case 1: //寻找等差数列
        for(LL i=a;;i+=k)
        {
            //这个元素存在,序列长度增加
            if(m[i]) m[i]--,l++;
            else break;
        }
        if(l>ans) ans=l;
        for(int i=a;l;i+=k)
        {
            m[i]++;
            l--;
        }
        break;
    case 2: //寻找等比数列
        for(LL i=a;;i*=k)
        {
            //这个元素存在,序列长度增加
            if(m[i]) m[i]--,l++;
            else break;
        }
        if(l>ans) ans=l;
        for(int i=a;l;i*=k)
        {
            m[i]++;
            l--;
        }
        break;
    case 3: //寻找等幂序列
        //注意这里的处理
        for(LL i=a;;i=power(i,k))
        {
            //这个元素存在,序列长度增加
            if(m[i]) m[i]--,l++;
            else break;
            if(!in_range(i,k)) break;
        }
        if(l>ans) ans=l;
        for(int i=a;l;i=power(i,k))
        {
            m[i]++;
            l--;
        }
        break;
    }
}



int main()
{
    freopen("5.18.in","r",stdin);
    cin>>cnt;
    while(cnt--)
    {
        cin>>n;
        ans=1;//长度至少为1
        m.clear();
        for(int i=0;i<n;i++)
        {
            cin>>d[i];
            m[d[i]]++;
        }
        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) //取出任意两个数
            {
                if(i!=j)
                {
                    findNum(d[i],d[j]-d[i],1); //找出最长的等差数列
                    //找等比数列,保证d[i]!=0,且可以整除
                    if( d[i]&&d[j]%d[i]==0 )
                        findNum(d[i],d[j]/d[i],2);
                    //找等幂序列,分好几种情况
                    switch(d[i])
                    {
                    case 0:
                        if(d[j]==0) //只能取0
                            findNum(0,1,3);
                        break;
                    case 1:
                        if(d[j]==1) //只能取1
                            findNum(1,1,3);
                        break;
                    case -1:
                        if(d[j]==-1) //k为奇数
                            findNum(-1,1,3);
                        if(d[j]==1) //k为偶数
                            findNum(-1,0,3);
                        break;
                    default:
                        for(int k=0;in_range(d[i],k);k++)
                        {
                            LL f=power(d[i],k);
                            if(f>abs(d[j])) break; //该元素不存在
                            else if(f==d[j]) //找到了当前的k
                            {
                                findNum(d[i],k,3);
                                break;
                            }
                        }

                    }
                }
            }
        cout<<ans<<endl;
    }
    return 0;
}