链接：https://www.luogu.com.cn/problem/P6989
题目描述：定义\(RPS\)自动机为一张有向图,每个点有一个\(R,P,S\)中的某个字
符表示在这个节点时会出什么手势,同时有三条出边分别表示对
手出\(R,P,S\)时会去往哪个节点。(\(R,P,S\)分别表示石头剪刀布)
你知道对手的\(RPS\)自动机的结构,节点数为\(n ≤ 100\),但不知道
起点。你需要给出一个不超过\(50000\)个节点的\(RPS\)自动机和一
个起点,使得无论对手的起点是什么,进行\(10^9\)次对局后你的自
动机获胜概率超过\(99\)%。
题解：考虑如果对手起点确定，那么只要按照自动机构造一个环就可以胜率\(100\)%。但是现在对手起点不确定，所以我们考虑找到起点。
首先我们对对手的自动机构造一个有向图匹配自动机，支持查询对于每一个字符串，哪些终止节点满足存在一条路径最后到达它且路径上的所有字符(包括每个节点上的字符和路径上的字符)依次顺连可以得到字符串。
考虑一个无穷大的三叉树，每一个儿子节点的权值分别对应\(R,P,S\)，如果我们\(dfs\)这棵树，那么利用这个有向图匹配自动机，对于根节点到每一个节点的字符串\(S\)，我们可以知道现在对手可能到达的节点有哪些。令其集合为\(T\)，那么假如\(S\)只有一个元素，可以构造环解决。否则假如\(T\)的每一个节点含有字符总数为\(cnt\)，若\(cnt=1\)，可以唯一确定自己的出法，否则可以随机一个字符进行匹配。
不难发现，对于这棵树，我们\(dfs\)的深度不超过\(n\)，否则这一个串的\(T\)集合是相同的，构造时可直接连接到第一次出现该集合的节点，然后可以正确率\(100\)%，那么胜率大概是\(\frac{10^9-n}{10^9}\)，自动机大小是自动机大小合并级别的，约为\(n^2=10000\)。
#include<iostream>
#include<cstdio>
#include<map>
#include<ctime>
#include<cstdlib>
#define D 50000
#define N 100
using namespace std;
int read()
{
char c=0;
int sum=0;
while (c<'0'||c>'9') c=getchar();
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum;
}
bool dp[D+1][N+1];
int n,length,S[N+1][3],tS[D+1][3],dep,sz[D+1];
char c[N+1],tc[D+1];
struct node
{
bool s[N+1];
bool operator < (const node &t)const
{
for (int i=1;i<=n;++i)
{
if (s[i]<t.s[i]) return 1;
if (s[i]>t.s[i]) return 0;
}
return 0;
}
};
map<node,int>p;
node tmp;
char f(int x)
{
if (x==0) return 'R';
if (x==1) return 'P';
return 'S';
}
int F(char x)
{
if (x=='R') return 0;
if (x=='P') return 1;
return 2;
}
void insert(char a,char b)
{
sz[++dep]=0;
for (int i=1;i<=n;++i) dp[dep][i]=0;
for (int i=1;i<=n;++i)
if (c[i]==a&&dp[dep-1][i])
dp[dep][S[i][F(b)]]=1;
for (int i=1;i<=n;++i) sz[dep]+=dp[dep][i],tmp.s[i]=dp[dep][i];
return;
}
int find_rd()
{
if (sz[dep]==0) return 1;
bool vis[3];
vis[0]=vis[1]=vis[2]=0;
if (p.find(tmp)!=p.end()) return p[tmp];
for (int i=1;i<=n;++i)
if (dp[dep][i])
vis[(F(c[i])+1)%3]=1;
int x=++length;
p.insert(make_pair(tmp,x));
tc[x]=f(rand()%3);
while (!vis[F(tc[x])]) tc[x]=f(rand()%3);
for (int i=0;i<=2;++i) insert(f(i),tc[x]),tS[x][i]=find_rd(),--dep;
return x;
}
int main()
{
srand(time(0));
n=read();
for (int i=1;i<=n;++i)
{
cin>>c[i];
for (int j=0;j<=2;++j) S[i][j]=read();
}
for (int i=1;i<=n;++i) dp[0][i]=tmp.s[i]=1;
sz[0]=n;
find_rd();
printf("%d\n",length);
for (int i=1;i<=length;++i) printf("%c %d %d %d\n",tc[i],tS[i][0],tS[i][1],tS[i][2]);
return 0;
}