首页 > ACM题库 > HDU-杭电 > hdu 2314 Dr. Podboq or: How We Became Asymmetric[解题报告]hoj
2014
01-05

hdu 2314 Dr. Podboq or: How We Became Asymmetric[解题报告]hoj

Dr. Podboq or: How We Became Asymmetric

问题描述 :

After long studying how embryos of organisms become asymmetric during their development, Dr. Podboq, a famous biologist, has reached his new hypothesis. Dr. Podboq is now preparing a poster for the coming academic conference, which shows a tree representing the development process of an embryo through repeated cell divisions starting from one cell. Your job is to write a program that transforms given trees into forms satisfying some conditions so that it is easier for the audience to get the idea.

A tree representing the process of cell divisions has a form described below.

* The starting cell is represented by a circle placed at the top.
* Each cell either terminates the division activity or divides into two cells. Therefore, from each circle representing a cell, there are either no branch downward, or two branches down to its two child cells.

Below is an example of such a tree.

Figure F-1: A tree representing a process of cell divisions

According to Dr. Podboq’s hypothesis, we can determine which cells have stronger or weaker asymmetricity by looking at the structure of this tree representation. First, his hypothesis defines "left-right similarity" of cells as follows:

1. The left-right similarity of a cell that did not divide further is 0.
2. For a cell that did divide further, we collect the partial trees starting from its child or descendant cells, and count how many kinds of structures they have. Then, the left-right similarity of the cell is defined to be the ratio of the number of structures that appear both in the right child side and the left child side. We regard two trees have the same structure if we can make them have exactly the same shape by interchanging two child cells of some cells.

For example, suppose we have a tree shown below:

Figure F-2: An example tree

The left-right similarity of the cell A is computed as follows. First, within the descendants of the cell B, which is the left child cell of A, the following three kinds of structures appear. Notice that the rightmost structure appears three times, but when we count the number of structures, we count it only once.

Figure F-3: Structures appearing within the descendants of the cell B

On the other hand, within the descendants of the cell C, which is the right child cell of A, the following four kinds of structures appear.

Figure F-4: Structures appearing within the descendants of the cell C

Among them, the first, second, and third ones within the B side are regarded as the same structure as the second, third, and fourth ones within the C side, respectively. Therefore, there are four structures in total, and three among them are common to the left side and the right side, which means the left-right similarity of A is 3/4.

Given the left-right similarity of each cell, Dr. Podboq’s hypothesis says we can determine which of the cells X and Y has stronger asymmetricity by the following rules.

1. If X and Y have different left-right similarities, the one with lower left-right similarity has stronger asymmetricity.
2. Otherwise, if neither X nor Y has child cells, they have completely equal asymmetricity.
3. Otherwise, both X and Y must have two child cells. In this case, we compare the child cell of X with stronger (or equal) asymmetricity (than the other child cell of X) and the child cell of Y with stronger (or equal) asymmetricity (than the other child cell of Y), and the one having a child with stronger asymmetricity has stronger asymmetricity.
4. If we still have a tie, we compare the other child cells of X and Y with weaker (or equal) asymmetricity, and the one having a child with stronger asymmetricity has stronger asymmetricity.
5. If we still have a tie again, X and Y have completely equal asymmetricity.

When we compare child cells in some rules above, we recursively apply this rule set.

Now, your job is to write a program that transforms a given tree representing a process of cell divisions, by interchanging two child cells of arbitrary cells, into a tree where the following conditions are satisfied.

1. For every cell X which is the starting cell of the given tree or a left child cell of some parent cell, if X has two child cells, the one at left has stronger (or equal) asymmetricity than the one at right.
2. For every cell X which is a right child cell of some parent cell, if X has two child cells, the one at right has stronger (or equal) asymmetricity than the one at left.

In case two child cells have equal asymmetricity, their order is arbitrary because either order would results in trees of the same shape.

For example, suppose we are given the tree in Figure F-2. First we compare B and C, and because B has lower left-right similarity, which means stronger asymmetricity, we keep B at left and C at right. Next, because B is the left child cell of A, we compare two child cells of B, and the one with stronger asymmetricity is positioned at left. On the other hand, because C is the right child cell of A, we compare two child cells of C, and the one with stronger asymmetricity is positioned at right. We examine the other cells in the same way, and the tree is finally transformed into the tree shown below.

Figure F-5: The example tree after the transformation

Please be warned that the only operation allowed in the transformation of a tree is to interchange two child cells of some parent cell. For example, you are not allowed to transform the tree in Figure F-2 into the tree below.

Figure F-6: An example of disallowed transformation

输入:

The input consists of n lines (1≤n≤100) describing n trees followed by a line only containing a single zero which represents the end of the input. Each tree includes at least 1 and at most 127 cells. Below is an example of a tree description.

((x (x x)) x)

This description represents the tree shown in Figure F-1. More formally, the description of a tree is in either of the following two formats.

"(" <description of a tree starting at the left child> <single space> <description of a tree starting at the right child> ")"

or

"x"

The former is the description of a tree whose starting cell has two child cells, and the latter is the description of a tree whose starting cell has no child cell.

输出:

The input consists of n lines (1≤n≤100) describing n trees followed by a line only containing a single zero which represents the end of the input. Each tree includes at least 1 and at most 127 cells. Below is an example of a tree description.

((x (x x)) x)

This description represents the tree shown in Figure F-1. More formally, the description of a tree is in either of the following two formats.

"(" <description of a tree starting at the left child> <single space> <description of a tree starting at the right child> ")"

or

"x"

The former is the description of a tree whose starting cell has two child cells, and the latter is the description of a tree whose starting cell has no child cell.

样例输入:

(((x x) x) ((x x) (x (x x))))
(((x x) (x x)) ((x x) ((x x) (x x))))
(((x x) ((x x) x)) (((x (x x)) x) (x x)))
(((x x) x) ((x x) (((((x x) x) x) x) x)))
(((x x) x) ((x (x x)) (x (x x))))
((((x (x x)) x) (x ((x x) x))) ((x (x x)) (x x)))
((((x x) x) ((x x) (x (x x)))) (((x x) (x x)) ((x x) ((x x) (x x)))))
0

样例输出:

((x (x x)) ((x x) ((x x) x)))
(((x x) ((x x) (x x))) ((x x) (x x)))
(((x ((x x) x)) (x x)) ((x x) ((x x) x)))
(((x ((x ((x x) x)) x)) (x x)) ((x x) x))
((x (x x)) ((x (x x)) ((x x) x)))
(((x (x x)) (x x)) ((x ((x x) x)) ((x (x x)) x)))
(((x (x x)) ((x x) ((x x) x))) (((x x) (x x)) (((x x) (x x)) (x x))))

http://acm.hit.edu.cn/hoj/problem/view?id=2314

最少要几个人能借到所需要的邮票

注意格式

#include <stdio.h>
#include <stdlib.h>

int compar(const void *a,const void *b);

int main()
{
    int n;
    int total, num, sum, offer[1024]= {0};
    int i, j, k;

    scanf("%d", &n);
    for (i = 1; i <= n; i++)
    {
        sum = 0;
        scanf("%d %d", &total, &num);
        for (j = 0; j < num; j++)
            scanf("%d",&offer[j]);

        qsort(offer,num,sizeof(offer[0]),compar);

        printf("Scenario #%d:\n", i);
        for (k = 0; k < num; k++)
        {
            sum += offer[k];
            if(sum >= total)
                break;
        }
        if(k == num)
            printf("impossible\n\n");
        else
            printf("%d\n\n", k+1);
    }

    return 0;
}
int compar(const void *a,const void *b)
{
    return *(int *)b-*(int *)a;
}

 

解题参考:http://blog.csdn.net/epk_lee/article/details/8204191


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

  2. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。

  3. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。