hdu 5312 Sequence

柔情只为你懂 2022-08-02 19:59 155阅读 0赞

#

#

Sequence

Time Limit: 2000/2000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 878 Accepted Submission(s): 267

Problem Description

Today, Soda has learned a sequence whose n-th (n≥1) item is 3n(n−1)+1. Now he wants to know if an integer m can be represented as the sum of some items of that sequence. If possible, what are the minimum items needed?

For example, 22=19+1+1+1=7+7+7+1.

Input

There are multiple test cases. The first line of input contains an integer T (1≤T≤104), indicating the number of test cases. For each test case:

There’s a line containing an integer m (1≤m≤109).

Output

For each test case, output −1 if m cannot be represented as the sum of some items of that sequence, otherwise output the minimum items needed.

Sample Input

  1. 10
  2. 1
  3. 2
  4. 3
  5. 4
  6. 5
  7. 6
  8. 7
  9. 8
  10. 22
  11. 10

Sample Output

  1. 1
  2. 2
  3. 3
  4. 4
  5. 5
  6. 6
  7. 1
  8. 2
  9. 4
  10. 4

官方题解:

这个题看上去是一个贪心, 但是这个贪心显然是错的.事实上这道题目很简单, 先判断1个是否可以, 然后判断2个是否可以. 之后找到最小的k(k>2)k (k > 2)k(k>2), 使得(m−k)mod6=0(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)+13n(n−1)+1=6(n∗(n−1)/2)+1, 注意到n∗(n−1)/2n*(n-1)/2n∗(n−1)/2是三角形数, 任意一个自然数最多只需要3个三角形数即可表示. 枚举需要kkk个, 那么显然m=6(km=6(km=6(k个三角形数的和)+k)+k)+k, 由于k≥3k \ge 3k≥3, 只要m−km-km−k是6的倍数就一定是有解的.

事实上, 打个表应该也能发现规律.

尽然还用到三角形数。。看了之后枚举还是超时,,后来才懂原来是在枚举2的时候超时了,开始的做法是枚举每个数与n的差值,用二分找差值,如果存在就枚举成功,时间复杂度是nlogn,但是还是超时(T比较大)。后来想到原数列是有序的,所以从原数列中找两个数的和为n可以用线性的算法。设置两个指针 l 和r 一个指向最前面,一个指向最后面,l指针不断往后,r指针不断往前,由于是排序好的,两个指针都不需要回溯。所以比较快。

  1. #include<map>
  2. #include<vector>
  3. #include<cstdio>
  4. #include<iostream>
  5. #include<cstring>
  6. #include<string>
  7. #include<algorithm>
  8. #include<cmath>
  9. #include<stack>
  10. #include<queue>
  11. #include<set>
  12. #define inf 0x3f3f3f3f
  13. #define mem(a,x) memset(a,x,sizeof(a))
  14. using namespace std;
  15. typedef long long ll;
  16. typedef pair<int,int> pii;
  17. inline ll in()
  18. {
  19. ll res=0;char c;
  20. while((c=getchar())<'0' || c>'9');
  21. while(c>='0' && c<='9')res=res*10+c-'0',c=getchar();
  22. return res;
  23. }
  24. int a[20005];
  25. int main()
  26. {
  27. mem(a,0);
  28. for(int i=1;i<=20000;i++)
  29. {
  30. a[i]=3*i*(i-1)+1;
  31. }
  32. int T=in();
  33. while(T--)
  34. {
  35. int n=in();
  36. int pos=lower_bound(a+1,a+20000,n)-a;
  37. if(a[pos]==n) //枚举1
  38. {
  39. puts("1");
  40. continue;
  41. }
  42. int l=1,r=pos-1;
  43. bool ok=0;
  44. while(l<=r) //枚举2
  45. {
  46. while(a[l]+a[r]>n)r--;
  47. if(a[l]+a[r]==n)
  48. {
  49. ok=1;
  50. break;
  51. }
  52. ++l;
  53. }
  54. if(ok)
  55. {
  56. puts("2");
  57. continue;
  58. }
  59. for(int i=3;i<=8;i++)//枚举3-8
  60. {
  61. if((n-i)%6==0)
  62. {
  63. printf("%d\n",i);
  64. break;
  65. }
  66. }
  67. }
  68. return 0;
  69. }

发表评论

表情:
评论列表 (有 0 条评论,155人围观)

还没有评论,来说两句吧...

相关阅读

    相关 HDU 5297 Y sequence

    题意: 给定正整数n和r,定义Y数列为从正整数序列中删除所有能表示成a^b(2 ≤ b ≤ r)的数后的数列,求Y数列的第n个数是多少。例如n = 10, r = 3,则Y