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

原题链接

• 洛谷 P5698 [CTSC1998] 算法复杂度

解题思路

1. 分析

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

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

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

2. 计算

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

初始设多项式 $P=0$。

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

• $\texttt{end}$：循环结束。

• $\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$。

3. 输出

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

1. 如果系数 $a_i=0$，不用输出。
2. 如果前面有输出，需要输出 +。
3. 对于常数项，输出系数 $a_0$。
4. 对于非常数项，系数 $a_i\not=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;
}