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

· · 题解

思路

问题分析：

需要计算一个未完成的二进制表达式填入 0 或 1 后结果为 0 的方案数。运算符 \oplus（对应 + ）和 \times（对应 \ast ）的优先级不同，且包含括号。

后缀表达式转换：

将输入的运算符和括号字符串转换为后缀表达式，以便按顺序处理运算符和变量。每个变量按顺序插入到后缀表达式中。

动态规划计算：

使用栈结构维护每个子表达式的 0 和 1 的方案数。遇到运算符时，从栈中弹出两个操作数，按运算符类型合并方案数。

模运算处理：

每一步计算都对 10007 取模，防止数值溢出。

步骤详解

统计运算符数目：

确定变量数目为运算符数目加一。

生成后缀表达式：

使用栈处理运算符优先级和括号。

初始时插入一个变量，每处理一个运算符后插入一个变量。

处理后缀表达式：

每个变量对应初始方案数 （1, 1）。

处理运算符时，根据类型合并左右操作数的方案数，结果压入栈中。

输出结果：

最终栈顶元素的 0 的方案数即为答案，对 10007 取模。

复杂度分析

时间复杂度：O(L)，处理每个字符和运算符一次。

空间复杂度：O(L)，存储后缀表达式和栈结构。

AC代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cctype>
#include <cstdlib>
#include <ctime>
#include <time.h>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <random>//poj*
#include <chrono>//poj*
#include <unistd.h>//poj*
#define int long long
typedef unsigned long long ull;
typedef long long ll;
const int INF = 0x3f3f3f3f;
const int N = 3e6+5;
const int MOD = 10007;
using namespace std;
int m;
int L;
string s;
int get_priority(char op){
    if(op == '+') return 1;
    else if(op == '*') return 2;
    else return 0;// '('
}
signed main(){
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>L>>s;
    // 统计运算符数目
    for(char c : s){
        if(c == '+' || c == '*') m++;
    }
    // 生成后缀表达式
    vector<char> postfix;
    stack<char> op_stack;
    postfix.push_back('v');// 初始变量
    int var_count = 1;
    for(char c : s){
        if(c == '('){
            op_stack.push(c);
        }else if(c == ')'){
            while(op_stack.top() != '('){
                postfix.push_back(op_stack.top());
                op_stack.pop();
            }
            op_stack.pop();// 弹出 '('
        }else{
            int curr_pri = get_priority(c);
            while(!op_stack.empty() && get_priority(op_stack.top()) >= curr_pri){
                postfix.push_back(op_stack.top());
                op_stack.pop();
            }
            op_stack.push(c);
            // 添加变量
            postfix.push_back('v');
            var_count++;
        }
    }
    // 处理剩余的运算符
    while(!op_stack.empty()) {
        postfix.push_back(op_stack.top());
        op_stack.pop();
    }
    // 处理后缀表达式
    stack<pair<int, int>> st;// cnt0, cnt1
    for(char token : postfix){
        if(token == 'v'){
            st.push({1, 1});
        }else{
            auto right = st.top();
            st.pop();
            auto left = st.top();
            st.pop();
            int cnt0,cnt1;
            if(token == '+'){
                cnt0 = (left.first * right.first) % MOD;
                cnt1 = ((left.first * right.second) % MOD + 
                        (left.second * right.first) % MOD + 
                        (left.second * right.second) % MOD) % MOD;
            }else{// '*'
                int left_total = (left.first + left.second) % MOD;
                int right_total = (right.first + right.second) % MOD;
                int total = (left_total * right_total) % MOD;
                int product_1 = (left.second * right.second) % MOD;
                cnt0 = (total - product_1 + MOD) % MOD;
                cnt1 = product_1;
            }
            st.push({cnt0, cnt1});
        }
    }
    cout<<st.top().first % MOD<<endl;
    return 0;
}
/*
-注释&笔记:

-样例输入:

-样例输出:

*/

感谢@whoseJam的讲解