首先，观察题目可知，该题不存在无解的情况，可以建一颗深度为n的满二叉树，以根为起点，收到0时向左走，收到1时向右走，再观察题目发现(1<<n+1)-1正好9192≈10000，无需证明，这就是对的。所以接下来只要把能够合并的点都合并起来，就能得到符合题意的自动机。
YYMHL（%A题大爷）说了，只要n^2枚举，两两合并，就可以A掉这题。时间复杂度O（kn^2），k为未知常数，听说很小。然后施大说正解就是这样的。顿时无语到不想鏼这题。
然后考试后的汪大就默默地想出了一个n（logn）^2的算法，怒艹标算！然后我就烧四五个小时把它膜了一遍，然后就没有然后了……
因此，蒟蒻决定重点分析这个算法。
先挂个代码，不然讲不清楚。
#include<cstdio> #include<iostream> #include<algorithm> #include<cstring> using namespace std; #define rep(i,j,k) for(i=j;i<=k;++i) #define per(i,j,k) for(i=j;i>=k;--i) #define ll long long #define ldb long double #define pii pair<int,int> #define mkp make_pair #define X first #define Y second const int N=10005; int n,nn,dep[N],ha[N],par[N],tot,u,vis[N],pos[N],lst[N],key[N];pii tmp[N]; struct TREE{int lc,rc;bool flg;}T[N]; void rebuild(int x){ if(vis[x])return;vis[x]=1; pos[key[x]=++u]=x;if(T[x].flg)lst[++tot]=u; rebuild(T[x].lc=par[T[x].lc]),rebuild(T[x].rc=par[T[x].rc]); } int main(){ int i,x,j,l;char str[14]; scanf("%d",&n);nn=(1<<n+1)-1; rep(i,1,nn){ scanf("%s",str); x=1;l=strlen(str)-1; rep(j,1,l)x=x<<1|str[j]=='1'; if(x<<1<nn)T[x]=(TREE){x<<1,x<<1|1,str[0]=='+'}; else T[x]=(TREE){x,x,str[0]=='+'}; } rep(i,1,nn)dep[par[i]=i]=dep[i>>1]+1; for(l=nn,i=0;i<n;++i,l>>=1){ rep(j,1,l)tmp[j]=mkp(ha[j]=ha[T[j].lc]+l*ha[T[j].rc]<<1|T[j].flg,j); sort(tmp+1,tmp+l+1); x=ha[tmp[1].Y]=0; rep(j,2,l)ha[tmp[j].Y]=x+=tmp[j].X>tmp[j-1].X; x=tmp[1].Y; rep(j,2,l) if(tmp[j].X==tmp[j-1].X){ if(dep[tmp[j].Y]>n-i)par[tmp[j].Y]=x; } else x=tmp[j].Y; } rebuild(1); printf("%d 1\n%d",u,tot); rep(i,1,tot)printf(" %d",lst[i]);puts(""); rep(i,1,u)printf("%d %d\n",key[T[pos[i]].lc],key[T[pos[i]].rc]); return 0; }
另外附一张优先级的图（压行走火入魔了……）。
该图来自百度百科。
T代表节点，lc、rc分别表示接收0、1后走到的节点，flg表示节点代表的串会被接受（1）还是拒绝（0）。
汪大说，叶子节点的lc、rc都要指向自己，这也许和rebuild有关。
给定每个点一个哈希值（用ha[]表示），其囊括了该节点本身与左右子树的flg信息，若两个节点的ha相同，则说明这两个节点完全相同，可以合并。哈希之后为了避免取模，可以进行离散化。
接着从大到小枚举深度，每次只能将枚举到深度的点与深度小于等于它的点合并。合并用到并查集。注意这里的并查集没有用到getpar（），原因是所有ha相同的节点都只会被连向编号最小的那个节点（即x，靠tmp维护）。
rebuild的过程比较水，只要从1开始搜，把走到的点压到一起（lst[]中，个数为u），其中flg为1的点压到一起（pos[]中，总数为tot）。注意得到的结果还不能直接输出，原因是要重新编号。我就是因为没想到这点，被simpleoj卡掉了80分。。。
应该差不多了。
算上考试和写博客，这一天全烧在这题上了。惨！！！
