题解：P2250 二面体群

· · 题解

思路

设这一圈 n 个数从小到大的方向为 t，其中方向为顺时针时 t=1，逆时针时 t=-1。 设 \frac{360\degree}{n} 为一个单位。

分别分析 2 种操作：

  1. 将这 n 个点顺时针旋转 a 个单位，因为转 n 个单位相当于没有转，所以可以把 a 对 n 取模，即 r %= n;
  2. 将这 n 个点沿 x 轴翻转 b 次，因为翻转 2 次相当于没有翻转，所以可以把 b 对 2 取模，即 b %= 2;。如果 b=1，那么数的方向要改变，原本顺时针的要改为逆时针，原本逆时针的要改为顺时针。即 t \to -t。

先将 t 从 1 改为 -1 再顺时针旋转 a 个单位，相当于先逆时针旋转 a 个单位再将 t 从 1 改为 -1，所以可以设一共相当于顺时针转了 ans 个单位，每次进行操作 1 时，ans \to ans+t \times a，并且对 n 取模。

最终再分类讨论，输出操作步数最少的方案，相对简单，就不详细讲述了，代码中有注释。

最后注意：若无需操作则什么都不输出。

代码

#include <iostream>
using namespace std;

int main() {
    int n, t = 1, ans = 0;
    cin >> n;
    string s;
    while (cin >> s) {
        int x = 0;
        for (int i = 1; i < s.size(); i++)
            x = x * 10 + s[i] - '0'; // 拼数字
        if (s[0] == 'r') ans = (ans + t * x) % n; // 计算 ans
        else if (x & 1) t = -t; // 改变方向
    }
    ans = (ans + n) % n; // 取模
    // 分类讨论
    if (~t) { // t=1 的情况
        if (n - ans + 2 < ans) printf("m1 r%d m1", n - ans);
        else if (ans) printf("r%d", ans); // 如果 ans = 0 则不输出
    } else { // t=-1 的情况
        // 先转后翻，步数为 ans；先翻后转，步数为 n - ans
        if (n - ans < ans) printf("m1 r%d", n - ans);
        else printf("r%d m1", ans);
    }
    return 0;
}