HDU 5312 Sequence (规律题)

题意：

　　一个序列的第n项为3*n*(n-1)+1，而 n>=1，现在给一个正整数m，问其最少由多少个序列中的数组成？

思路：

　　首先，序列第1项是1，所以任何数都能构成了。但是最少应该是多少？对式子进行变形，6*(n*(n-1)/2)+1，看到了三角形数n*(n-1)/2，那么应该是6*（任意自然数）+x=m才对，因为最多只要3个三角形数就能组成任何自然数啦。

　　不妨试试m%6是多少？这样试图求x可以吗？因为任意自然数最多由3个组成，如果是k个，那么应该x>=k，别忘了还有个+1的项。x-k那部分，就只能由1来搞定了。

　　还有个前提，m%6=0怎么办？总不能由0个组成吧？那应该起码是1，所以(m-1)%6可以保证不为0。试试看m=13，则x=(13-1)%6+1=1，这样就真的能由1个序列中的数构成吗？序是1，7，19...好像没有。。。悲剧！应该是7+1+1+1+1+1+1才是，那6个1是补上去的。同理x=2也是需要保证序列中有两个数字能组成m才行，否则要x+=6才是答案。而3及以上就不用了，为什么我也不知道。。。

 #include <bits/stdc++.h>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x7f7f7f7f

 using namespace std;

 const int N=;

 unordered_map<int,int> mapp;

 vector<int > seq;

 void pre_cal()

 {

     int t=;

     for(int i=; i<&&t<=; i++)

     {

         t=*i*(i-)+;

         mapp[t]=;

         seq.push_back(t);

     }

 }

 bool cal(int m)

 {

     int q=, p=seq.size()-;

     while(q<=p)

     {

         int  t=seq[q]+seq[p];

         if(t==m)    return ;

         if(t>m) p--;

         else    q++;

     }

     return ;

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int t, m;

     pre_cal();

     cin>>t;

     while(t--)

     {

         scanf("%d",&m);

         int k=(m-)%+;//k是不会超过6的。但是答案可能超过6。

         if(k>=)    printf("%d\n",k);

         else if(k==)//特判

         {

             if(mapp[m]) printf("1\n");

             else    printf("%d\n",k+=);

         }

         else if(k==)//特判

         {

             if(cal(m))  printf("2\n");

             else printf("%d\n",k+=);

         }

     }

     return ;

 }

AC代码

巴特西

HDU 5312 Sequence (规律题)

最新文章

热门文章