题解：P2250 二面体群

思路

设这一圈

n

个数从小到大的方向为

t

，其中方向为顺时针时

t=1

，逆时针时

t=-1

。设

\frac{360\degree}{n}

为一个单位。

分别分析

2

种操作：

将这 $n$ 个点顺时针旋转 $a$ 个单位，因为转 $n$ 个单位相当于没有转，所以可以把 $a$ 对 $n$ 取模，即 r %= n;
将这 $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

取模。

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

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

代码

CPP

#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;
}

题解：P2250 二面体群

文章操作

思路

代码

相关推荐

评论

题解：P2250 二面体群