题目地址：HDU 5312
题意：Soda习得了一个数列, 数列的第nn (n \ge 1)(n≥1)项是3n(n-1)+13n(n1)+1. 现在他想知道对于一个给定的整数mm, 是否可以表示成若干项上述数列的和. 如果可以, 那么需要的最小项数是多少?例如, 22可以表示为7+7+7+17+7+7+1, 也可以表示为19+1+1+119+1+1+1.
思路：
三角形数形如n*(n-1)/2，他们形成的数列是1，3，6，10…….，同样也可以表示成n*(n+1)/2(表示方式不同)。
性质：任何一个正整数最多用三个三角形数就可以表示出来。
然后这道题的第n个数为3*n*(n-1)+1，所以可以表示成6*(n-1)*n/2+1,假设最少需要k个三角形数，设第i个三角形数为Ai，所以m=6*(A1+A2+A3+…..+AK)+k,所以当k>=3时，只需要判断一下（m-k）%6是不是等于0就可以了。然后当k=1和k=2的时候特判一下就好了。。
#include <stdio.h>#include <math.h>#include <string.h>#include <stdlib.h>#include <iostream>#include <sstream>#include <algorithm>#include <set>#include <queue>#include <stack>#include <map>//#pragma comment(linker, "/STACK:102400000,102400000")using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const double pi= acos(-1.0);const double esp=1e-6;int maxn=1e9;int a[100010];int n;int cnt1(int m){for(int i=1;i<=n;i++){if(a[i]==m)return 1;}return 0;}int cnt2(int m){int i;int j=n;for(i=1;i<n&&a[i]<m;i++){while(a[i]+a[j]>m)j–;if(a[i]+a[j]==m)return 1;}return 0;}int main(){int T,m,i;memset(a,0,sizeof(a));for(int i=1;;i++){a[i]=3*i*(i-1)+1;if(a[i]>maxn){n=i;break;}}scanf("%d",&T);while(T–){scanf("%d",&m);if(cnt1(m)){puts("1");continue;}else if(cnt2(m)){puts("2");continue;}else{for(i=3;i<=n;i++){if((m-i)%6==0){printf("%d\n",i);break;}}}}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
有些人注定是等待别人的，有些人是注定被人等的。
