20240502比赛总结

[NOIP2017 提高组] 时间复杂度

https://gxyzoj.com/d/hzoj/p/3673

按题意模拟即可

时间复杂度的计算方式是：

1. 常数->常数 O(1)

2. 常数->n O(n)

3. n->n O(1)

就是细节很多，也不会算时间复杂度，挂成了40

代码：

#include<cstdio>
#include<iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
int T,n,tim,st[105],top,ax[105],ay[105];
string t,name[105];
bool use[30];
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		cin>>t;
		tim=0;
		if(t!="O(1)")
		{
			for(int i=4;i<=t.size()-2;i++)
			{
				tim=tim*10+t[i]-'0';
			}
		}
		int ans=0,cnt=0,fl=0;
		for(int i=1;i<=n;i++)
		{
			ax[i]=ay[i]=0;
			string opt;
			cin>>opt;
			if(opt[0]=='F')
			{
				string x,y;
				cin>>name[i]>>x>>y;
				st[++top]=i;
				int tmp=name[i][0]-'a';
				if(use[tmp])
				{
					fl=1000;
					continue;
				}
				if(fl) continue;
				use[tmp]=1;
				int a=0,b=0;
				if(x[0]=='n') a=200;
				else
				{
					for(int i=0;i<x.size();i++) a=a*10+x[i]-'0';
				}
				if(y[0]=='n') b=200;
				else
				{
					for(int i=0;i<y.size();i++) b=b*10+y[i]-'0';
				}
				if(a>b)
				{
					fl=i;
					continue;
				}
				if(b>a&&b==200) cnt++;
				ans=max(ans,cnt);
				ax[i]=a,ay[i]=b;
			}
			else
			{
				if(top==0)
				{
					fl=1000;
					continue;
				}
				int x=st[top];
				top--;
				int tmp=name[x][0]-'a';
				use[tmp]=0;
				if(fl==x) fl=0;
				if(ax[x]<ay[x]&&ay[x]==200&&!fl) cnt--;
			}
		//	printf("%d %d\n",top,cnt);
		}
		if(fl==1000) printf("ERR\n");
		else if(top) printf("ERR\n");
		else if(ans==tim) printf("Yes\n");
		else printf("No\n");
		for(int i=0;i<=26;i++)
		{
			use[i]=0;
		}
		top=0;
	}
	return 0;
}