[NOIP2017]时间复杂度

发布于 2017-12-03  44 次阅读



题目(洛谷)
用栈来大模拟......
代码写得比较杂也不一一解释了......
总之注意几种情况:
ERR的情况:1.栈都空了还在E    2.栈中出现相同字母
然后就是合法情况了:

  1. 常数 -> 常数  O(1),并且判断后面那个常数是否大于等于前面那个
  2. 常数 -> n  ++O
  3. n->常数  O(1)且不进入循环
  4. n->n  O(1)且进入循环

完了?
完了。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <climits>
#define ll long long
#define llmax LONG_LONG_MAX
#define llmin LONG_LONG_MIN
#define readf(f) scanf(
#define putY puts("Yes")
#define putN puts("No")
#define putE puts("ERR")
#define check ans=max(ans,cnt)
using namespace std;
inline void init()
{
	freopen("complexity.in","r",stdin);
	freopen("complexity.out","w",stdout);
}
template <class _E> inline void read(_E &e)
{
	e=0;bool ck=0;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ck=1;ch=getchar();}
	while(ch>='0'&&ch<='9'){e=e*10+ch-'0';ch=getchar();}
	if(ck)e=-e;
}
stack <int> s;
bool vis[30];
char o[105];
int which[105];
bool chang[105];
int t;
inline void chushi();
inline int gettmp()
{
	int len=strlen(o);
	int ret=0;
	for (int i=4;i<len-1;++i)
		ret*=10,ret+=(o[i]-'0');
	return ret;
}
inline int getnum(char *p)
{
	int len=strlen(p);
	int ret=0;
	for (int i=0;i<len;++i)
		ret*=10,ret+=(p[i]-'0');
	return ret;
}
int main()
{
//	init();
	read(t);
	while (t--)
	{
		chushi();
		int L;
		read(L);
		int cnt=0,tmp=0,ans=0,da=0,huan=0;
		scanf(
		if (o[2]=='n') tmp=gettmp();
		else tmp=0;
		bool can=true,dayu=false;
		while (L--)
		{
			char c,i,x[5],y[5];
			cin>>c;
			if (c=='F')
			{
				s.push(2);
				cin>>i;
				scanf(
				scanf(
				if (vis[i-'a']) can=false;
				vis[i-'a']=1;
				++huan;
				which[huan]=i-'a';
				if (dayu)
				{
					++da;
					continue;
				}
				if (x[0]!='n' && y[0]=='n')
				{
					++cnt;
					check;
				}
				else if ((x[0]!='n' && y[0]!='n') || (x[0]=='n' && y[0]=='n'))
				{
					chang[huan]=1;
					int n1=getnum(x),n2=getnum(y);
					if (n1>n2)
					{
						dayu=true;
						++da;
					}
					else
					{
						check;
					}
				}
				else if (x[0]=='n' && y[0]!='n')
				{
					dayu=true;
					++da;
				}
			}
			else if (c=='E')
			{
				if (s.empty()) can=false;
				else if (s.top()==2)
				{
					s.pop();
					if (dayu)
					{
						--da;
						if (!da) dayu=false;
					}
					else if (!chang[huan]) --cnt;
					chang[huan]=0;
					vis[which[huan]]=0;
					if (huan) --huan;
				}
				else can=false;
			}
		}
		if (!s.empty() || can==false)
		{
			putE;
			continue;
		}
		if (ans==tmp) putY;
		else putN;
	}
	return 0;
}
inline void chushi()
{
	while (!s.empty()) s.pop();
	memset(vis,0,sizeof vis);
	memset(which,0,sizeof which);
	memset(chang,0,sizeof chang);
	memset(o,0,sizeof o);
}

哦对了,上面这份代码并不是我考试时提交的代码。
考试时94行的代码是这样的:

				else if (x[0]!='n' && y[0]!='n')

这句话就是在表明:我完全漏了n->n的情况......
但还是过了,因缺思厅。
后来思考了一下为什么会过,发现主要是ccf的数据很水......
我这么写会错的话就是在ERR上面会判断错误,如果栈中出现了两个相同字母的话。
而数据里面没有n->n还出现相同字母的情况。
于是就过了233