noip 2017 时间复杂度

自认为是少有的复杂的代码

这题思想很简单,就是大模拟

对于for循环,一行读入4个字符串,然后分类讨论:

①:如果是一个正常的O(n),那么累计n的指数加1

②:如果是一个常数级别的,那么继续循环,但是不累计指数

③:如果这个循环是从n到常数,或大常数到小常数,那么这个循环及它内部的循环都不进,打好标记不要累计

④:至于如何防止变量的重复使用:将用过的变量放进栈里并打上标记,循环结束时出栈清标记即可

⑤:还要注意一些小细节:循环层数只计最深的一层,所以我们用一个累计变量cnt,每次结束循环考虑循环的情况:如果这个循环被累计了,cnt--,否则cnt不变,所以我们还要开一个栈,记录每个循环的情况(与存变量的栈同步使用即可)

剩下就好办了:

#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
using namespace std;
char s[];
char s1[],s2[];
char tt[];
bool used[];
int n;
stack <char> Q;
stack <int> M;
int main()
{
scanf("%d",&n);
while(n--)
{
int l;
scanf("%d",&l);
scanf("%s",tt);
int flag=;
int flag0=;
int flag2=;
int cnt=,maxcnt=;
memset(used,,sizeof(used));
while(!M.empty())
{
M.pop();
Q.pop();
}
for(int i=;i<=l;i++)
{
scanf("%s",s);
if(flag0)
{
if(s[]=='F')
{
scanf("%s",s);
scanf("%s",s);
scanf("%s",s);
}
continue;
}
if(s[]=='E')
{
if(!flag)
{
flag0=;
continue;
}else
{
char c=Q.top();
used[c]=;
Q.pop();
flag--;
int y=M.top();
if(y==)
{
cnt--;
}else if(y==)
{
flag2=;
}
M.pop();
}
}else
{
scanf("%s",s);
if(used[s[]])
{
flag=;
scanf("%s",s);
scanf("%s",s);
continue;
}
used[s[]]=;
Q.push(s[]);
scanf("%s",s1);
scanf("%s",s2);
flag++;
if(s1[]-''<=&&s2[]-''<=&&s1[]-''>=&&s2[]-''>=)
{
int j=;
int x=;
while(s1[j]-''<=&&s1[j]-''>=)
{
x=x*+s1[j]-'';
j++;
}
int y=;
j=;
while(s2[j]-''<=&&s2[j]-''>=)
{
y=y*+s2[j]-'';
j++;
}
if(x>y)
{
flag2=;
M.push();
}else
{
M.push();
}
continue;
}else if(s2[]-''<=&&s2[]-''>=)
{
M.push();
flag2=;
continue;
}else
{
if(s2[]=='n'&&s1[]=='n')
{
M.push();
continue;
}
if(!flag2)
{
cnt++;
M.push();
}else
{
M.push();
}
maxcnt=max(maxcnt,cnt);
}
}
}
if(flag)
{
flag0=;
}
if(flag0)
{
printf("ERR\n");
continue;
}else if(maxcnt==&&tt[]=='')
{
printf("Yes\n");
continue;
}else
{
int j=;
int x=;
while(tt[j]-''<=&&tt[j]-''>=)
{
x=x*+tt[j]-'';
j++;
}
if(x==maxcnt)
{
printf("Yes\n");
continue;
}
printf("No\n");
continue;
}
}
return ;
}
上一篇:MySQL 存储过程和存储函数学习


下一篇:jQuery技术内幕预览版.pdf3