ZOJ1246 Instant Complexity

原题通道：ZOJ1246

大概思路：用深搜的思想+数组的加减去模拟括号的进入和弹出。并且用数组的加减操作模拟数据项的加减操作，具体题意看了下面的输入输出应该能理解。

直接看输出输入

输入

Sample Input 
2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END
BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END

输出

Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

2表示有两个测试样例，其中BEGIN表示每个测试样例的开始。看下第一个样例的情况。
LOOP n -> n×( )
OP 4 -> n×( 4 + )
LOOP 3 -> n×( 4 + 3×( ) )
LOOP n -> n×( 4 + 3×( n×( ) ) )
OP 1 -> n×( 4 + 3×( n×( 1 ) ) )
END OP 2 -> n×( 4 + 3×( n×( 1 ) + 2 ) )
END OP 1 -> n×( 4 + 3×( n×( 1 ) + 2 ) + 1 )
END OP 17 -> n×( 4 + 3×( n×( 1 ) + 2 ) + 1 ) + 17
所以最后的结果就是：n×( 4 + 3n + 6 + 1 ) + 17 = 3n^2 + 11n + 17

就是，LOOP表示进一个括号，OP表示在括号里面进行加减，END表示跳出一个括号

每个LOOP对应一个END，BEGIN对应一个END

看了输入输出基本上就差不多已经理解题目了，然后要注意，n×( n×(n×( )))，也就是

2
BEGIN
LOOP 1
LOOP 1
LOOP 1
END
END
END
END
BEGIN
END

这两个例子的结果都是0

代码解析

1. 因为OP 和 LOOP后面的可以是n，也可以是1~9，也可以是>10，所以我用string接收后面的参数，如果第一个字符不是n，则转化为int型

int getInt(string s){   //用来把一个字符串转化为int型数据
    int num = 0,ff = 1;
    for(long i = s.size() - 1; i>=0; i--){
        num += (s[i]-'0')*ff;
        ff *= 10;
    }
    return num;
}

2. 数组相乘和相加。int temp[] = {1,2,6,4……}，这个数组表示1+2n+6n^2+4n^3，也就是用数组下标表示幂次方，数组元素表示对应的系数。所以用以下两个函数表示一个数（n或者一个数）乘以一个数组和两个数组相加。

void mul(string w,int (&temp)[N]){   //一个数乘以一个数组
    if(w[0]>='0'&&w[0]<='9'){
        int kw = getInt(w);
        for(int i=0; i<N; i++) temp[i] *= kw;
    }else{
        for(int i=N-1; i>0; i--)
            temp[i] = temp[i-1];
        temp[0] = 0;
    }
}
void add(int (&a)[N],int (&temp)[N]){   //两个数组相加
    for(int i=0; i<N; i++)
        temp[i] = temp[i] + a[i];
}

3. 用dfs表示递进和，如果是OP操作，则进行加操作。如果是LOOP操作，则先dfs()取得递归层的结果集，因为是引用操作，所以dfs(k)之后，k里面已经有数据了，所以可以执行mul(ch,k)操作，执行操作之后继续在本dfs()中，直到遇到END则退出到上一个dfs()中。用一点深搜的思想来模拟括号的进入和弹出

void dfs(int (&temp)[N]){
    string ch;
    while(cin>>str&&str!="END"){
        cin>>ch;
        if(str=="OP"){
            if(ch[0]>='0'&&ch[0]<='9'){   //下标0处直接加
                int cot = getInt(ch);
                temp[0] += cot;
            }
            else temp[1] += 1;   //如果是OP n，则加在下标为1的位置
        }else if(str=="LOOP"){
            int k[N] = {0};
            dfs(k);
            mul(ch,k);
            add(k,temp);
        }
    }
}

完整代码如下

#include <iostream>
#include <string>
#define N 21
using namespace std;
string str;
int getInt(string s){
    int num = 0,ff = 1;
    for(long i = s.size() - 1; i>=0; i--){
        num += (s[i]-'0')*ff;
        ff *= 10;
    }
    return num;
}
void mul(string w,int (&temp)[N]){
    if(w[0]>='0'&&w[0]<='9'){
        int kw = getInt(w);
        for(int i=0; i<N; i++) temp[i] *= kw;
    }else{
        for(int i=N-1; i>0; i--)
            temp[i] = temp[i-1];
        temp[0] = 0;
    }
}
void add(int (&a)[N],int (&temp)[N]){
    for(int i=0; i<N; i++)
        temp[i] = temp[i] + a[i];
}
void dfs(int (&temp)[N]){
    string ch;
    while(cin>>str&&str!="END"){
        cin>>ch;
        if(str=="OP"){
            if(ch[0]>='0'&&ch[0]<='9'){
                int cot = getInt(ch);
                temp[0] += cot;
            }
            else temp[1] += 1;
        }else if(str=="LOOP"){
            int k[N] = {0};
            dfs(k);
            mul(ch,k);
            add(k,temp);
        }
    }
}
int main(int argc, const char * argv[]) {
    int T,flag;
    cin>>T;
    for(int l = 1; l<=T; l++){
        cin>>str;
        int temp[N] = {0};  //初始化数据
        dfs(temp);   //递归得到结果集
        cout<<"Program #"<<l<<endl<<"Runtime = ";
        flag = 0;
        for(int i=N-1; i>=0; i--)   //遍历结果集并输出
            if(temp[i]!=0){
                if(flag) cout<<"+";
                else flag = 1;
                if((i!=0&&temp[i]!=1) || i==0) cout<<temp[i];
                if(i>0&&temp[i]!=1) cout<<"*n";
                else if(i>0&&temp[i]==1) cout<<"n";
                if(i>1) cout<<"^"<<i;
            }
        if(flag==0) cout<<"0";  //如果不存在，则输出0
        cout<<endl<<endl;
    }
    return 0;
}

看网上好像没有这题的题解，顺手写一个……