P3952 NOIP2017 时间复杂度

写了两三个小时,麻烦倒是不麻烦,要考虑清楚,想全了
只过了样例提交是不是傻,要自己造数据
数据不大可以用STL
建议自己刚一下,不看代码

#include <iostream>
#include <stack>
#include <cstring>
#include <cstdio>
using namespace std;
int n;
char a[200][200];
int fuzadu;
int vis[30];
struct node {
	int zimu,id,fzd;
	node(int a,int b,int c) {
		zimu=a;id=b;fzd=c;
	} 
//zimu是最后用来删除的,id是check弹栈用的 ,fzd是判断这个F是否能有贡献,是不是O(n)的 
};
stack<node> sta;
void read()
{
	while(!sta.empty()) sta.pop();
	memset(a,0,sizeof(a));
	memset(vis,0,sizeof(vis));
	scanf("%d O(",&n);
	char s=getchar();
	if(s=='n') {
		scanf("^%d)",&fuzadu);
	} else fuzadu=0;
	while(s!='
')s=getchar();
	for(int i=1;i<=n;++i)
		cin.getline(a[i]+1,'
');
}
bool check(int &i,int dsr)
{
	++i;
	for(;i<=n;++i)
	{
		if(a[i][1]=='F') //F 
		{
			//处理 循环变量
			if(vis[a[i][3]-'a']) { //如果出现过的话,ERR 
				return 1;
			} else {
				vis[a[i][3]-'a']=1; //vis数组++ 
				sta.push(node(a[i][3]-'a',i,0));//加入栈 
			}
		} else { //E 
			if(a[i][1]=='E') { //如果结束这个循环 
				if(sta.empty()) { return 1;}//没有对应的F,ERR 
				vis[sta.top().zimu]=0;// 这个F的字母以后可以用了 
				if(sta.top().id==dsr) {
					sta.pop();return 0;
				}
				sta.pop(); //在栈中删除 
			}
		}
	}
	return 0;
} 
void solve()
{
	read();
	int js=0;//时间复杂度 
	int ans=0;//最大复杂度 
	for(int i=1;i<=n;++i)
	{
		if(a[i][1]=='F') //F 
		{
			//处理 循环变量 
			if(vis[a[i][3]-'a']) { //如果出现过的话,ERR 
				{ puts("ERR");return;}
			} else {
				vis[a[i][3]-'a']=1; //vis数组++ 
			}
			
			//F的范围 
			int j=5,x=0,y=0;
			if(a[i][5]=='n') {
				sta.push(node(a[i][3]-'a',i,0));//一定不可能是复杂度一定不可能是O(1)的
			//如果第一个数是n,那么只有第二个数也是n才能进入循环(复杂度O(1)),否则就直到弹栈为止
 				if(a[i][7]!='n') { //只需要检查是否ERR即可 
 					
				 	if(check(i,i)) {
						puts("ERR");return;
					}			
				}
			} else {
				while(a[i][j]>='0'&&a[i][j]<='9') {x=x*10+a[i][j]-'0';j++;} j++;//读入x
				if(a[i][j]=='n') {
					sta.push(node(a[i][3]-'a',i,1));
					js++;//如果第1个是数字第2个是n,复杂度++ 
					ans=max(ans,js); //更新最高复杂度 
				}
				else {
					sta.push(node(a[i][3]-'a',i,0));
					while(a[i][j]>='0'&&a[i][j]<='9') {y=y*10+a[i][j]-'0';j++;} j++;
					//如果都是数字,分为可以进入和不可以进入 
					if(x>y) {//不可以进//只需要检查是否ERR即可入
						if(check(i,i)) {
							puts("ERR");return;
						}
					}
					//可以进入就不管啦,复杂度O(1) 	
				}
			}			
		} else { 
			//处理E 
			if(a[i][1]=='E') { //如果结束这个循环 
				if(sta.empty()) { puts("ERR");return;}//没有对应的F,ERR 
				vis[sta.top().zimu]=0;// 这个F的字母以后可以用了 
				js-=sta.top().fzd;//这个复杂度也得--,所以要过程中取max 
				sta.pop(); //在栈中删除 
			}
		}
	} 
	if(sta.size()) 
		puts("ERR");
	else if(ans==fuzadu)
		puts("Yes");
	else puts("No");
}
int main()
{
//	freopen("a.in","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--)
		solve();
	return 0;	
}
原文地址:https://www.cnblogs.com/dsrdsr/p/9548509.html