2011年Noip普及组第四题解析

本文作者：Zhang, Xuheng  本文分类：编程学习笔记  浏览：1357
阅读时间：1894字, 约2-3分钟

（这题有点难）

这道题的步骤很简单:
①:将式子从+(x)的形式变成的带有空的形式
②:将式子从中缀表达式化作后缀表达式
③:进行动态规划
状态转移方程:
设f[i][0]表示第i个空，能填0，f[i][1]表示第i个空，能填1
那么转移方程就出来了:

switch(w_c[i]){
                    case '+':{
                        f[top-1][1] = (f[top][0] * f[top-1][1] + f[top][1] * f[top-1][0] + f[top][1] * f[top-1][1])%10007;
                        f[top-1][0] = (f[top][0] * f[top-1][0]) % 10007; 
                        break;
                    }
                    case '*':{
                        f[top-1][0] = (f[top][0] * f[top-1][1] + f[top][1] * f[top-1][0] + f[top][0] * f[top-1][0])%10007;
                        f[top-1][1] = (f[top][1] * f[top-1][1]) % 10007;
                        break;
                    }
                }

代码如下：

#include <cstdio>
#include <stack> 
#include <iostream>
using namespace std;
int i,j,n,m;
string s,w_c;
char str[100001],first[3] = {'(','+','*'};
int f[100001][2];
stack<char> op;
    int OPS(char a){
        int i;
        for(i=0;i<3;i++){
            if(a == first[i]) return i;
        }
        return -1;
    }
    inline void ChangeS(){
        int i;
        for(i=0;i<n;i++){
            if(str[i] == '(') s.push_back(str[i]); 
            else if(str[i] == ')' && str[i-1] != ')') s+="_)";
            else if(str[i]!=')' && str[i-1] != ')') {
                s.push_back('_');
                s.push_back(str[i]);
            }
            else s.push_back(str[i]);  
        }
        if(s.at(s.size()-1)!=')') s.push_back('_');
    }

    inline void ChangeE(){


        size_t i;
        char t;
        for(i=0;i<s.size();i++){
            t = s.at(i);
            if(t == '_') w_c.push_back(t);
            else{
                if(t!=')'){
                    if(t=='(') op.push(t);
                    else{
                    if(op.empty()) op.push(t);
                    else{
                        while((!op.empty())&& OPS(op.top())>=OPS(t)) {
                            w_c.push_back(op.top());
                            op.pop();
                        }
                        op.push(t);
                    }
                }
            }
            else{
                while((!op.empty()) && op.top()!='('){
                    w_c.push_back(op.top());
                    op.pop();
                }
                op.pop();
            }
        }  
    }    
    while(!op.empty()){
        w_c.push_back(op.top());
        op.pop();
    }
}
    void work(){
        size_t i,top(0);
        size_t l = w_c.size();
        for(i=0;i<l;i++) {
            if(w_c[i] == '_'){
                f[top][0] = f[top][1] = 1;
                top++;
            }
            else{
                --top;
                switch(w_c[i]){
                    case '+':{
                        f[top-1][1] = (f[top][0] * f[top-1][1] + f[top][1] * f[top-1][0] + f[top][1] * f[top-1][1])%10007;
                        f[top-1][0] = (f[top][0] * f[top-1][0]) % 10007; 
                        break;
                    }
                    case '*':{
                        f[top-1][0] = (f[top][0] * f[top-1][1] + f[top][1] * f[top-1][0] + f[top][0] * f[top-1][0])%10007;
                        f[top-1][1] = (f[top][1] * f[top-1][1]) % 10007;
                        break;
                    }
                }
            }
        }
        printf("%d",f[top-1][0]);
}

int main(){
    scanf("%d",&n);
    scanf("%s",str);
    ChangeS();
    ChangeE(); 
    //for(i=0;i<=w_c.length();i++) printf("%c",w_c[i]); 
    work();
    return 0;
}

关于作者Zhang, Xuheng

• 还没有填写个人简介
• Email: hy23682@126.com
• 注册于: 2020-04-07 05:11:14