noip2018普及组初赛解析_NOIP复赛

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

本题大意如下：

NOIP2011普及组——表达式的值

Description

对于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 。

Input

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

Output

输出文件exp.out 共1 行。包含一个整数，即所有的方案数。注意：这个数可能会很大，请输出方案数对10007 取模后的结果。

Sample Input

4
+(*)

Sample Output

3

Data Size & Hint

给定的表达式包括横线字符之后为：+(_*)?
在横线位置填入(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% 的数据输入表达式中不含括号。

博主是一个逗逼的高中生，在进行noip训练的时候遇到这一题，当时写了2个多小时
惭愧啊惭愧，
只能感叹一声普及组好可怕！！！
然而这题在code.vs里只有黄金。。。
我现在很怀疑自己是怎么做出那些大师题的。。。
原题链接在此：
http://codevs.cn/problem/1133/
好了，现在我们来分析一下这个题目。
这个题目中读入的字符串是只有‘*’、‘+’、‘（‘和’）‘的，而左右括号是互相配对的，优先级最高。
因此我们可以在栈中加入左括号的位置，在遇见右括号的时候依次取出栈中的值即可
在计算时有意思的是这个式子中是没有数字的，原题只是需要计算填完数字后值为0的情况总数而已
这个时候一些码农同志们可能就会不考虑复杂度直接开敲
给各个位置都填上数值，最后check。。。
这种人我也是醉了，博主对此不作评价
而正常人在开敲每道题的代码之前总是会总结一些什么的
在这一道题中
如果我们把数对（a，b)当做一个数Si分别为为0、1的情况数
那么很容易可以得出：

（a，b）*（c，d）=（ac+bc+ad，bd）；
（a，b）+（c，d）=（ac，bc+ad+bd）；

知道了这个性质之后同志们就可以开始敲代码了，每次把括号中的值算好后储存在左括号的位置即可
需要注意的是循环中的下标的变化并能连续的，否则复杂度为O（n^2）会超时
这个时候就需要一点简单的小技巧了，每次计算完一个括号中的值时，将左括号的nxt指向右括号，保证不重复遍历某一子串。
而且这个解法如果使用c++数据库中的string可以简单很多，好吧，其实没啥区别
代码如下：

//PS：原题有特别说明，将结果mod10007
#include<string>
#include<vector>
#include<iostream>
using namespace std;
#define M 300005
#define P 10007
string str;
int pre[M],nxt[M];
struct node{
    int a,b;
    node init(){
  
  //初始化每个数为0或1的情况数
        a=1;b=1;
    }
}ans,res[M];
struct li{
    int l,r;
};
vector<li>edge;
void add(node &A,node B){
    node C;
    C.a=(A.a*B.a)%M;
    C.b=(A.a*B.b+A.b*B.a+A.b*B.b)%M;
    A=C;
}// 加法计算
void mul(node &A,node B){
    node C;
    C.a=(A.a*B.a+A.a*B.b+A.b*B.a)%M;
    C.b=A.b*B.b%M;
    A=C;
}//乘法运算
int main(){
    int n;
    cin>>n;
    cin>>str;
    str.insert(0," ");
    for(int i=0;i<str.length();i++)res[i].init();
    int top=0;
    for(int i=0;i<str.length();i++){
        if(str[i]=='(')pre[top++]=i;
        else if(str[i]==')'){
            int p=pre[--top],s=p,cnt=0;
            li tmp;
            tmp.l=p,tmp.r=i;
            edge.push_back(tmp);
        }//好吧，这里是博主智障了，其实完全可以再加上1层for直接计算括号中的值。
       //反正仍旧是O(n)复杂度
        //（其实这里是博主当初敲O(n^2)WA代码的时候想的优化，然而似乎并没有什么软用）
    }for(int i=0;i<str.length();i++)nxt[i]=i+1;
    for(int k=0;k<edge.size();k++){
        li tmp=edge[k];
        int p=tmp.l,i=tmp.r,s=p;
        for(int j=p+1;j<i;j=nxt[j])
            if(str[j]=='(')res[j-1]=res[j];//将括号中计算好的结果导出
        for(int j=p+1;j<i;j=nxt[j]){
            if(str[j]=='*')mul(res[s],res[j]);//先计算乘法
            else if(str[j]=='+')s=j;//若遇到加号，略过它，并且之后的乘法需要累加到这个加号上。。
                                        //这一点相信有点智商的小朋友都能明白
        //至于为什么要累加到加号上，这纯粹是因为博主不想在运算符之中插入一个个空格，影响式子的美感罢了
        }s=p;                                                      //（好吧，我承认我懒。。）
        for(int j=p+1;j<i;j=nxt[j])
            if(str[j]=='+')add(res[s],res[j]);//最后再进行加法运算
        nxt[p]=i;//将左括号的nxt指向右括号
    }
    //*
    for(int i=1;i<str.length();i=nxt[i])
        if(str[i]=='(')res[i-1]=res[i];
    int s=0;
    for(int i=1;i<str.length();i=nxt[i]){
        if(str[i]=='*')mul(res[s],res[i]);
        else if(str[i]=='+')s=i;
    }s=0;
    for(int i=1;i<str.length();i=nxt[i])
        if(str[i]=='+')add(res[s],res[i]);
        *//中间带注释的这一段你可以选择略过它，
     //因为这本就是博主一时懵逼敲的。。
    //后来才察觉，可以直接用string.insert往整个式子的开头和末尾在插入一对括号就行了。。。 
    cout<<res[0].a<<endl;
    return 0;
}