(BC 一周年) hdu 5312 Sequence
比赛的时候没做出来.这道题需要用到的一个重要的性质是,任意一个自然数可以表示成至多三个三角形数(1,3,6,10,15.....)的和(orz高斯)然后也有推广到任意自然数可以表示成k个k角形数的和的结论(费马提出了猜想,柯西给了证明)然后官方题解说的比较好:
**这个题看上去是一个贪心, 但是这个贪心显然是错的. 事实上这道题目很简单, 先判断1个是否可以, 然后判断2个是否可以. 之后找到最小的k (k > 2)k(k>2), 使得(m - k) mod 6 = 0(m−k)mod6=0即可.**证明如下: 3n(n-1)+1 = 6(n(n-1)/2)+13n(n−1)+1=6(n∗(n−1)/2)+1, 注意到n(n-1)/2n∗(n−1)/2是三角形数, 任意一个自然数最多只需要3个三角形数即可表示. 枚举需要kk个, 那么显然m=6(km=6(k个三角形数的和)+k)+k, 由于k ge 3k≥3, 只要m-km−k是6的倍数就一定是有解的.**
事实上, 打个表应该也能发现规律.
另外还有一点,特判一个和两个的情况时,一个的好判断,扫一遍就好了
两个的话,由于这个数列是递增的,我们可以从两边往中间,算是一个不错的优化,具体见代码.
1 /*************************************************************************
2 > File Name: code/nv/#ann/1003.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年07月28日 星期二 23时03分09秒
6 ************************************************************************/
7
8 #include<iostream>
9 #include<iomanip>
10 #include<cstdio>
11 #include<algorithm>
12 #include<cmath>
13 #include<cstring>
14 #include<string>
15 #include<map>
16 #include<set>
17 #include<queue>
18 #include<vector>
19 #include<stack>
20 #define y0 abc111qqz
21 #define y1 hust111qqz
22 #define yn hez111qqz
23 #define j1 cute111qqz
24 #define tm crazy111qqz
25 #define lr dying111qqz
26 using namespace std;
27 #define REP(i, n) for (int i=0;i<int(n);++i)
28 typedef long long LL;
29 typedef unsigned long long ULL;
30 const int inf = 0x7fffffff;
31 const int N=1E5+7;
32 int k,m,f[N];
33 void init()
34 {
35 for ( int i = 1 ; i <N; i++)
36 {
37 f[i]=3*i*(i-1)+1;
38 if (f[i]>1000000000)
39 {
40 k = i-1;
41 break;
42 }
43 }
44 }
45 int solve (int x)
46 {
47 for ( int i = 1 ; f[i]<=x ; i++ )
48 {
49 if (x==f[i])
50 return 1;
51 }
52 int j = k;
53 for ( int i = 1 ; i <= k-1&&f[i]<x ; i++)
54 {
55 while(f[i]+f[j]>x) j--;
56 if (f[i]+f[j]==x) return 2;
57 }
58 for ( int i = 3 ; i <= m ; i++ )
59 {
60 if ((m-i)%6==0)
61 return i;
62 }
63 }
64 int main()
65 {
66 int T;
67 init();
68 cin>>T;
69 int ans;
70 while (T--)
71 {
72
73 scanf("%d",&m);
74 cout<<solve(m)<<endl;
75
76 }
77
78 return 0;
79 }
80
81
82