题解：P5698 [CTSC1998] 算法复杂度

lailai0916 · 2024-01-06 16:22:54 · 题解

解题思路

思想

时间复杂度是一个不超过 20 次的多项式。

用 f(k) 模拟执行 k 次的循环的复杂度。

特别地，令 k=0 表示执行 n 次。

计算

考虑计算 f(k) 的复杂度。

初始时，设多项式 P=0。

循环读入字符串 S 并分类讨论：

• \texttt{loop x <statement>}

  递归调用 f(x) 计算 \texttt{<statement>} 的复杂度。

  将 P\gets P+f(x)。

• \texttt{op <statement>}

  将 P\gets P+\texttt{<statement>}。

• \texttt{break <statement>}$ 或 $\texttt{continue <statement>}

  如果它（\texttt{break} 或 \texttt{continue}）不在任何一层循环中，请忽略它们。

  根据循环的嵌套关系，读入并忽略后面的语句。

  而 \texttt{break} 前的语句只会执行 1 次，即 k\gets1。

  特别地，如果当前是在最外层的大循环，直接忽略。

此时 P 为循环内的复杂度，一共要执行 k 次，所以该循环的总复杂度为 P\times k。

输出

倒序遍历多项式的 i 次项：

1. 如果系数 a_i=0，不用输出。
2. 如果前面有输出，需要输出加号 +。
3. 对于常数项，输出系数 a_0。
4. 对于非常数项，系数 a_i\ne 1 时输出 a_i；一次项输出 n，其余项输出 n^i。

特别地，如果没有任何输出，需要输出 0。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N=22;
struct Poly
{
    int a[N];
    Poly(){for(int i=0;i<N;i++)a[i]=0;}
};
Poly f(int k,bool b)
{
    Poly P;
    string s;
    while(cin>>s&&s!="end")
    {
        if(s=="loop")
        {
            cin>>s;
            Poly T=f(s=="n"?0:stoi(s),1);
            for(int i=0;i<N;i++)P.a[i]+=T.a[i];
        }
        else if(s=="op")
        {
            cin>>s;
            if(s=="n")P.a[1]++;
            else P.a[0]+=stoi(s);
        }
        else if((s=="continue"||s=="break")&&b)
        {
            if(s=="break")k=1;
            int t=1;
            while(t)
            {
                cin>>s;
                if(s=="loop")t++;
                else if(s=="end")t--;
            }
            break;
        }
    }
    if(k)for(int i=0;i<N;i++)P.a[i]*=k;
    else{for(int i=N-1;i>0;i--)P.a[i]=P.a[i-1];P.a[0]=0;}
    return P;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string s;
    cin>>s;
    Poly ans=f(1,0);
    bool b=0;
    for(int i=N-1;i>=0;i--)
    {
        if(ans.a[i]==0)continue;
        if(b)cout<<'+';
        if(i==0||ans.a[i]!=1)cout<<ans.a[i];
        if(i>1)cout<<"n^"<<i;
        else if(i==1)cout<<'n';
        b=1;
    }
    if(!b)cout<<0<<'\n';
    return 0;
}