CSP历年复赛题-P1310 [NOIP2011 普及组] 表达式的值

原题链接：https://www.luogu.com.cn/problem/P1310

题意解读：+代表按位或运算，*代表按位与运算，给定一个没有填数字的表达式，要求结果为0的数字方案数。

解题思路：

下面一步一步，由浅入深的来解决本题

思路一（20分做法）：

观察得知，20%的数据，只有10个符号，且没有括号，也就是对应数字最多11个，可以考虑DFS枚举所有长度是n+1的01数字组合，然后根据运算符、数字进行表达式计算。

需要注意的点是，对于中序表达式，在求值的时候，需要使用两个栈：运算符栈、操作数栈，主要流程如下：

1、遍历操作符和操作数

2、如果操作符栈为空，则将操作符和对应两个操作数入栈

3、如果操作符栈不为空，且当前操作符优先级不高于栈顶操作符的优先级，则将栈顶操作符和对应的两个操作数弹出进行运算，结果入操作数栈

4、再把当前操作符和下一个操作数分别入栈

5、最后，对栈中剩余的操作符和操作数进行一遍运算

6、结果即操作数栈顶元素

20分代码：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;
int n;
string str;
int a[15]; //n+1个0/1数字的组合
int ans = 0;

map<char, int> priority = {{'+', 1} , {'*', 2}};

int eval()
{
    stack<char> op; //运算符栈
    stack<int> num; //数字栈
    for(int i = 0; i < str.size(); i++) 
    {
        if(op.empty()) //运算符栈为空，则将运算符，左右操作数入栈
        {
            op.push(str[i]);
            num.push(a[i]);
            num.push(a[i + 1]);
            continue;
        }
        //如果运算符栈不空，且当前运算符优先级不高于栈顶运算符优先级
        //则弹出栈顶运算符和相应数字，进行计算，之后再把当前运算符和右操作数入栈
        if(op.size() && priority[str[i]] <= priority[op.top()]) 
        {
            char c = op.top(); op.pop();
            int a = num.top(); num.pop();
            int b = num.top(); num.pop();
            int res;
            if(c == '*') res = a & b;
            else res = a | b;
            num.push(res);
        }
        op.push(str[i]);
        num.push(a[i + 1]);
    }
    //最后对栈中剩余运算符和操作数进行计算
    while(op.size())
    {
            char c = op.top(); op.pop();
            int a = num.top(); num.pop();
            int b = num.top(); num.pop();
            int res;
            if(c == '*') res = a & b;
            else res = a | b;
            num.push(res);
    }
    //最终结果为栈顶数字
    return num.top();
}   

void dfs(int k)
{
    if(k == n + 1) //枚举到一组n + 1个0、1的数的组合
    {
        if(eval() == 0) ans++; //计算表达式的值
        return;
    }
    a[k] = 0;
    dfs(k + 1);

    a[k] = 1;
    dfs(k + 1);
}

int main()
{
    cin >> n >> str;
    dfs(0);
    cout << ans % MOD;
    return 0;
}

思路2（50分做法）：

由于前50%的数据长度不超过1000，且没有括号，可以利用组合数的思想：

对于一个+*组成的表达式，要为0，必须+对应的所有操作数都为0

表达式中可能有多个连续的*，形如+*+**+，完整表达式为_+_*_+_*_*_+_

结果为0，则有_ , _*_, _*_*_, _这四个都是0

_，代表一个数，为0的方案数只有1种

_*_，代表两个数做与运算，为0的方案有01,10,00 3种，也就是2个数，其中有可能有1个0,2个0，对应的方案数为C(2,1)+C(2,2) = 3种

_*_*_，代表三个数做与运算，为0的方案有C(3,1)+C(3,2)+C(3,3) = 7种

_，代表一个数，为0的方案只有1种

所以，_+_*_+_*_*_+_表达式为0的方案数为1 * 3 * 7 * 1 = 21种

基于以上分析，只需要找到表达式中的连续的*，每cnt个*，代表有cnt+1个数做与运算，为0的方案是C(cnt+1,1)+C(cnt+1,2)+...+C(cnt+1,cnt+1)

所有连续*的方案数相乘即可。

注意需要对组合数进行预处理。

50分代码：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;
int n;
string str;
int ans = 1;

int c[1005][1005];

int main()
{
    cin >> n >> str;

    //初始化组合数
    for(int i = 0; i <= 1000; i++)
    {
        for(int j = 0; j <= i; j++)
        {
            if(j == 0) c[i][j] = 1;
            else c[i][j] = (c[i-1][j-1] + c[i-1][j]) % MOD;
        }
    }

    int cnt = 0; 
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == '*') cnt++;
        else
        {
            //处理连续cnt个*
            if(cnt > 0)
            {
                int sum = 0; //cnt个*对应的表达式计算为0的方案数，也就是cnt+1个数有几个1~cnt+1个0的方案数：c(cnt,0)+c(cnt,1)+...+c(cnt,cnt)种
                for(int j = 1; j <= cnt + 1; j++)
                {
                    sum += c[cnt+1][j]; sum %= MOD;
                }   
                ans *= sum; ans %= MOD;
                cnt = 0;
            }
        }
    }
    if(cnt > 0)
    {
        int sum = 0; //cnt个*对应的表达式计算为0的方案数，也就是cnt+1个数有几个1~cnt+1个0的方案数：c(cnt,0)+c(cnt,1)+...+c(cnt,cnt)种
        for(int j = 1; j <= cnt + 1; j++)
        {
            sum += c[cnt+1][j]; sum %= MOD;
        }   
        ans *= sum; ans %= MOD;
        cnt = 0;
    }
    cout << ans;

    return 0;
}

思路3（100分做法）：

如果知道了中缀表达式的计算方法，也知道了此题跟组合数的关系，更进一步可以得出：

如果要计算结果是0的方案数

a+b是0的方案数 = a是0的方案数 * b是0的方案数

a*b是0的方案数 = a是0的方案数 * b是0的方案数 + a是0的方案数 * b是1的方案数 + a是1的方案数 * b是0的方案数

因此，我们可以借助表达式求值的代码流程，但实际进行计算是，不是具体计算两个数的+或者*，而是递推的计算

{结果是0的方案数、结果是1的方案数}，

操作数栈存的就是一个结构体

struct node 
{
    int cnt0; //结果为0的方案数
    int cnt1; //结果为1的方案数
};

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int MOD = 10007;
int n;
string str;

struct node
{
    int cnt0; //结果为0的方案数
    int cnt1; //结果为1的方案数
};

stack<char> op;
stack<node> num;

map<char, int> priority = {{'+', 1} , {'*', 2}}; //运算符的优先级


void eval()
{
    char c = op.top(); op.pop();
    node a = num.top(); num.pop();
    node b = num.top(); num.pop();
    node res;
    if(c == '+')
    {
        //两边都是0，+才是0
        res.cnt0 = (a.cnt0 * b.cnt0) % MOD; 
        //有一边是1，+就是1
        res.cnt1 = (a.cnt0 * b.cnt1 + a.cnt1 * b.cnt0 + a.cnt1 * b.cnt1) % MOD; 
    } 
    else if(c == '*')
    {
        //有一边是0，*就是0
        res.cnt0 = (a.cnt0 * b.cnt1 + a.cnt1 * b.cnt0 + a.cnt0 * b.cnt0) % MOD;
        //两边都是1，*才是1
        res.cnt1 = (a.cnt1 * b.cnt1) % MOD;
    }
    num.push(res);
}

int main()
{
    cin >> n >> str;

    num.push({1, 1}); //第一个操作数，只有1位，结果为0和为1的方案数都是1
    for(int i = 0; i < str.size(); i++)
    {
        if(str[i] == '(') op.push(str[i]);
        else if(str[i] == ')')
        {
            while(op.top() != '(') eval();
            op.pop(); //弹出')'
        }
        else 
        {
            while(op.size() && op.top() != '(' && priority[str[i]] <= priority[op.top()])
                eval();
            op.push(str[i]); //存入当前运算符
            num.push({1, 1}); //存入右操作数
        }
    }
    while(op.size()) eval(); //处理栈中剩余操作符

    cout << num.top().cnt0; //数据栈的结果0的方案数即答案

    return 0;
}