本文主要是介绍HDU 2446 Shell Pyramid，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接~~>
做题感悟：这种题以前做过类似的题，但是在做这题时一直超内存，真心无语，后来才发现开一个数组就 ok了我傻傻的开了两个怪不得呢 ! 做完之后百度了一下原来还有更简单的方法不用开数组就可以了。
解题思路：1 ) 开数组。可以先打个表，把到前 i 个的和存到 f [ i ] 中，这样就可以用二分查找到 s 处于第几堆，然后再用一次二分查找在第几层。
2 ) 不开数组。 a1 =1, a2 = 3 , a3 = 6 , so ~ > an = (1+ n) * n / 2 ; 于是前 n 项和 Sn = a1+a2+a3……an = 1/2 *( 1*1+1 + 2*2 +2 +3*3+3 ……i * i + i ……n * n + n ) =
1/2 * ( 1^2 +2^2+3^2 …… i ^ 2 +n^2 + 1+2+3+4+5+……+ i + ……n ) = 1/2*( ∑n*n + ∑n ) = n*(n+1)*(n+2)/6 ;
公式：前n项和公式 = n * ( n + 1 ) / 2 ; 平方和公式：n * ( n+1 ) * ( 2*n+1 ) / 2 ; 立方和公式 ：[ n * ( n+1 ) / 2 ] ^ 2 ;
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
#define pret(a,b) memset(a,b,sizeof(a))
#define lld __int64
const double PI = 3.1415926535898 ;
const int INF = 99999999 ;
const double esp = 1e-7 ;// 精确到 7 位即可，8位超时
const lld md= 2810778 ;
const int MX = md+5 ;
lld binary_searchA(lld n)
{lld le=0,rt=md,mid,fx ;while(le<rt){mid=(le+rt)/2 ;fx=mid*(mid+1)*(mid+2)/6 ;if(fx==n) return mid ;else if(fx>n) rt=mid ;else le=mid+1 ;}return le ;
}
lld binary_searchB(lld n)
{lld le=0,rt=md,mid,fx ;while(le<rt){mid=(le+rt)/2 ;fx=mid*(mid+1)/2 ;if(fx==n) return mid ;else if(fx>n) rt=mid ;else le=mid+1 ;}return le ;
}
int main()
{lld Tx,n,y,cx ;scanf("%I64d",&Tx) ;while(Tx--){scanf("%I64d",&n) ;lld ax=binary_searchA(n) ; // 在第几堆if(ax*(ax+1)*(ax+2)/6==n)y=ax*(ax+1)/2 ;elsey=n-(ax-1)*ax*(ax+1)/6 ;lld bx=binary_searchB(y) ; // 第几层if(bx*(bx+1)/2==y)cx=bx ;elsecx=y-(bx-1)*bx/2 ;printf("%I64d %I64d %I64d\n",ax,bx,cx) ;}return 0 ;
}
代码（开数组）：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
#define pret(a,b) memset(a,b,sizeof(a))
#define lld __int64
const double PI = 3.1415926535898 ;
const int INF = 99999999 ;
const double esp = 1e-7 ;
const lld md= 2810778 ;
const int MX = md+5 ;
lld f[MX] ;
void init() // 打表
{lld p=2 ; f[1]=1 ; f[0]=0 ;for(int i=2 ;i<=md ;i++)f[i]=f[i-1]+p++ ;for(int i=1 ;i<=md ;i++)f[i]+=f[i-1] ;
}
lld binary_search(lld le,lld rt,lld n)
{lld mid ;while(le<rt){mid=(rt+le)/2 ;mid*(mid+1)/2 > n ? rt=mid : le=mid+1 ;}return le ;
}
int main()
{init() ;int Tx ;lld n,a,b,c,bx ;scanf("%d",&Tx) ;while(Tx--){scanf("%I64d",&n) ;lld x,y ;x=lower_bound(f,f+md,n)-f ;if(f[x]>n)x-- ;if(f[x]==n) // 判断在第几堆a=x ;else a=x+1 ;y=n-f[x] ;if(!y) y=f[x]-f[x-1] ; // 算出第几个数b=binary_search(0,md,y) ; // 计算第几层 b*(b+1) >=y ;if(b*(b+1)/2==y)bx=b ;else if(b*(b+1)/2>y) // 计算第几层{b-- ;if(b*(b+1)/2==y)bx=b ;elsebx=b+1 ;}c=y-bx*(bx-1)/2 ;printf("%I64d %I64d %I64d\n",a,bx,c) ;}return 0 ;
}
这篇关于HDU 2446 Shell Pyramid的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
