P2250二面体群（题解）

发表于 | 更新于 | 阅读次数：
本文字数： 6.4k | 阅读时长 ≈ 6 分钟

这里有一篇题解。

P2250二面体群（题解）

点我

PS.

我不知道这道题为什么会是灰的，通过数还这么少。
作为第三个$\texttt{A}$了这道题的人，来发一篇题解。
这道题读入调了我半天呢。

problem.

首先，在一个平面直角坐标系中，有一个单位园，它上面均匀分布了$\texttt{n}$个点。
然后有两种操作，可以顺时针旋转$\frac{\texttt{2}\pi}{k}$弧度，也可以把它按照$\texttt{x}$轴对称。
求一堆操作的最短等价操作是什么。

Solution.

Part 1.

首先，操作二上下轴对称是对点的相对分布是五影响的。
所以，操作二与操作一是相对独立的，操作二只与操作一的旋转方向有关。
所以可以记录下来操作二的操作次数，然后在执行操作一的时候加入操作二的次数，记录下逆时针旋转了几个单位。
然后就记录下来了读入。

Part 2.

从第一部分可以知道操作的总体显现情况，具体的说，就是$\texttt{t=}$有没有翻转，$\texttt{x=}$逆时针旋转了几个单位。
然后可以从$\texttt{t}$与$\texttt{x}$中推出答案，具体看代码。

可能有一点玄乎，那么上代码吧

Coding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
int n,x,t=1,a=0;
char c;
inline void init()	//第一部分 读入
{
	scanf("%d\n",&n),c=getchar();	//读入第一行的数以及第二行的第一个字符。
	while(1)	//一直循环
	{
		while(c!='\n'&&c!=EOF&&c!='r'&&c!='m') c=getchar();		//这里有锅，见下一行
		if(c=='\n'||c==EOF) break;		//数据有锅，如果这里没有EOF的话亲测最后一个点会TLE。
		scanf("%d",&x);		//读入操作数据
		if(c=='r') (a+=t*x%n)%=n;	//旋转操作直接模拟，要加上翻转操作中的顺逆时针，这条语句相当于a=(a+t*x%n)%n;
		if(c=='m') t=(x&1)?-t:t;	//翻转操作，记录下来有多少次翻转（奇数是-1，偶数是1）
		c=getchar();	//继续读
	}
	(a+=n)%=n;	//防止a<0
}
inline void out()
{
	if(n+1-a-t<a) printf("m1 r%d ",n-a),t=-t;	//这个特判也卡了我半天QwQ，特判语句我试了半天
//	1-t表示先翻转（可能之后的翻转不需要，或者之后多出来一次翻转），n-a表示翻转之后顺时针旋转。然后t要取反
	else if(a) printf("r%d ",a);	//如果a=0，就不需要输出了。
	if(t==-1) printf("m1 ");	//如果还有一次
	puts("");	//个人强迫症
}
int main()
{
	return init(),out(),0;	//完美主程序结束
}