10月28日考试解题报告

考试中的心路历程

说实话第一道题和第三道题真的是水题，然鹅我只搞到了100分，感觉有些亏，最后一题看错了题目，导致我的思路开始各种螺旋，当其他人都为第二题思考的时候，我居然在想第三题的优化？！感觉没爱了….果然以后还是得更加专心的看题目，不能想太多（当然也不能太少），至于第二题。。。没做，只有一个印象：恶心！

第二题

题目
【题目描述】
给出一个表达式，包含数字、未知数x、“+”、“-”、“*”和括号。把它化简成a0x0+a1x1+a2x2+……+anxn的形式。
【输入格式】
一行一个字符串，即表达式。
【输出格式】
第一行一个非负整数n，接下来n+1个数，其中第i行为ai-1。由于ai可能很大，对10007取模后输出。
若有多个n满足条件，输出最小的n。
【样例输入】
(x-2)*3+x
【样例输出】
1
10001
4

做题思路
没做怎么办。。。只感觉到好恶心。。。
题解
emmmmm。。。自己在改的时候只专注于弄数字去了，结果好不容易搞定单纯的数字乘法后，突然发现居然不知道怎么插入x了，真的尴尬了。。。
后面orange大佬讲了一下思路虽然没有全过程在听，但是因为大佬的奥秘代码，于是很快理解了，%%%。。。然后自己再打了一遍，加了自己的许多注释，就更加有成就感了，但还是自己打出AC的话成就感更强。。。思路大概都在代码上了，理解应该没问题;
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<string>
#include<stack>
using namespace std;
struct node
{
    void check(node &q);//膜10007(为什么老是这个数); 
    int len;
    int xi[500];
    node operator + (const node &x)
    {
        len=max(len,x.len);//最大长度; 
        for(int i=0;i<=len;i++)xi[i]+=x.xi[i];//相同系数相加; 
        return *this;//把(雷姆)丢回去; 
    }
    node operator - (const node &x)
    {
        len=max(len,x.len);//最大长度; 
        for(int i=0;i<=len;i++)xi[i]-=x.xi[i];//相同系数相加; 
        if(xi[len]==0)len--;//去除多余长度; 
    return *this;
    } 
    node operator * (const node &x)
    {
        node y;
        memset(y.xi,0,sizeof(y.xi));//似乎不清0就没有初始值; 
        y.len=len+x.len;//两个相乘，系数相加;
        for(int i=0;i<=len;i++)
            for(int j=0;j<=x.len;j++)
                y.xi[i+j]+=xi[i]*x.xi[j];//组合起来？？ 
        return y; 
    }
};
stack <node> st;//多项式栈 
stack <char> ch;//符号栈 (直接搬大佬的定义算了);
string s;
void check(node &q)
{
    for(int i=0;i<=q.len;i++)
    {
        while(q.xi[i]<0) q.xi[i]+=10007;//看到 
        q.xi[i]%=10007; 
    }
}
void work()
{
    if(ch.top()=='+')//+; 
    {
        node x=st.top(); st.pop();
        node y=st.top(); st.pop();
        x=x+y;
        st.push(x); 
    }
    else if (ch.top()=='-')//-;
    {
        node x=st.top(); st.pop();
        node y=st.top(); st.pop();
        x=y-x;
        st.push(x);
    }
    else//乘法; 
    {
        node x=st.top(); st.pop();
        node y=st.top(); st.pop();
        x=x*y;
        st.push(x);
    }//从这里就看出了重载运算符的快速之处了; 
    check(st.top());
    ch.pop();//这里是丢掉运算符,不是左边括号(说明右括号还是有些良心的); 
}
bool judge(char c){
    if ((c=='+'||c=='-')&&ch.top()!='(') return true;
    if (c=='*'&&ch.top()=='*') return true;
    return false;
}
int main()
{
    cin>>s;
    s="(0+"+s+"+0)";//要给它加个buff;
    node x;//x的系数就存在这里面;
     memset(x.xi,0,sizeof(x.xi));//不清0似乎就有问题; 
    x.len=1;
    x.xi[1]=1; //初始化;
    int p=0,len=s.size();
    while(p<len)//这里如果用s.size()的话就会每次多一个o(n)的运算; 
    {
        while(s[p]=='(')//处理左边的括号; 
        {
            ch.push('(');//入栈; 
            p++;  
        }
        if(s[p]<='9'&&s[p]>='0')//好了，终于处理数字了;
        {
            node y;//又定义y。。。有点没味,来点其他的不也挺好么;
            y.len=0;
            memset(y.xi,0,sizeof(y.xi));//一次又一次的为y清0;
            while(s[p]<='9'&&s[p]>='0')y.xi[0]=y.xi[0]*10+s[p++]-'0';//p++...好省代码; 
            st.push(y);//再次把(雷姆)丢回去; 
        } 
        do
        {
            if(s[p]==')'){//对)处理;
            while(ch.top()!='(') work();//发现打了//的k会不一样！
              ch.pop();//丢掉它的另一半2333; 
        }
        else if(s[p]=='x') st.push(x);//处理的这么冷漠的吗？
        else //处理那些符号了; 
            {
                while(judge(s[p]))work();
                ch.push(s[p]); 
            } 
            p++;
        } 
        while(p<len&&s[p-1]==')');
    }
    node ans=st.top();//最后只剩下一个孤苦老人了; 
    printf("%d\n",ans.len);
    for(int i=0;i<=ans.len;i++) printf("%d\n",ans.xi[i]);
}