首页 > ACM题库 > HDU-杭电 > hdu 3758-factorial simplification-最小生成树-[解题报告]hoj
2015
04-10

hdu 3758-factorial simplification-最小生成树-[解题报告]hoj

Problem Description
Peter is working on a combinatorial problem. He has carried out quite lengthy derivations and got a resulting formula that is a ratio of two products of factorials like this:

This does not surprise Peter, since factorials appear quite often in various combinatorial formulae, because n! represents the number of transpositions of n elements – one of the basic combinatorial objects.
However, Peter might have made a mistake in his derivations. He knows that the result should be an integer number and he needs to check this first. For an integer result Peter wants to simplify this formula to get a better feeling of its actual combinatorial
significance. He wants to represent the same number as a product of factorials like this.



where all ri are distinct integer numbers greater than one in the descending order (ri > ri+1 > 1), si and t are positive integers. Among all the possible representations in this form, Peter is interested in one where r1 is
the largest possible number, among those in the one where s1 is the largest possible number; among those in the one where r2 is the largest possible number; among those in the one where s2 is the largest possible number; etc,
until the remaining t cannot be further represented in this form. Peter does not care about the actual value of t. He wants to know what is the factorial-product part of his result.
 

Input
The input begins with an integer T. The next T blocks each represents a case. The first line of each case contains two integer numbers n and m (1 ≤ n, m ≤ 1000). The second line contains n integer numbers pi (1 ≤ pi ≤ 10 000) separated
by spaces. The third line contains m integer numbers qi (1 ≤ qi ≤ 10 000) separated by spaces.
 

Output
For each case, on the first line of the output write a single integer number k. Write k = -1 if the ratio of the given factorial products is not an integer. Write k = 0 if the ratio is an integer but it cannot be represented in the
desired form. Write k > 0 followed by k lines if the ratio can be represented by a factorial product as described in the problem statement. On each of the following k lines write two integers ri and si (for i = 1 … k) separated by a space.
 

Sample Input
3 1 2 6 4 4 1 2 6 3 4 4 2 9 2 2 2 3 4
 

Sample Output
-1 0 2 7 1 2 2
 

Author
Andrey Stankevich
 

Source
 

Recommend
notonlysuccess

这题想要化简分子和分母都是阶乘之积,即第一幅图,然后形成第二幅图的形式,让r尽量大,不管t

预处理阶乘t中每个质数的幂,然后二分求每个r即可。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
using namespace std;

#define MAXN 10010

bool prime[MAXN+5];
int p[1400];
int up;
int num[1400];
int ans[MAXN][2];
vector <short> init[MAXN+2];

void Prime()
{
    int i,k;
    up=0;
    memset(prime,0,sizeof(prime));
    for (i=2;i<MAXN;i++)
    {
        if (prime[i]==1) continue;
        k=i;
        while(k*i<MAXN)
        {
            prime[i*k]=1;
            k++;
        }
        p[up++]=i;
    }
}

int GetNum(int t,int k)
{
    if (t<k) return 0;
    return t/k+GetNum(t/k,k);
}

void Init()
{
    int i,j;
    for (i=1;i<MAXN;i++)
    {
        for (j=0;j<up;j++)
        {
            if (i<p[j]) break;
            init[i].push_back(GetNum(i,p[j]));
        }
    }
}

bool Check(int t,int k)
{
    int i;
    for (i=0;i<k;i++)
    {
        if (t<p[i]) break;
        if (init[t][i]>num[i]) return false;
    }
    return true;
}

int Count(int t,int &k)
{
    int i,ss,tag;
    ss=100000;
    for (i=0;i<k;i++)
    {
        if (t<p[i]) break;
        ss=min(ss,num[i]/init[t][i]);
    }
    tag=k;
    for (i=0;i<k;i++)
    {
        if (t<p[i]) break;
        num[i]-=ss*init[t][i];
        if (num[i]==0) tag=min(tag,i);
    }
    k=tag;
    return ss;
}

int main()
{
    int T,i,j,n,m,s,k,l,r,mid,now,x;
    Prime();
    Init();
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(num,0,sizeof(num));
        s=0;
        for (i=0;i<n;i++)
        {
            scanf("%d",&x);
            for (j=0;j<up;j++)
            {
                if (x<p[j]) break;
                num[j]+=init[x][j];
            }
            s=max(s,j);
        }
        for (i=0;i<m;i++)
        {
            scanf("%d",&x);
            for (j=0;j<up;j++)
            {
                if (x<p[j]) break;
                num[j]-=init[x][j];
            }
            s=max(s,j);
        }
        k=s;
        for (i=0;i<s;i++)
        {
            if (num[i]<0) break;
            if (num[i]==0) k=min(k,i);
        }
        if (i<s)
        {
            printf("-1\n");
            continue;
        }
        now=0;
        while(1)
        {
            if (k==0) break;
            l=1;
            r=p[k]-1;
            while(l<=r)
            {
                mid=(l+r)/2;
                if (Check(mid,k)==true) l=mid+1;
                else r=mid-1;
            }
            ans[now][0]=r;
            ans[now++][1]=Count(r,k);
        }
        printf("%d\n",now);
        for (i=0;i<now;i++)
        {
            printf("%d %d\n",ans[i][0],ans[i][1]);
        }
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。


  1. for(int i=1; i<=m; i++){
    for(int j=1; j<=n; j++){
    dp = dp [j-1] + 1;
    if(s1.charAt(i-1) == s3.charAt(i+j-1))
    dp = dp[i-1] + 1;
    if(s2.charAt(j-1) == s3.charAt(i+j-1))
    dp = Math.max(dp [j - 1] + 1, dp );
    }
    }
    这里的代码似乎有点问题? dp(i)(j) = dp(i)(j-1) + 1;这个例子System.out.println(ils.isInterleave("aa","dbbca", "aadbbcb"));返回的应该是false

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. simple, however efficient. A lot of instances it is difficult to get that a??perfect balancea?? among usability and appearance. I must say that youa??ve done a exceptional task with this. Also, the blog masses quite fast for me on Web explore.