萌新求助!已经被本机的getchar给搞疯了。
查看原帖
萌新求助!已经被本机的getchar给搞疯了。
33063
Focus_on楼主2020/10/17 11:10

如题

#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)O(tk),结果本机一直在getchar()上面出一些玄学错误,洛谷的评测姬又没有调试功能~~(跪求awa)~~

然后就没有然后了,如果换用字符串又会出像如下的错误:

terminate called after throwing an instance of 'std::length_error'
  what():  basic_string::_S_create

求哪位大佬帮忙看一下,码风不好,字丑见谅!!!

2020/10/17 11:10
加载中...