题解 P2250 【二面体群】
Terrible
·
·
题解
我们先来审一下题
角度为 $\frac{360k}{n}$ 度
那也就是说一个**圆被 n 个点均分为 n 个单位**，标号为 $0$ 的点在 $x$ 的正半轴上，其他点按逆时针顺序有序排列。
需要进行两种操作：
'r'：顺时针旋转 $\frac{360}{n}$，也就是每个点顺时针转动一个单位。对于'r' $a$，转动次数 $a$ 如果大于 $n$ 那么就相当于转了**超过一圈**了，那么就**直接取模**，相当于转了 $a\%n$ 个单位。
'm'：相对于 x 轴对称。对于 'm' $a$，对称次数 $a$ 如果大于 $1$，容易知道**对称两次会自我抵消**，只有 $a$ **是奇数**时，所有点才需要关于 x 轴对称。
继续想可以想到两点：
①给出的点的序列是有序的，在变换过程中**始终有序**。如果只需要支持旋转操作，那么仅需要记录出来某个点作为**基准点**，就可以**代表一个序列**。
②更进一步，如果要支持对称操作，我们发现，可以将对称后的序列改为**逆时针序列**，对称前的叫**顺时针序列**，**顺时针序列顺时针旋转**，**逆时针序列逆时针旋转**，我们甚至不需要更改基准点的位置，只需要记录是顺时针序列还是逆时针序列即可。
对于得出**最短操作序列**：
如果是**逆时针序列**:
①一定需要在对准基准点之后确保对称了奇数次；
②如果基准点逆时针操作数少可以先对称，后旋转。
如果是**顺时针序列**：
①如果基准点逆时针操作数少可以借助对称两次，得到最短序列；
②对称两次的操作序列长度需要加 $2$。
## 思路总结：
$p$ 表示基准点位置，$f=1$ 表示顺时针序列，$f=0$ 表示逆时针序列。
顺时针序列旋转 $a$ 次，则 $p=(p+a\%n)\%n$；
逆时针序列旋转 $a$ 次，则 $p=(n+p-a\%n)\%n$；
对称操作 $a$ 次，若 $a$ 为奇数，只需要更改 $f$ 即可。
#### 图示：
例如以下数据：
~~~~
10
r13 m3 r5
~~~~
注：$p$ 表示基准点的位置，其中位置是**顺时针描述**的。其中的“①②...”表示**点的标号**，与本题解的做法没有太大关系。
**模拟**一遍得到**最终状态**。
最后我们需要考虑得到**最终状态**的**最短操作序列**。
#### 边角情况的讨论：
$3\leqslant N \leqslant 10^8$，就是说 $N\not=2$，不存在既可以是逆时针序列又是顺时针序列的情况。
考虑这组数据：
~~~~
60
r31
~~~~
最后结果可以是：
~~~~
m1 r29 m1
~~~~
也可以是
~~~~
r31
~~~~
但是本题没有 $\color{blue} Special Judge$，也确实没有这种数据，可以放心做本题。还有一种数据与此类似，但都不必讨论。
## 代码：
```cpp
#include<cstdio>
int read()
{
int a(0);char c(getchar());
while(c<'0')c=getchar();
while(c>='0')a=a*10+(c^48),c=getchar();
return a;
}
int main()
{
int n(read()),a,p(0),f(1);
//p初值为0，表示选取基准点为0号点，f=1，f=0分别表示顺时针序列、逆时针序列
for(char c=getchar();~c;c=getchar())//~c表示如果读入-1(EOF)跳出
{
if(c<33)continue;
//ASCII中前32个字符中不包含数字和字母，直接吃掉继续读入
a=read();
if(c=='r')
{
a%=n;
if(f)p=(p+a)%n;
else p=(n+p-a)%n;//p有可能为负，需要+n
}
else if(a&1)f=!f;
}
if(p==0)
{
if(!f)return printf("m1"),0;
else return 0;
}//如果没有旋转操作直接结束程序，最多对称一下
if(f)
{
//顺时针序列：
//n-p+2表示借助两次对称进行旋转，p表示直接旋转，可以取等，不必讨论这种情况
if(n-p+2<p)printf("m1 r%d m1",n-p);
else printf("r%d",p);
}
else
{
//逆时针序列：
//n-p表示先对称后旋转，p表示先旋转后对称，可以取等，不必讨论这种情况
if(n-p<p)printf("m1 r%d",n-p);
else printf("r%d m1",p);
}
}
```