欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

洛谷P3952 时间复杂度

程序员文章站 2024-03-19 09:25:40
...

非常繁琐,细节巨多。
1.尤其注意两个n出现时按常数算。
2.读入数字时要读整个字符串,而不是单个字符

#include<cstring>
#include<algorithm>
#include<stack>
#include<cstdio>
#include<iostream>
using namespace std;
const int inf = 100000 + 3;
int check[200];
inline int get(char a){  return (int)a; }
inline int exchange(char h[])
{
    if(h[0] == 'n')return inf;
    else 
    {
        int num = 0, cnt = 0;
        while(h[cnt] >= '0' && h[cnt] <= '9')
        {
            num = num * 10 + h[cnt] - '0';
            ++cnt;
        }
        return num;
    }
}
struct Node
{
    int skip, comp, idx;        
    Node(int skip = 0,int comp = 0,int idx = 0):skip(skip), comp(comp), idx(idx){}
};
stack<Node>S;
int main()
{
    //freopen("f.txt","r",stdin);
    int T;
    scanf("%d",&T);
    char h[10];
    char s[20];
    while(T--)
    {
        while(!S.empty()) S.pop();
        memset(check,0,sizeof(check));
        int n;
        int  flag = 1, ans = 0;
        scanf("%d",&n);
        scanf("%s",s);
        for(int i = 1;i <= n;++i)
        {
            scanf("%s",h);
            if(h[0] == 'E')
            {
                if(S.empty()) {flag = 0;}
                else 
                {
                    Node u = S.top();
                    check[u.idx] = 0;
                    ans = max(ans,u.comp);
                    S.pop();
                }
                continue;
            }
            Node new_node;
            scanf("%s",h);
            int id = get(h[0]), num1, num2, cm = 0;
            if(check[id]) {flag = 0;}
            check[id] = 1;
            scanf("%s",h);  num1 = exchange(h);
            scanf("%s",h);  num2 = exchange(h);
            cm = (!S.empty()) ? S.top().comp : 0;
         //  printf("%d %d\n",num1,num2);
            if(num1 > num2) S.push(Node(1,0,id));
            else 
            {
                if(!S.empty() && S.top().skip == 1)S.push(Node(1,0,id));
                else
                {
                    if(num2 == inf && num1 != inf) ++cm;
                    ans = max(ans,cm);
                    S.push(Node(0,cm,id));
                } 
            }
        }
        if(flag == 0 || !S.empty()) printf("ERR\n");
        else
        {
            if(s[2] - '0' == 1)
            {
                if(ans == 0) printf("Yes\n");
                else printf("No\n");
            } 
            else
            {
                int num = 0, cnt = 4;
                while(s[cnt] >= '0' && s[cnt] <= '9')
                {
                    num = num * 10 + s[cnt] - '0';
                    ++cnt;
                }
                if(num == ans) printf("Yes\n");
                else printf("No\n");
            }
        }
    }
    return 0;
}