NOIP 2017 DAY1 T2 时间复杂度
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/contest/265/E
题目链接
细节都放到代码注释里面了
#include<bits/stdc++.h>
using namespace std;
#define rg register
int t;
int n;
int flag;//1--常数复杂度 2--开方复杂度
int cf;//记录开的是几次方
char c[50],a[150][105];
int len_c;
inline void mes()
{
flag=0;
cf=0;
memset(c,0,sizeof(c));
memset(a,0,sizeof(a));
len_c=0;
}
inline bool solve_1()
{
int tot1,tot2;//1--统计F 2--统计E
int tot;//查看F与E是否一一匹配
tot1=tot2=tot=0;
for(rg int i=1;i<=n;++i)//统计整个程序中F和E的数量和位置关系
{
if(a[i][0]=='F') tot1++;
if(a[i][0]=='E') tot2++;
tot=tot1-tot2;
if(tot<0) return false;//如果出现一个F匹配多个E,则编译错误
}
if(tot1!=tot2) return false;//两者数量不同当然编译错误
return true;//当两个条件都满足时,则①情况满足,即F与E数量和位置都匹配
}
inline bool solve_2()
{
/*
需要注意的是
变量命名重复只在循环镶嵌中存在
*/
bool vis[223]={0},vit[1000]={0};//vis用来存变量名 vit用来存i
for(rg int i=1;i<=n;++i)
{
if(a[i][0]=='F')
{
if(vis[(int)a[i][2]]==1)
{
//cout<<"kokodayo"<<endl;
return false;
}
else
{
vis[(int)a[i][2]]=1;
}
}
if(a[i][0]=='E')
{
for(rg int j=i-1;j>=1;--j)
{
if(a[j][0]=='F'&&vit[j]==0)//vit说明这个循环还没结束
{
vit[j]=1;
vis[(int)a[j][2]]=0;//消除这个循环的影响;
break;
}
}
}
}
return true;
}
inline bool judge_wrong()
{
if(solve_1()==0) return false;//① F 和 E 不匹配
if(solve_2()==0) return false;//②新建的变量与已经存在但未被销毁的变量重复两种情况），则输出ERR 。
return true;
}
inline bool work_1()//判断该程序是否为常数复杂度
{
/*
ps:
判断常数复杂度(F i x y) i从x开始每次++直到y
1.单个循环同时x,y皆为常数满足要求(F i 1 2)
2.单个循环无法进入满足要求 (F i n 1)
3.单个循环x,y皆为n满足要求(F i n n) (存疑)
4.循环组每个循环皆为常数复杂度
5.循环组内在进入开方复杂度的循环之前已经结束
eg(5)
F a 1 8
F b n 3
F c 1 n
需要注意的是循环中n到n并不会直接结束,而是会循环一次,只有在x>y的时候该循环会直接结束,x=y时会循环一次,x<y时会循环y-x+1次
所以F i n n 视为常数复杂度的循环
*/
int tot1,tot2;//1--F的数量 2--E的数量
int tot;//==tot1-tot2
bool flag;//0--当前为单循环 1--为循环组
tot1=tot2=tot=flag=0;
for(rg int i=1;i<=n;++i)
{
if(a[i][0]=='F') ++tot1;
if(a[i][0]=='E') ++tot2;
tot=tot1-tot2;
if(tot==0&&tot1==1)//单循环
{
int k=4,ans1=0;
if(a[i-1][k]!='n')
{
while(a[i-1][k]!=' ')
{
ans1*=10;
ans1+=(int)(a[i-1][k]-48);
++k;
}
++k;
if(a[i-1][k]!='n')
{
tot1=tot2=tot=0;
continue;
}
else if(a[i-1][k]=='n') return false;
}
if(a[i-1][4]=='n')//2,3. 只要第一个为n 都满足
{
tot1=tot2=0;
continue;
}
return false;//单循环只有 1,2,3满足常数复杂度 如果前两个if 都不满足 则说明该方程不是常数复杂度 直接return false
}
if(tot==0&&tot1>1)//多循环
{
for(rg int j=i-tot1*2+1;j<=i-tot1;++j)//此处为从多循环第一个循环到最后一个循环的枚举
{
if(a[j][4]=='n'&&a[j][6]!='n')
{
tot1=tot2=tot=0;
break;//此时 x>y 整个循环组提前结束
}
if(a[j][4]=='n'&&a[j][6]=='n') continue;//此时这个循环只循环一次
if(a[j][4]!='n'&&a[j][6]=='n') return false;//此时这个循环已经是开方复杂度 return false
int k=4,ans1=0;
while(a[j][k]!=' ')
{
ans1*=10;
ans1+=(int)(a[j][k]-48);
++k;
}
++k;
int ans2=0;
while(a[j][k]<='9'&&a[j][k]>='0')
{
ans2*=10;
ans2+=(int)(a[j][k]-48);
++k;
}
// cout<<a[j][k-1]<<endl;
// cout<<ans1<<" "<<ans2<<" "<<k<<endl;
if(ans1>ans2)
{
tot1=tot2=tot=0;
break;//此时这个循环组提前结束
}
if(ans1==ans2) continue;//此时这个循环只循环一次
if(ans1<ans2) continue;//此时这个循环是常数复杂度要进入下一个循环
}
tot1=tot2=tot=0;
}
}
return true;
}
inline bool work_2()//判断该程序是否为开方复杂度
{
/*
判断是否为开方复杂度
两种情况分别讨论
一.为单循环
1.只需要满足 y=n 且x!=n 就行了
二.为循环组
1.至少有一个循环满足y=n 且x!=n
2.在达到该循环之前整个循环组不能结束
即之前某个循环不能出现x>y的情况
*/
int tot1,tot2;//1--F的数量 2--E的数量
int tot;//==tot1-tot2
int cnt1,cnt2;//统计当前是几次方 cnt1统计单循环 cnt2统计循环组
tot1=tot2=tot=cnt1=cnt2=0;
for(rg int i=1;i<=n;++i)
{
if(a[i][0]=='F') ++tot1;
if(a[i][0]=='E') ++tot2;
tot=tot1-tot2;
if(tot==0&&tot1==1)//单循环
{
int k=4,ans1=0;
if(a[i-1][k]!='n')
{
while(a[i-1][k]!=' ')
{
ans1*=10;
ans1+=(int)(a[i-1][k]-48);
++k;
}
++k;
if(a[i-1][k]=='n')
{
tot1=tot2=tot=0;
cnt1=1;
continue;
}
}
if(a[i-1][4]!='n'&&a[i-1][6]=='n')//满足条件一
{
tot1=tot2=tot=0;
cnt1=1;
continue;
}
if(a[i-1][4]=='n') return false;//当x=n 时,该单循环无论如何也不可能为开方级别复杂度
tot1=tot2=tot=0;
}
if(tot==0&&tot1>1)//多循环
{
int nt;//负责找到该多循环最多为几次方
nt=0;
for(rg int j=i-tot1*2+1;j<=i-tot1;++j)//此处为从多循环第一个循环到最后一个循环的枚举
{
if(a[j][4]=='n'&&a[j][6]!='n')//循环提前结束
{
tot1=tot2=tot=0;
cnt2=max(cnt2,nt);//更新几次方
break;
}
if(a[j][4]=='n'&&a[j][6]=='n') continue;
int k=4,ans1=0;
while(a[j][k]!=' ')
{
ans1*=10;
ans1+=(int)(a[j][k]-48);
++k;
}
++k;
if(a[j][k]=='n')
{
++nt;
cnt2=max(cnt2,nt);
continue;
}
int ans2=0;
while(a[j][k]<='9'&&a[j][k]>='0')
{
ans2*=10;
ans2+=(int)(a[j][k]-48);
++k;
}
if(ans1>ans2)
{
tot1=tot2=tot=0;
cnt2=max(cnt2,nt);//更新几次方
break;//此时这个循环组提前结束
}
}
tot1=tot2=tot=0;
}
}
cnt2=max(cnt2,cnt1);
if(cnt2!=cf) return false;
return true;
}
int main()
{
cin>>t;
while(t--)
{
mes();//清空
cin>>n;//程序行数
cin>>c;
len_c=strlen(c);
for(rg int i=0;i<len_c;++i)
{
if(c[i]=='(')
{
if(c[i+1]=='1')
{
flag=1;//常数复杂度
break;
}
if(c[i+1]=='n')
{
flag=2;
int k=i+3;
while(c[k]>='0'&&c[k]<='9')
{
cf*=10;
cf+=(int)(c[k]-48);
++k;
}
break;
}
}
}
char l=getchar();//读掉第一个换行
for(rg int i=1;i<=n;++i)
{
cin.get(a[i],101);
l=getchar();//读掉每个换行符
}
if(judge_wrong()==0)//判断是否存在语法错误
{//如果有则直接输出
cout<<"ERR"<<endl;
continue;
}
if(flag==1) //如果为常数复杂度
{
if(work_1()==0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
else// 如果为开方复杂度
{
if(work_2()==0) cout<<"No"<<endl;
else cout<<"Yes"<<endl;
}
}
}
小天才公司福利 691人发布
