题面：https://zhengruioi.com/problem/3625
由于没有报CSP7连测的大家看不到题面，这边再把题面放一下
起始标记 (mark)
限制（比赛题目配置）
| 时间限制 | 空间限制 | 分数 | 代号 | 子文件夹 | 评测配置 |
|---|---|---|---|---|---|
| 1000ms | 1024MB | 100 | mark | 是 | 文件 IO (mark.in, mark.out) |
题目描述
小 Z 的机器人在二维整数坐标平面上运动，初始位于 (0, 0)，面向北方。北、东、南、西分别对应 y 轴正方向、x 轴正方向、y 轴负方向、x 轴负方向。
机器人使用一张环形指令带。指令带上依次写有 n 条指令，相邻关系首尾相接：
F：沿当前朝向前进一步；L：原地向左转 90°；R：原地向右转 90°。
执行程序时，机器人会从指令带上的某一条指令开始，沿固定方向依次执行，直到每条指令都恰好执行一次。指令的环上次序已知，但原本用于标记第一条指令的记号脱落了。
给定按环上顺序抄录的指令串 。若选择第 i 条指令作为起点，实际执行顺序为
枚举全部 n 个可能的起点，求机器人一共可能到达多少个不同的最终位置。
输入格式
第一行一个整数 。
第二行一个长度为 的字符串 ，仅包含字符 F、L、R。
输出格式
输出一个整数，表示不同最终位置的数量。
样例
样例 1 输入
3
FLF样例 1 输出
3样例解释
三个可能的起点对应字符串 FLF、LFF、FFL，最终位置依次为 (-1,1)、(-2,0)、(0,2)。
样例 2 输入
参见下发文件中的 mark2.in。
样例 2 输出
参见下发文件中的 mark2.ans。
大样例说明
该样例符合测试点 1 ~ 12 的约束。
样例 3 输入
参见下发文件中的 mark3.in。
样例 3 输出
参见下发文件中的 mark3.ans。
大样例说明
该样例符合测试点 15 ~ 20 的约束。
数据范围与提示
对于所有测试数据，保证：
- ;
- 仅包含字符
F、L、R。
本题共 20 个测试点，每个测试点 5 分，各测试点单独计分。
| 测试点编号 | 特殊限制 |
|---|---|
| 1 ~ 12 | |
| 13 ~ 14 | 执行完整指令串后，机器人的朝向不变 |
| 15 ~ 20 | 无 |
文件输入输出
在比赛中，请从文件 mark.in 中读入数据，并将答案写入文件 mark.out。
附加文件下载：点击下载
如果大家想要做这题并进行评测，请前往U724903 起始标记 (mark) – 洛谷，数据是官方数据，故不进行公开
题解
之后要用的例子：FLRF
题面上面都放了，我就不再叙述了。
那么首先，很容易观察到：如果我们从左到右枚举每一个起点，等价于将上一个操作序列的第一个操作放到末尾。
进一步思考，又等价于回退上一个操作序列的第一个操作，并在序列的最后重新加入相同的操作。
例如我给的这个操作序列，如果我们需要求LRFF（以第二个操作为第一步）这个操作序列的终点，在已知FLRF这个操作序列的结果的情况下，我们只需要回退一步F的操作，并重新进行一步F的操作，就可以得到这个操作序列的最终结果，而不需要使用非常暴力的 模拟做法。
那么我们现在来考虑如何进行回退。分类讨论一下：
- F：当上一个操作序列的第一步为F，很容易发现这一步一定是向北（上）方走的，于是我们向南（下）方走一步，也就是纵坐标减一，就能够回退F操作
- L：当上一个操作序列的第一步为L，由于L是在开头的，这会使得整体的路线都向左偏移90°，也就是最终走到的点相对原点逆时针旋转了90°，那么我们只需要将上一个操作序列的终点相对原点顺时针旋转90°，就能够回退这一步L操作。
- R：与L同理，终点相对原点逆时针旋转90°即可。
旋转怎么做，我简单说明一下：
- 对于原点顺时针旋转90°，则会使得得到的点的横坐标等于操作前的点的纵坐标，且得到的点的纵坐标等于操作前的点的横坐标的相反数，即：若操作前的点的坐标为 ，则进行旋转操作后得到的点为 。
- 对于原点逆时针旋转90°，则会使得得到的点的横坐标等于操作前的点的纵坐标的相反数，且得到的点的纵坐标等于操作前的点的横坐标，即：若操作前的点的坐标为 ，则进行旋转操作后得到的点为 。
那么接下来是将操作添加到末尾。容易发现：当添加的操作为L或R，终点是不会变化的，对于这两个操作，只需要进行回退即可。
那么将F操作添加到末尾应该如何处理呢：
- 如果需要添加F操作，就需要操作序列最终的朝向信息。
- 那么我们就可以先暴力求一下第一步为第一个操作的情况的终点（用于推出之后的操作序列的终点）和朝向信息，并存储起来。
- 由于序列中操作L和R的数量是永远不会变的，所以不管第一步为哪个操作，最终朝向都不会有变化。
- 我们只需要向我们得到的最终朝向走一步就可以了。
使用上述方法，我们可以求得以每一个操作为第一步的最终位置，最后我们只需要使用哈希表判重，即可在期望 的时间复杂度完成本题。也可以使用集合判重，复杂度
现在使用我举的这个例子模拟一下上述做法：
- 首先求出FLRF这个操作序列的信息，容易得到：终点 ，最终朝向为北（上）
- 接着是LRFF，相对上一个操作序列的信息，首先回退一步开头的F操作，即向下移动一次，得到坐标 ，接着将F操作放到末尾，由于最终朝向为北（上），向上移动一次，终点 。
- 接着是RFFL，相对上一个操作序列的信息，首先回退一步开头的L操作，即上一个求得的终点相对原点顺时针旋转90°，得到坐标 。再将该操作加入到末尾，由于仅进行转向，不会影响终点坐标，故终点 。
- 接着是FFLR，相对上一个操作序列的信息，首先回退一步开头的R操作，即上一个求得的终点相对原点逆时针旋转90°，得到坐标 。再将该操作加入到末尾，由于仅进行转向，不会影响终点坐标，故终点 。
- 由于操作L和操作R的数量全程不变，故最终朝向全程不变。
- 仅有两个不同终点，分别为 和 ，最终答案为 。
ok，贴代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct pair_hash{
template <class T1,class T2>
std::size_t operator() (const std::pair<T1,T2>& p) const{
auto h1=std::hash<T1>{}(p.first);
auto h2=std::hash<T2>{}(p.second);
return h1^(h2<<1);
}
};
void left(int &dir)
{
dir--;
if(dir==-1)
{
dir=3;
}
}
void right(int &dir)
{
dir++;
if(dir>3)
{
dir=0;
}
}
void gof(int &x,int &y,int dir)
{
if(dir==0)
{
++y;
}
if(dir==1)
{
++x;
}
if(dir==2)
{
--y;
}
if(dir==3)
{
--x;
}
}
void gob(int &x,int &y,int dir)
{
if(dir==0)
{
--y;
}
if(dir==1)
{
--x;
}
if(dir==2)
{
++y;
}
if(dir==3)
{
++x;
}
}
unordered_map<pair<int,int>,bool,pair_hash> mp;
signed main(){
int n;
scanf("%lld",&n);
string s;
cin>>s;
int len=s.length();
s=" "+s;
int dir1=0;
int fx=0;
int fy=0;
for(int i=1;i<=len;++i)
{
if(s[i]=='L')
{
left(dir1);
}
else if(s[i]=='R')
{
right(dir1);
}
else
{
gof(fx,fy,dir1);
}
}
int ans=1;
mp[{fx,fy}]=1;
int x=fx;
int y=fy;
for(int i=2;i<=n;++i)
{
if(s[i-1]=='F')
{
gob(x,y,0);
gof(x,y,dir1);
}
else if(s[i-1]=='L')
{
int tx=x;
int ty=y;
x=ty;
y=-tx;
}
else
{
int tx=x;
int ty=y;
y=tx;
x=-ty;
}
if(mp[{x,y}]==0)
{
mp[{x,y}]=1;
++ans;
}
}
printf("%lld",ans);
return 0;
}