NOIp2017 그룹 Day1T2 시간 복잡성 향상

이것은 매우 짜증나는 시뮬레이션 문제다.
코드 능력을 특별히 시험하고, 특히 잉크, 특히 메스꺼워.
문제가 메스꺼운 것이 아니라 쓰기가 메스꺼운 것이다.
문제부터 봅시다.
제목.
제목 설명 소명은 새로운 프로그래밍 언어를 배우고 있다
A++, 순환문장을 막 배운 그는 흥분해서 많은 프로그램을 썼고 자신이 계산한 시간의 복잡도를 제시했다. 그러나 그의 프로그래밍 선생님은 샤오밍을 검사하는 프로그램을 정말 원하지 않는다. 그래서 너의 기회가 왔다!다음은 샤오밍이 그의 모든 프로그램에 제시한 시간의 복잡도가 정확한지 판단하기 위해 프로그램을 작성해 주십시오.
A++ 언어의 순환 구조는 다음과 같습니다.
F i x y     ****** E
그 중
새 변수를 나타내는 F i x y
i (변수
i 삭제되지 않은 변수와 이름을 바꿀 수 없음) 및 초기화
x, 그리고 판단
i와
y의 크기 관계
i보다 작음
y는 순환에 들어간다. 그렇지 않으면 들어가지 않는다.매번 순환이 끝난 후
i는 다 수정돼요.
i+1, 일단
i 이상
y 순환을 종료합니다.
x 및
y는 양의 정수(
x 및
y의 크기 관계가 일정하지 않음) 또는 변수
n.
n은 데이터 규모를 나타내는 변수로 시간 복잡도 계산에서 이 변수를 보존해야 하며 상수로 볼 수 없다. 이 수는 100보다 훨씬 크다.
E는 루프의 끝을 나타냅니다.순환체가 끝날 때, 이 순환체가 새로 만든 변수도 삭제됩니다.
주: 본 문제에서는 쓰기가 편리하도록 복잡도를 묘사할 때 대문자 영문자를 사용한다.
"O"는 일반적인 의미에서"
Θ”라는 개념이다.
입력 출력 형식
입력 형식: 파일의 첫 번째 줄에 양의 정수를 입력합니다.
있다
t(t≤10)개 프로그램은 시간 복잡도를 계산해야 한다.프로그램마다 저희가 뽑기만 하면 돼요.
F i x y 및
E는 시간의 복잡도를 계산할 수 있다.
참고: 주기 구조는 중첩을 허용합니다.
다음 프로그램의 첫 줄에는 정수가 포함되어 있다
L과 문자열,
L은 프로그램의 행수를 나타내고 문자열은 프로그램의 복잡도를 나타낸다.
O(1)는 상수의 복잡도를 나타낸다.
복잡도
n^w
w는 100보다 작은 정수(입력에 인용부호가 포함되지 않음)로 입력의 복잡도는
O(1)와 O(n^w) 두 가지 유형.
다음
L행은 프로그램의 순환 구조에서
F i x y 또는
E.
프로그램 실행
F로 시작하여 하나의 순환에 들어가고 그 다음에 빈칸이 분리된 세 글자(직렬)를 나타낸다
ixy, i는 소문자
n), 새 변수 이름을 나타냅니다.
x 및
이 가능하다, ~할 수 있다,...
n, 정수라면 반드시 100보다 작다는 것을 알고 있다.
프로그램 실행
E로 시작하면 순환체가 끝난다는 뜻이다.
출력 형식:
출력 파일 총 t줄, 입력에 대응하는 t개 프로그램, 줄마다 출력
Yes 또는
No 또는
ERR (출력에 인용부호가 포함되지 않음) 프로그램의 실제 복잡도와 입력이 주는 복잡도가 일치하면 출력
Yes, 일치하지 않으면 내보내기
No, 프로그램에 문법 오류가 있으면 (그 중에서 문법 오류는 다음과 같습니다: ①
F와
② 새 변수와 존재하지만 삭제되지 않은 변수가 일치하지 않으면 출력
ERR.
주의: 프로그램이 실행하지 않는 순환체에서 문법 오류가 발생하더라도 컴파일 오류가 발생할 수 있습니다. 출력하려면
ERR.
출력 샘플 가져오기
샘플 입력:
8 2 O(1) F i 1 1 E 2 O(n^1) F x 1 n E 1 O(1) F x 1 n 4 O(n^2) F x 5 n F y 10 n E E 4 O(n^2) F x 9 n E F y 2 n E 4 O(n^1) F x 9 n F y n 4 E E 4 O(1) F y n 4 F x 9 n E E 4 O(n^2) F x 1 n F x 1 10 E E
출력 예제
Yes Yes ERR Yes No Yes Yes ERR
설명
입력 출력 예시 첫 번째 프로그램 설명
i는 1에서 1까지는 상수 복잡도다.
두 번째 프로그램
x에서 1까지
n 예
n의 일차적인 복잡도.
세 번째 프로그램은 하나 있어요.
F 순환이 열리지 않음
E 끝, 문법 오류.
네 번째 프로그램 이중 순환,
n의 제곱의 복잡도.
다섯 번째 프로그램은 두 개의 일중 순환,
n의 일차적인 복잡도.
여섯 번째 프로그램은 첫 번째 순환이 정상적이지만 두 번째 순환이 시작되면 종료된다.
n은 100보다 훨씬 크고 100은 4보다 크다).
일곱 번째 프로그램의 첫 번째 순환은 들어갈 수 없기 때문에 상수의 복잡도이다.
여덟 번째 프로그램 2차 순환 중의 변수 x와 1차 순환 중의 변수가 중복되어 문법 오류가 ②, 출력
ERR.
데이터 규모와 약정이 30%에 대한 데이터: 문법 오류가 존재하지 않으며 데이터는 소명이 제시한 모든 프로그램의 앞을 보장한다.
L/2 행은 반드시
F로 시작하는 문장,
L/2+1 행에서 제
L 줄은 반드시
E로 시작하는 문장,
L≤10,
x、
y는 정수입니다.
x는 반드시 보다 작다
y, 그리고 오직
이 가능하다, ~할 수 있다,...
n.
50%의 데이터: 문법 오류가 없음,
L≤100 및
x、
y는 정수입니다.
x는 반드시 보다 작다
y, 그리고 오직
이 가능하다, ~할 수 있다,...
n.
데이터 70%: 구문 오류 없음,
L≤100.
100% 데이터의 경우:
L≤100.
분석하다.
누드 시뮬레이션.
모두 세 걸음으로 나눌 수 있다.
일단 읽어. 이건 틀림없어.
읽으면서 판단해서 나는 이 문제를 경기장에서 한 점도 얻지 못했다.
문법 오류를 먼저 판단하고, 직접적으로
ERR 간다.
.
그리고 계산의 복잡도, 부합
Yes, 맞지 않음
No.
나머지는 디버깅이다.
부호를 붙이다
이거 하루 걸렸네.
(변함없는 유니크한 사이즈)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define N 110

using namespace std;

int n;
int m;
int i=1;
int ans=0;
int flag=1;
int bz[N+N];
char s[N];

int get()
{
    char c;
	
	c=getchar();
    
	int x;
	
	x=0;
	
    if(c=='n') 
    {
        getchar();
        
        return -1;
    }
    for(;c>='0'&&c<='9';c=getchar())
		x=x*10+c-48;
		
    return x;
}
void dg(int x)
{
    int aans;
	int hy;
	
	hy=ans;
	aans=ans;
	
    while(i<=n)
    {
        i++;
        
        char c;
		
		c=getchar();
		
        if(c=='E')
        {
            scanf("
");
            
            ans=aans;
            
            return;
        }
        
        scanf(" %c ",&c);
        
        if(bz[c]==1)
			flag=0;
			
        bz[c]=1;
        
        int q;
		int w;
		
		q=get();
		w=get();
		
        if(q==-1&&w==-1)
            dg(x+1);
            
        if(q==-1&&w>0)
        {
            int jy=ans;
            
			dg(x+1);
			
            ans=jy;
        }
        
        if(q>0&&w==-1)
        {
            ans++;
            
			dg(x+1);
        }
        
        if(q>0&&w>0)
        {
            int jy=-1;
            
            if(q>w)
				jy=ans;
				
			dg(x+1);
			
            if(jy!=-1)
				ans=jy;
        }
        
        bz[c]=0;
        
        aans=max(ans,aans);
        
        ans=hy;
    }
    ans=aans;
    
    if(i>n&&x!=0)
		flag=0;
}
int main()
{
    int ac;
    
	scanf("%d
",&ac);
	
    for(;ac;ac--)
    {
        memset(bz,0,sizeof(bz));
        
        i=1;
        
		flag=1;
		
		ans=0;
		
        char c;
        
		scanf("%d O(%c",&n,&c);
		
        if(c=='n')
            scanf("^%d",&m);
        else
			m=0;
			
        scanf(")
");
        
        dg(0);
        
        if(i<=n) 
        {
            flag=0;
            
            while(i<=n)
            {
                char c;
				
				c=getchar();
				
                if(c=='E')
                    scanf("
");
                else
                {
                    scanf(" %c ",&c);
                    int q;
					q=get();
					q=get();
                }
                
                i++;
            }
        }
        if(flag==0)
			printf("ERR");
        else
        {
            if(ans==m)
				printf("Yes");
            else
				printf("No");
        }
        
        printf("
");
    }
    return 0;
}

PS
1. 입력 흐름 함수 포맷"
scanf "는 지정한 내용을 읽을 수 있습니다. 제 코드에는 이 점이 많이 적용됩니다.
2. 잘 못 쓰다
추천
cin, 너무 간단해.
3. 내가 쓰는 귀환, 물론 여러 가지 방법은 귀환이 너무 추상적이기 때문이야. 하하하.