自动搬运

查看原文

来自洛谷，原作者为

	Terrible 没错，这家伙还真的是很懒惰，真的什么都没留下！！

搬运于2025-08-24 21:35:36，当前版本为作者最后更新于2020-05-24 16:21:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

我们先来审一下题

$n$ 个点的标号为 $k=0,1,...,n-1$， 角度为 $\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$，也确实没有这种数据，可以放心做本题。还有一种数据与此类似，但都不必讨论。

代码：

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