题解：P1310 [NOIP2011 普及组] 表达式的值

Walrus · 2025-01-20 12:02:43 · 题解

一眼是建树之后在树上 dp，问题是如何建树。首先联系 CSP-2020 的一道题可知依靠运算优先级建表达式树，朴素的建树法是 O(N^2) 暴力建，也就是递归建树，但可以发现这显然是没必要的，我们完全可以给每个点设置一个优先级建笛卡尔树。

由于括号的优先级是最高的，所以括号里的东西需要优先运算，人话版理解就是这个式子外面套的括号越多其优先级就越高。

每有一对括号相当于给括号内的区间优先级加上了一个值，相当于区间加，故考虑差分，大概是这么写的：

stack<int> ss;
rep(i, 1, n) {
    if(s[i] == '(') ss.push(i);
    if(s[i] == ')') b[ss.top()] += 2, b[i + 1] -= 2, ss.pop();
}
rep(i, 1, n) b[i] += b[i - 1], a[i] = b[i] + (s[i] == '*' ? 2 : 1); 

然后建笛卡尔树，由于用单调栈维护所以复杂度是 O(N) 的，然后跑 dp。

令 dp_{x,0/1} 表示以 x 为根运算结果为 0/1 的方案数，根据位与和位或的性质可以得出表达式：

• 位与

  dp_{x,1}=dp_{ls,1}\times dp_{rs,1} dp_{x,0}=dp_{ls,0}\times dp_{rs,1}+dp_{ls,1}\times dp_{rs,0}+dp_{ls,0}\times dp_{rs,0}

• 位或

  dp_{x,0}=dp_{ls,0}\times dp_{rs,0} dp_{x,1}=dp_{ls,0}\times dp_{rs,1}+dp_{ls,1}\times dp_{rs,0}+dp_{ls,1}\times dp_{rs,1}

注意取模。

附建树代码：

void init(int *a) {
    rep(i, 1, n) {
        if(s[i] == '(' || s[i] == ')') continue;
        while(top && a[st[top]] > a[i]) ch[i][0] = st[top--];
        if(top) ch[st[top]][1] = i;
        st[++top] = i;
    } 
}