首页 > 代码库 > 2016 ICPC大连站---F题 Detachment

2016 ICPC大连站---F题 Detachment

2024-08-16 23:22:57   219人阅读

 

题意：输入一个x，将x拆分成一些小的数（这些数不能相同，即x=a1+a2+......   ai!=aj when i!=j），然后这些数相乘得到一个成积(s=a1*a2*......)，求最大的乘积s；

思路：考虑最简单的做法便是贪心，很明显将一个数分的越小，这个乘积越大，那么对于给的x 先找2+3+4+....+n<=x 找到最大的n  如果和小于x ，那么将n右移一个数（n->n+1）  如果和还小于x继续将n-1右移......知道和x相等时，输出s   这样做时间复杂度很高，那么得优化。 由上面的过程分析发现，2+3+...+n<=x &&2+3+...+n+(n+1)>x

那么x-(2+3+...+n)<=n  那么最终x分成的数结果只有三种情况：x=2+3+...+(k-1)+(k+1)+...+n+(n+1)     x=3+4+...+n+(n+1)    x=3+4+...+(n-1)+n+(n+2)  

其实第一种和第二种情况相同。 分析过程如上，详细计算过程如下：2+3+...+n<=x  所以n*(n+1)<=2*x+2   n<=sqrt(2*n+2)  

代码如下：

#include <iostream>#include <algorithm>#include <cstdio>#include <cstring>#include <cmath>#include <bitset>using namespace std;typedef long long LL;const LL mod=1e9+7;const LL maxn=1e5+5;LL A[maxn],s[maxn];LL Inv[maxn];void getINV()///逆元;{    Inv[1]=1;    for(LL i=2; i<maxn; i++)        Inv[i] = (mod-mod/i)*Inv[mod%i]%mod;}void init(){    s[1]=0;    for(LL i=2;i<maxn;i++)       s[i]=s[i-1]+i;    A[0]=1;    for(LL i=1;i<maxn;i++)        A[i]=A[i-1]*i%mod;    getINV();}int main(){    init();    int T;    cin>>T;    while(T--)    {        int pos;        LL x,sum;        scanf("%lld",&x);        LL n=(LL)(sqrt(2*x+2));        for(int i=n;i>=1;i--)        if(s[i]<=x){            pos=i;            break;        }        if(x==1) { puts("1"); continue; }        if(s[pos]==x) { printf("%lld\n",A[pos]); continue; }        if(s[pos]+pos-1>=x){            LL tot=s[pos]+pos-1-x;            sum=(A[pos+1]*Inv[tot+2])%mod;        }        else{            LL tot=s[pos+1]-2+pos-1-x;            sum=((A[pos+2]*Inv[2])%mod)*Inv[tot+3]%mod;        }        printf("%lld\n",sum);    }    return 0;}

 

2016 ICPC大连站---F题 Detachment


联系
我们