洛谷 P1310 NOIP2011普及组 表达式的值 题解【DP】【字符串】【栈】

作者: wjyyy 分类: DP,字符串,,解题报告,递推 发布时间: 2018-06-18 15:28

点击量:21

 

   普及组的题也会很毒瘤啊……

 

题目描述

对于 1 位二进制变量定义两种运算:
运算符 运算规则

0⊕0=0
0⊕1=1
1⊕0=1
1⊕1=1
×
0 × 0=0
0 × 1=0
1 × 0=0
1 × 1=1

运算的优先级是:
1. 先计算括号内的,再计算括号外的。

2. “×”运算优先于“⊕”运算,即计算表达式时,先计算×运算,再计算⊕运算。
例如:计算表达式A⊕B × C 时,先计算B × C,其结果再与A 做⊕运算。
现给定一个未完成的表达式,例如_+(_*_),请你在横线处填入数字0 或者1,请有多少种填法可以使得表达式的值为0。

输入输出格式

输入格式:

共 2 行。

 

第 1 行为一个整数L,表示给定的表达式中除去横线外的运算符和括号的个数。

第 2 行为一个字符串包含L 个字符,其中只包含’(’、’)’、’+’、’*’这4 种字符,其中’(’、’)’是左右括号,’+’、’*’分别表示前面定义的运算符“⊕”和“×”。这行字符按顺序给出了给定表达式中除去变量外的运算符和括号。

 

输出格式:

共 1 行。包含一个整数,即所有的方案数。注意:这个数可能会很大,请输出方案数对 10007 取模后的结果。

 

输入输出样例

输入样例#1:
4
+(*)
输出样例#1:
3

说明

【输入输出样例说明】

给定的表达式包括横线字符之后为:_+(_*_)

 

在横线位置填入(0 、0 、0) 、(0 、1 、0) 、(0 、0 、1) 时,表达式的值均为0 ,所以共有3种填法。

对于 20%的数据有0 ≤L≤ 10。

对于 50%的数据有0 ≤L≤ 1,000。

对于 70%的数据有0 ≤L≤ 10,000。

对于 100%的数据有0 ≤L≤ 100,000。

对于 50%的数据输入表达式中不含括号。

 

   其实如果理解清题意,这个DP/递推也是很好想的,不过这个题难就难在处理字符串和括号上。

 

   在一串表达式中,空格初始值为0和1各有一种情况,即DP初始值为v[0]=1,v[1]=1,接着如果是_+_,那么1可以由0⊕1,1⊕0(分别是两种),1⊕1的情况推过来,我们假设这两块空格都是初始状态,那么把这个式子合并成一个空格,继续转移,此时v[0]=1,v[1]=3。

 

   既然表达式中有括号,那么我们就应该用栈来做括号匹配的工作。因为括号的优先级大于乘法大于加法,所以我们把数和数后面的操作符(数后面的操作符要么是+要么是×或者是字符串结尾’\0’,下面给出证明)放在一个结构体中放入栈内。

 

   证明:因为不会出现省略×,即1(1+0),所以任何数后面都不会有‘(’。

 

   如果是左括号,我们直接把它放入栈中,继续读入,因为它在数学运算中左边不能有数字。

 

   如果是右括号,我们就要进行从栈顶开始的括号匹配,将右括号右边的运算符(一定是运算符)存起来放在结构体里。此时的运算符只有+和×,我们只要按顺序进行就可以了,匹配的同时做递推。同时匹配到左括号时停止,并把存的运算符加给当前的结果。

 

   当我们检测到栈中次顶元素所带的操作符是×号,我们就要立即进行运算。因为×比+优先级高,但是如果出现×(+),就会在上一步中跟下去着运算,等到退栈时会回来。而(+)×这种情况是不会存在的,因为前面匹配到完整的括号一定会消掉。

 

   当字符串匹配完后,结果可能是(……)或……,而其中只有加法(乘法被处理完了),我们就无脑匹配,特判最后一个是不是‘(’就可以了。

 

   剧毒的普及组题啊。。。

 

Code:

#include<cstdio>
#include<cstring>

char c[200000];
struct node
{
    int v[2];
    char op;
    node()
    {
        v[0]=1;
        v[1]=1;
    }
};
node s[200000];
int top=0;
int cnt=0;
int main()
{
    //freopen("testdata.in","r",stdin);
    int n;
    scanf("%d",&n);
    scanf("%s",c);
    int ans=0;
    node p,q;
    for(int i=0;i<=n;i++)
    {
        p.op=c[i];
        p.v[0]=1;
        p.v[1]=1;
        s[++top]=p;
        if(p.op=='(')
            continue;
        if(s[top-1].op=='*')
        {
            p=s[top--];
            q=s[top--];
            node t;
            t.op=p.op;
            t.v[0]=p.v[0]*q.v[0]+p.v[0]*q.v[1]+p.v[1]*q.v[0];
            t.v[1]=p.v[1]*q.v[1];
            t.v[0]%=10007;
            t.v[1]%=10007;
            s[++top]=t;
        }
        while(p.op==')')
        {
            s[top].op=c[++i];
            while(s[top-1].op!='(')//一定只剩加法?
            {
                p=s[top--];
                q=s[top--];
                node t;
                t.op=p.op;
                t.v[0]=p.v[0]*q.v[0];
                t.v[1]=p.v[0]*q.v[1]+p.v[1]*q.v[0]+p.v[1]*q.v[1];
                t.v[0]%=10007;
                t.v[1]%=10007;
                s[++top]=t;
            }
            p=s[top--];
            s[top]=p;
            if(s[top-1].op=='*')
            {
                p=s[top--];
                q=s[top--];
                node t;
                t.op=p.op;
                t.v[0]=p.v[0]*q.v[0]+p.v[0]*q.v[1]+p.v[1]*q.v[0];
                t.v[1]=p.v[1]*q.v[1];
                t.v[0]%=10007;
                t.v[1]%=10007;
                s[++top]=t;
            }
        }//可能还有乘法
    }
    int k=(s[1].op=='(')+1;
    while(top>k)
    {
        p=s[top--];
        q=s[top--];
        node t;
        t.op=p.op;
        t.v[0]=p.v[0]*q.v[0];
        t.v[1]=p.v[0]*q.v[1]+p.v[1]*q.v[0]+p.v[1]*q.v[1];
        t.v[0]%=10007;
        t.v[1]%=10007;
        s[++top]=t;
    }
    printf("%d\n",s[k].v[0]);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */