首页 > ACM题库 > HDU-杭电 > HDU 1566 奇怪的公式-模拟-[解题报告] C++
2013
12-12

HDU 1566 奇怪的公式-模拟-[解题报告] C++

奇怪的公式

问题描述 :

alpc12是个满脑子奇怪思想的孩子.新年到了,他想做做数学题,但是发现多边形的面积公式好复杂,于是他将其修改为S = a*b*c*d*…(a, b, c, d..是边且为正数且所有边不相等),alpc12的老师alpc01看他如此偷懒,作为惩罚,决定好好考考他。于是alpc01问:” 现在知道这个多边形的周长,这个多边形的面积最大为多少呢?而且,这回可不许你乱改周长公式哦!”

输入:

多个测试情况.每行输入n(3 <= n <= 1000),代表多边形周长,读到文件尾(EOF结束)。

输出:

对于每个输入的n,输出2行,
第一行:多边形的边数,然后是单调不降的各边的长度.
第二行:这个多边形的面积的最大值.
输出不要有任何的无用字符

样例输入:

3
4
5

样例输出:

2 1 2
2
2 1 3
3
2 2 3
6

这道题忒恶心,你懂的。。。本来这题不不知道怎么做,只是猜,这些边必定是递增的。有木有听过哥德巴赫猜想。。。当不知道做法时,可以猜想,也只能猜了,也就是YY^_^
本来用C++做的,但涉及到大数,太恶心了,后来改用java,Pe了,这时我心动了,因为我的猜想是对的。。。。。。。。。。。PE原因是因为 他是一行判断边,再一行判断面积。
解法:
从i=2开以始,一真做k=n-i;i++;      真到i>k,这时,可以确定有i-2条边,这时将最k逆向循环分给这些连,分到k=0为止,此时面积s=这些边的积。
不要问我为什么,我无法证明。。
import java.io.BufferedInputStream;
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner cin=new Scanner(new BufferedInputStream(System.in ));
        int n,i,j,k;
        BigInteger sum = null;

        while(cin.hasNext()){
            n=cin.nextInt();
            if(n<5){
                if(n==3)System.out.println("2 1 2");
                else if(n==4)System.out.println("2 1 3");
                sum=BigInteger.valueOf(n-1);
            }else{
            k=n;sum=BigInteger.valueOf(1);
            for(i=2;i<=k;i++)k-=i;
            if(k==0){
                System.out.print(i-2);
                k=1;
                for(j=2;j<i;j++){
                    System.out.print(" "+j);
                    sum=sum.multiply(BigInteger.valueOf(j));
                }
                System.out.println();
            }else{
                n=k%(i-2);//余数
                k=(k/(i-2));//增加的偏移量
                System.out.print(i-2);
                j=2+k;
                i+=k;
                for(;j<i-n;j++){
                    System.out.print(" "+j);
                    sum=sum.multiply(BigInteger.valueOf(j));
                }
                for(j=j+1;j<=i;j++){
                    System.out.print(" "+j);
                    sum=sum.multiply(BigInteger.valueOf(j));
                }
                System.out.println();
            }

        }
            System.out.println(sum);
        }

    }

}

http://blog.csdn.net/xinglely/article/details/8787754


  1. 给你一组数据吧:29 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 1000。此时的数据量还是很小的,耗时却不短。这种方法确实可以,当然或许还有其他的优化方案,但是优化只能针对某些数据,不太可能在所有情况下都能在可接受的时间内求解出答案。