首页 > ACM题库 > HDU-杭电 > HDU 1446 Paper Cut-模拟-[解题报告] C++
2013
12-10

HDU 1446 Paper Cut-模拟-[解题报告] C++

Paper Cut

问题描述 :

Still remember those games we played in our childhood? Folding and cutting paper must be among the most popular ones. Clever children will always search for something new, even when they play games like cutting paper. Now, Carol, a smart girl, asks her brother Mike to solve a puzzle. However, as always, Mike cannot find the solution, therefore he turns to you for help.

Carol’s puzzle is simple to state. She folds the paper in a certain manner and then uses a knife to cut through the folded paper. What Mike needs to do is to tell how many pieces the folded paper will turn into after it is cut. To eliminate the ambiguity, we can coordinate the paper as [0, 1] * [0, 1], with the coordinates of lower left corner (0, 0). A fold is denoted by two points (x1, y1) and (x2, y2) on the folding line, with which, the direction of the line is determined by from (x1, y1) to (x2, y2). Carol will always fold the paper from left to right relative to the directed line given (see Figure-1). The cut is determined by the two points on the cut line. Please note that the points given to determine the fold or the cut are not necessarily on the paper.

输入:

The first line of the input contains one integer t, the number of test cases. Then t cases follow. For each test case, the first line consists of an integer N (0 <= N <= 20), the number of folds, and the following N lines give two points on each fold line as x1, y1, x2, y2. The following line gives two points on the cut line in the same way.

输出:

For each test case, output one line containing the number of pieces the paper will turn into after the cut.

样例输入:

2
1
0 0.5 1 1
0.5 0 0.5 1
1
0 0.5 1 1
0 0.4 1 0.4

样例输出:

2
3

#include<cstdio>
int hash[32][201];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        int i,k,po;
        bool f=1;
        hash[1][0]=1;
        for(i=2;i<=n;i++)
        {
            hash[i][0]=1;
            for(po=0;po<=n*(n-1)/2;po++)
                for(k=1;k<=i;k++)
                    if(hash[k][po])
                        hash[i][(i-k)*k+po]=1;
        }
        for(i=0;i<=n*(n-1)/2;i++)
            if(hash[n][i])
            {
                if(f)
                {
                    printf("%d",i);
                    f=0;
                }
                else
                    printf(" %d",i);
            }
        printf("\n");
    }
    return 0;
}

解题报告转自:http://blog.csdn.net/ray007great/article/details/8971020


  1. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])

  2. 题本身没错,但是HDOJ放题目的时候,前面有个题目解释了什么是XXX定律。
    这里直接放了这个题目,肯定没几个人明白是干啥

  3. Thanks for using the time to examine this, I truly feel strongly about it and enjoy finding out far more on this subject matter. If achievable, as you achieve knowledge

  4. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。

  5. 在方法1里面:

    //遍历所有的边,计算入度
    for(int i=0; i<V; i++)
    {
    degree = 0;
    for (j = adj .begin(); j != adj .end(); ++j)
    {
    degree[*j]++;
    }
    }

    为什么每遍历一条链表,要首先将每个链表头的顶点的入度置为0呢?
    比如顶点5,若在顶点1、2、3、4的链表中出现过顶点5,那么要增加顶点5的入度,但是在遍历顶点5的链表时,又将顶点5的入度置为0了,那之前的从顶点1234到顶点5的边不是都没了吗?

  6. L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-1])这个地方也也有笔误
    应改为L(X [0 .. M-1],Y [0 .. N-1])= 1 + L(X [0 .. M-2],Y [0 .. N-2])