2011年Noip普及组第四题解析
本文最后更新于 408 天前,其中的信息可能已经有所发展或是发生改变。

(这题有点难)

这道题的步骤很简单:
①:将式子从+(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原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接: https://nth.ink/cpp/P1855.html

(广告由我们的赞助商提供,内容与本站无关)

评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇