首页 > ACM题库 > HDU-杭电 > Hdu 1486 Dihedral groups 待解决 [解题报告] C++
2013
12-11

Hdu 1486 Dihedral groups 待解决 [解题报告] C++

Dihedral groups

问题描述 :

Consider n points on a unit circle with numbers k = 0, 1, …, n-1. Initially point k makes an angle of 360 ・ k / n degrees to the x-axis, measured in counter-clockwise direction. We are going to perform two different kind of operations on that set of points:

  • rotation by 360 / n degrees in clockwise direction
  • reflection with respect to the x-axis
  • The following picture shows an example of these operations:

    Given a sequence of operations, we are interested in the shortest sequence of operations which gives the same result, i.e., the position of every single point is the same after performing either of those sequences of operations.

    The sequence is given as a string consisting of the characters ‘r’ and ‘m’ which represent clockwise rotation and reflection respectively ("to the right" and "mirror"). Multiple consecutive occurrences of the same character are collected into the representation <character><number>, and for convenience this will also be done for single occurrences. So "rrmrrrrrrrrrrrr" will be abbreviated to "r2 m1 r12". The representations of different operations are always separated by a single space.

    输入:

    The input file consists of several test cases. Each test case starts with a line containing n (3 ≤ n ≤ 10^8), the number of points. The second line of each test case consists of an abbreviated sequence of operations as described above. All numbers will be positive and less than 10^8. There will be no empty line in the input file, and no line will contain more than 100000 characters. The last test case is followed by a line containing 0.

    输出:

    For each test case print one line containing the abbreviated format of the sequence with the minimum number of operations which results in the same configuration of points as the input sequence. In case of multiple optimal solutions, print any solution. Note that the second line of the sample output is a blank line.

    样例输入:

    4
    r2
    100
    m1 r100 m1
    54
    r218 m3 r1
    0

    样例输出:

    r2
    
    r1 m1


    1. 有两个重复的话结果是正确的,但解法不够严谨,后面重复的覆盖掉前面的,由于题目数据限制也比较严,所以能提交通过。已更新算法

    2. 第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。第2题,TCP不支持多播,多播和广播仅应用于UDP。所以B选项是不对的。

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