杭电5464 DZY Loves Partition

Love The Way You Lie 2022-07-27 13:52 121阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5646][http_acm.hdu.edu.cn_showproblem.php_pid_5646]

题目大意：  
给你一个数n，问是否能把n拆成K个不相同的正整数之和，若能输出k个数的乘积，若不能输出-1。

解题思路：  
先说输出-1的情况，如果从1加到k都大于n，那就肯定没有解，反之肯定有解。  
因为相等的乘积最大，但是又不能相等，答案肯定是尽量从中间连续。  
当找出中间值n/k后，我们要向两边进行扩展k-1个数。  
如果k-1为偶数的话，只需从h1=n/k-(k-1)/2扩展到h2=n/k+(k-1)/2即可，但是从h1加到h2可能有的数会没有加完，就是还剩p=n-（h1到h2的和）这么大的数，因为是连续的，于是我们从最大的数向前总共p个数，每个数加1（不会加完全部数）  
奇数的就进行判断，如果1.0\*n/k-n/k<0.5就向右扩展k-1/2个，向左扩展k/2个，如果》0.5就扩向右扩展k/2个，向左扩展k-1/2个，扩展后的操作同上。

代码如下：

#include <vector>
    #include <list>
    #include <map>
    #include <set>
    #include <deque>
    #include <queue>
    #include <stack>
    #include <bitset>
    #include <algorithm>
    #include <functional>
    #include <numeric>
    #include <utility>
    #include <sstream>
    #include <iostream>
    #include <iomanip>
    #include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <cstring>
    #include <ctime>
    #include <cassert>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define Cl0(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9+7;
    const int inf1=-1*1e9;
    typedef long long LL;
    
    int main()
    {
        int t;
        RI(t);
        while(t--)
        {
            LL  n,k;
            scanf("%lld %lld",&n,&k);
            long long int ans=1;
            if(1.0*(1+k)/2*k>n)
            {
                cout<<-1<<endl;
                continue;
            }
            else
            {
                LL p,s,e,mid=n/k,k1=k-1;
                if(k1%2==0)
                {
                    LL k2=k1/2;
                    LL x=mid*k;
                    p=n-x;
                    s=mid-k2;
                    e=mid+k2;
                }
                else
                {
                    if(1.0*n/k-n/k>=0.5)
                    {
                        LL x=(2*mid+1)*k/2;
                        p=n-x;
                        s=mid-k1/2;
                        e=mid+k1/2+1;
                    }
                    else
                    {
                        LL x=(mid*2-1)*k/2;
                        p=n-x;
                        s=mid-k1/2-1;
                        e=mid+k1/2;
                    }
    
                }
                for(LL i=s; i<=e; i++)
                {
                    if(i+p>e) ans=(ans*(i+1))%inf;
                    else ans=(ans*(i))%inf;
                }
            }
    
    
            cout<<ans<<endl;
        }
    
    
    
        return  0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5646]: http://acm.hdu.edu.cn/showproblem.php?pid=5646