http://codeforces.com/gym/100443
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4423

首先用一个栈记录操作S后笔的位置,然后在此基础上统计笔之后可能在哪些位置。
定义向左走的「潜力」l为那些已经确定可以到达的点的未达的左儿子个数,类似定义向右走的「潜力」r
那么向左走就是ans+=l,同时更新r+=l;向右走类似。
不在根节点时向上走就是++ans,同时根据向上走的方向来更新lr

(只贴出与题目有关的代码,宏定义见 GitHub

const int mx = 1e5 + 5;

char s[mx], ss[mx];

int main()
{
    int i, ans, l, r;
    TT
    {
        stack<char> st;
        Pcas();
        SSS(ss, s);
        for (i = 0; ss[i]; ++i)
        {
            if (ss[i] == 'L' || ss[i] == 'R') st.push(ss[i]);
            else if (!st.empty()) st.pop();
        }
        ans = l = r = 1;
        for (i = 0; s[i]; ++i)
        {
            if (s[i] == 'L') ans += l, r += l;
            else if (s[i] == 'R') ans += r, l += r;
            else if (!st.empty()) ++ans, (st.top() == 'L' ? ++r : ++l), st.pop();
            ans %= mod, l %= mod, r %= mod;
        }
        PI(ans);
    }
    return 0;
}

Comments

comments powered by Disqus