hdu 5312 Sequence(三角形数)-白红宇

hdu 5312 Sequence(三角形数)

阅读量：6408 次

发布时间：2019-06-23

本文共 2553 字，大约阅读时间需要 8 分钟。

题意：通式为3*i*(i-1)+1(n>=1)的数列中每个数可用若干次，求构成给定n所需的最小个数；

思路：

设构成n所需个数为x,则n=3*1*(1-1)+3*2*(2-1)+...+3*x*(x-1)+x;当时推到这一步就没有再做下去了；

n*(n-1)/2或n*(n+1)/2形式表示的数为三角形数；

然后整理得n=6*(sigma((i*(i-1)/2))+x（i*(i-1)为偶数）;

也就是说n%6即为所求结果，当n%6=1,2时特判一下是否能找到满足条件的数；

二分查找：（手动二分）(STL二分)

#include
     
      #include
      
       #include
       
        using namespace std;int t,n,m,mark;int num[500010];void pre(){    for(int i=1;i<20000;i++){       num[i]=3*i*(i-1)+1;    }}/*int seek(int x){    int k=lower_bound(num,num+20000,x)-num;    return num[k]==x;}*/int seek(int x){    int l=0,r=20000;    while(l<=r)    {        int mid=(l+r)/2;        if(num[mid]==x) return 1;        else if(num[mid]
        
         x) r=mid-1;    }    return 0;}int main(){    int i,j,k,temp;    pre();    while(scanf("%d",&t)!=EOF)    {        while(t--)        {            scanf("%d",&n);            temp=(n-1)%6+1;            mark=0;            if(temp>2) printf("%d\n",temp);            else{                if(temp==1){                    if(seek(n)) printf("1\n");                    else printf("7\n");                    continue;                }                else{                    for(i=1;num[i]*2<=n;i++){                       if(seek(n-num[i])){                           mark=1;break;                       }                    }                    if(mark) printf("2\n");                    else printf("8\n");                }            }        }    }    return 0;}

STL中map映射:

#include
     
      #include
      
       #include
       #include
        
         using namespace std;int t,n,m,mark;int num[500010];map
         
           mm;void pre(){    for(int i=1;i<20000;i++){       num[i]=3*i*(i-1)+1;       mm[num[i]]=i;    }}int main(){    int i,j,k,temp;    pre();    while(scanf("%d",&t)!=EOF)    {        while(t--)        {            scanf("%d",&n);            temp=(n-1)%6+1;            mark=0;            if(temp>2) printf("%d\n",temp);            else{                if(temp==1){                    if(mm.count(n)) printf("1\n");                    else printf("7\n");                    continue;                }                else{                    for(i=1;num[i]*2<=n;i++){                       if(mm.count(n-num[i])){                           mark=1;break;                       }                    }                    if(mark) printf("2\n");                    else printf("8\n");                }            }        }    }    return 0;}