如题
#include<cstdio>
#include<utility>
#include<vector>
#include<cstring>
#include<iostream>
#include<memory.h>
using namespace std;
const int inf=1e9;
struct node{
int end,times;//这个for循环的结束行与时间复杂度
//如果times=-1表示该行为E,否则表示该行所对应的循环的单个复杂度(只有0或1)
node(){}
node(int _en,int _ti){
end=_en; times=_ti;
}
};
bool used[26];
int t,k,num,flag,w,w0,pre[210];//上一个F出现的位置(不包括本行)
char cpy[21],ch;//cpy:complexity
node a[210];//a数组下标为开始行
string str;
inline int fgetn(){//将n看做无穷大的快读
int x=0; char c=getchar();
while((c<'0'||c>'9')&&c!='n') c=getchar();
while((c>='0'&&c<='9')||c=='n') x=((c!='n')?((x<<3)+(x<<1)+c-'0'):inf),c=getchar();
return x;
}
inline int fgetN(){//正常快读
int x=0; char c=getchar();
while(c<'0'||c>'9') c=getchar();
while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();
return x;
}
void fget(char &c,char &p,int &x,int &y){//读入每行的字符串
c=getchar();
if(c=='F'){
getchar(); p=getchar();
x=fgetn(); y=fgetn();
}
getchar();
}
int fget2(){//读入开头的复杂度
getchar();
getchar();//O(
char ch=getchar();
if(ch=='1') return 0;//O(1)
int w1=fgetN();//O(n^w)
//getchar(); getchar();//读掉换行符 )字符已经被读掉了
return w1;
}
inline int getm(int &a,const int b){
if(a<b) a=b;
}
int work(int st,int en){
int ans=0,i=st+1;
while(i<en){
if(a[i].times!=-1){
getm(ans,work(i,a[i].end));
i=a[i].end+1;
}
else i++;
}
return ans+a[st].times;
}
int main(){
ios::sync_with_stdio(false);
t=fgetN();
for(int i=1;i<=t;i++){
memset(a,0,sizeof(a));
memset(used,0,sizeof(used));
flag=-1,w=0,w0=0,num=0;//flag=1 Yes flag=2 No flag=0 ERR
k=fgetN();
// getchar();/*读掉空格*/
// ch=getchar();
w0=fget2();
a[0]=node(k+1,0);//相当于在前面放一个F,在后面放一个E
a[k+1]=node(-1,-1);
pre[0]=pre[1]=-1;
// getchar(); getchar(); getchar();
for(int j=1;j<=k;j++){
a[j]=node(-1,-1);
char c='\0',p='\0'; int x=0,y=0,ti=0;
fget(c,p,x,y);
// printf("%c %c %d %d\n",c,p,x,y);
// return 0;
if(c=='F'){
if(used[p-'a']){
flag=0;
break;
}
used[p-'a']=1;
}
if(x>y) ti=0;
else if(x!=inf&&y!=inf) ti=0;
else if(x==inf&&y==inf) ti=0;
else if(y==inf) ti=1;
if(c=='F'){
a[j].times=ti;
pre[j+1]=j;
// printf("Now it is the %d line, and the next line's pre is %d\n",j,pre[j+1]);
num++;
}
if(c=='E'){
if(pre[j]!=-1){
a[pre[j]].end=j;
pre[j+1]=pre[pre[j]];
num--;
}
else{
flag=0;
break;
}
}
}
//初始化 将F与E一一对应 a数组中
// for(int j=1;j<=k;j++) printf("%d ",pre[j]);
// putchar('\n');
// printf("%d\n",k);
// printf("%d\n",w0);
// for(int j=1;j<=k;j++)
// if(a[j].times!=-1) printf("%d %d %d\n",j,a[j].end,a[j].times);
// putchar('\n');
// putchar('\n');
if(num>0) flag=0;
if(flag==0){
puts("ERR");
continue;
}
w=work(0,k+1);
if(w==w0)
puts("Yes");
else
puts("No");
}
return 0;
}
这是用动态处理再加上FE动态匹配来做的,时间复杂度理论上是O(tk),结果本机一直在getchar()上面出一些玄学错误,洛谷的评测姬又没有调试功能~~(跪求awa)~~
然后就没有然后了,如果换用字符串又会出像如下的错误:
terminate called after throwing an instance of 'std::length_error'
what(): basic_string::_S_create
求哪位大佬帮忙看一下,码风不好,字丑见谅!!!