题解 P5597 【【XR-4】复读】

一道有趣的题2333.

思路

首先,指令循环一次后,出发点和结束点相对位置都是相同的.也就是说如果一次指令后到根的左儿子的右儿子,第二次指令就到根的左儿子的右儿子的左儿子的右儿子,第三次就到根的左儿子的右儿子的左儿子的右儿子的左儿子的右儿子...
我们可以YY一下,第一次指令结束后肯定在有宝藏的地方.因为所有有宝藏的地方构成一棵树,没有宝藏的地方再怎么向下延伸都不会有宝藏.
数据范围还是比较友好的,只有2000,我们很容易想到O(N^2)的暴力.于是我们先枚举第一次指令后到达的节点.
先来看张图(灰色节点代表根节点以及每次指令结束后所处的节点):

很明显的一点是,每次指令后都不可能返回祖先节点了.也就是说,到下一个灰色点之前必须先把上面部分全部访问完,否则就不可能回去了.
我们必须找到一个指令集,能把被灰色点分开的连通块内所有的节点都访问.
再来张图:

我们把被灰色点分开的连通块(很明显是树)取出来(灰色点同属于两个连通块),然后把这些树"合并"起来.你可以在一些透明纸上画出这些树,然后把这些透明纸叠起来(注意这些树的根节点重合,根节点左儿子重合,根节点右儿子重合),然后你从上面看到的树就要"合并"的结果.
容易发现,遍历这棵树(最终停在下一个灰色点)的指令集就是要求的答案.
设这棵"合并树"含size个节点,根节点到下一个灰色点的最短路径是d,指令集的长度就是2\times(size-1)-d.
因为求"合并树"时每个节点仅访问一次,求一次"合并树"的复杂度是O(N)的.
加上枚举下一个灰色点,总复杂度是O(N^2)的.
具体实现细节请参考代码.

代码

#include<bits/stdc++.h>
using namespace std;
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
template<typename T> inline bool cmin( T &x, T y ){ return y < x ? x = y, 1 : 0; }

const int MAXN = 2e3 + 15;
struct node{ int ls, rs; }o[MAXN], p[MAXN];
int ans(1e9), tmp, n, cnt, cur; char s[MAXN];

void Build( int &c ){ // 构建出题目给出有宝藏的节点构成的树
    if ( !c ) c = ++cnt;
    char t(s[n++]);
    if ( t & 1 ) Build(o[c].ls);
    if ( t & 2 ) Build(o[c].rs);
}
void Merge( int &c, int l ){ // "合并"过程
    if ( !c ) c = ++cnt;
    if ( l == cur ) return;
    if ( o[l].ls ) Merge(p[c].ls, o[l].ls);
    if ( o[l].rs ) Merge(p[c].rs, o[l].rs);
}

char pth[MAXN];
void Work( int c, int stp ){ //枚举灰色点的过程
    if ( c != 1 ){
        memset( p, 0, sizeof p ), cnt = cur = 1;
        while( cur ){
            const int t(cur);
            fp( i, 0, stp - 1 ) cur = pth[i] == 'L' ? o[cur].ls : o[cur].rs; // 找下一个灰色点
            Merge(tmp = 1, t);
        } cmin( ans, (cnt - 1) * 2 - stp ); // 答案取最小值
    }
    pth[stp] = 'L';
    if ( o[c].ls ) Work(o[c].ls, stp + 1);
    pth[stp] = 'R';
    if ( o[c].rs ) Work(o[c].rs, stp + 1);
}

signed main(){
    scanf( "%s", s ), n = 0, cnt = 1;
    Build(tmp = 1), Work(1, 0);
    printf( "%d\n", ans );
    return 0;
}