题意：
戳这里查看
分析：
由于这是一个无限大的完全二叉树，所以不合法的方案仅存在于跳到根节点的父亲这一种，且由于指令会无限重复，所以我们必须保证指令会使得离开被标记的子树的时候，所有被标记的点已经全部访问完，因为我们不会折返回去向上跳的
那么我们考虑枚举它是经过哪条路径，从哪个点离开整颗子树的，只要保证在走这条路经的同时遍历完所有的点，且由于指令会无限重复，所以我们对于路径上每一个点，将所有的子树求一个形态上的并集，只要使得整个并集能被访问，那么所有的点都会被访问到，最后的答案就是
(
c
n
t
−
1
)
∗
2
−
d
e
p
(cnt-1)*2-dep
(cnt−1)∗2−dep,其中
c
n
t
cnt
cnt是并集的树上节点数，
d
e
p
dep
dep为我们枚举的离开的点的深度
代码：
#include<bits/stdc++.h>
using namespace std
;
namespace zzc
{
const int maxn
= 2e3+5;
int ans
=1e9+7,cnt
,cur
,rt
,pos
;
char ch
[maxn
],pth
[maxn
];
struct tree
{
int lc
,rc
;
}f
[maxn
],g
[maxn
];
void build(int &x
)
{
if(!x
) x
=++cnt
;
int t
=ch
[pos
++]-'0';
if(t
&1) build(f
[x
].lc
);
if(t
&2) build(f
[x
].rc
);
}
void merge(int &x
,int y
)
{
if(!x
) x
=++cnt
;
if(y
==cur
) return ;
if(f
[y
].lc
) merge(g
[x
].lc
,f
[y
].lc
);
if(f
[y
].rc
) merge(g
[x
].rc
,f
[y
].rc
);
}
void solve(int u
,int dep
)
{
if(u
!=1)
{
memset(g
,0,sizeof(g
));
cur
=cnt
=1;
while(cur
)
{
const int t
=cur
;
for(int i
=0;i
<dep
;i
++)
{
cur
=pth
[i
]=='l'?f
[cur
].lc
:f
[cur
].rc
;
}
merge(rt
=1,t
);
}
ans
=min(ans
,(cnt
-1)*2-dep
);
}
pth
[dep
]='l';
if(f
[u
].lc
) solve(f
[u
].lc
,dep
+1);
pth
[dep
]='r';
if(f
[u
].rc
) solve(f
[u
].rc
,dep
+1);
}
void work()
{
scanf("%s",ch
);pos
=0;cnt
=1;
build(rt
=1);
solve(1,0);
printf("%d\n",ans
);
}
}
int main()
{
zzc
::work();
return 0;
}
