题解

5 条题解

  • 3
    @ 2018-02-13 23:29:22

    用栈模拟,模拟时记下所有未被销毁的名字集合,以及当前层的复杂度的维数。
    F i x y中,
    若x=c1,y=c2,c1<=c2,维数为0
    若x=c1,y=c2,c1>c2,维数为-inf(循环不执行)
    若x=c1,y=n,维数为1
    若x=n,y=c2,维数为-inf(循环不执行)
    若x=y=n,维数为0

    作者:NiroBC大姐姐
    链接:https://www.zhihu.com/question/67960571/answer/258225928
    来源:知乎

    #include <bits/stdc++.h>
    using namespace std;
    
    const int inf=128;
    int T,L,w,i,d;
    char O[128],I[128][64],n[32],x[32],y[32];
    bool f[256]; //mark for used variable
    stack< pair<char,int> > S;
    
    int main() {
        scanf("%d",&T);
        while (T--) {
            int D=0,ans=0;  
            scanf("%d%s\n",&L,O); //do not omit '\n'
            w=atoi(O+4);  //O(n^w)
            for (i=0;i<L;i++) gets(I[i]);   
            for (i=0;i<L;i++) {
                if (I[i][0]=='F') {
                    sscanf(I[i],"%*s%s%s%s",n,x,y); //n=variable name,
                    if (f[n[0]]++) break; //err: used variable
                    switch ((x[0]!='n')<<1|(y[0]!='n')) {
                        case 0: d=0;    break; //n to n
                        case 1: d=-inf; break; //n to y
                        case 2: d=1;    break; //x to n
                        case 3: d=atoi(x)<=atoi(y)?0:-inf; //x to y
                    }
                    S.push({n[0],d});
                    ans=max(ans,D+=d);
                } else {
                    if (S.empty()) break; //err: too much E
                    f[S.top().first]=0;
                    D-=S.top().second;
                    S.pop();
                }
            }
            puts(i!=L||!S.empty()?"ERR":ans==w?"Yes":"No");
            while (!S.empty()) f[S.top().first]=0, S.pop(); 
        }
    }
    
  • 1
    @ 2019-11-11 21:59:49

    #include <bits/stdc++.h>
    #define in inline
    #define re register
    #define N 1005
    using namespace std;
    int pos=0,cnt=0,tot=0,num=0,T,L,ans,st[N];
    /* pos表示如果在某处的循环是不执行的 那么 它的嵌套也是无效的
    cnt记录复杂度,只负责记录n^ 的复杂度 表示当前的时间复杂度
    tot表示给出的整个程序中的最大复杂度 即程序的复杂度
    num当前是第几个循环
    ans是题目给出的复杂度
    st数组 模拟栈 后进先出
    /
    string s;
    char tar[N];
    bool bz=false,vis[N];
    /

    bz表示是否出现语法错误
    vis表示用过的变量名 用于判断是否出现语法错误
    */

    in int read()
    {
    int x=0;
    char ch=getchar();
    while (ch>'9' || ch<'0') ch=getchar();
    while (ch>='0' && ch<='9')
    x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x;
    }

    int main()
    {
    T=read();
    while (T--)
    {
    memset(vis,false,sizeof(vis));
    L=read(),cin>>s,ans=0;
    bz=false,pos=0,cnt=0,num=0,tot=0;
    if (s=="O(1)") ans=-1;
    else
    for (re int i=4; i<s.size()-1; ++i)
    ans=ans*10+s[i]-'0';
    for (re int i=1; i<=L; ++i)
    {
    char ch;
    cin>>ch;
    string a,b,c;
    re int x=0,y=0;
    if (ch=='F') //如果为'F' 即表示进入循环
    {
    if (num==0)
    //如果 num=0 表示之前的所有清空 除了 变量名重复的语法错误外
    memset(vis,false,sizeof(vis)),tot=max(cnt,tot),cnt=0,pos=0;
    ++num; // 循环次数+1
    st[num]=0; //先标记为0 即为常数复杂度
    cin>>a>>b>>c;
    tar[num]=a[0]; //tar记录之前用过的变量 也是模拟栈实现
    if (vis[a[0]-'a']) bz=true; //如果变量名重复 即为语法错误
    vis[a[0]-'a']=true; //标记为用过的变量
    if (b[0]=='n') x=100;
    else for (re int j=0; j<b.size(); ++j)
    x=x*10+b[j]-'0'; //对于b的提取
    if (c[0]=='n') y=100;
    else for (re int j=0; j<c.size(); ++j)
    y=y*10+c[j]-'0'; //对于c的提取
    if (x>y) ++pos,st[num]=-1; //表示不执行的循环 当前st标记为-1
    if (pos) continue;
    //如果前面存在不执行的循环仍未清空 即后面的循环的复杂度没有贡献
    if (y==100 && x!=100) ++cnt,st[num]=1;
    //为n的复杂度 且 起点不为 n 当前st的值标记为1
    tot=max(tot,cnt);
    //记录最大的复杂度 即程序的复杂度
    }
    else
    {
    vis[tar[num]-'a']=false; //循环结束 上次的变量名清空
    if (st[num]==1) --cnt; //如果上次循环有贡献 则cnt需要-1
    if (st[num]==-1) --pos; //如果上次是不执行的 则pos需要-1
    --num; //当前执行少了 一个循环
    }

    }
    if (num!=0 || bz==true) printf("ERR\n");
    //如果末尾字符不够 或者变量重名 即为语法错误
    else if ( (ans==-1 && tot==0) || (ans==tot) ) printf("Yes\n");
    else printf("No\n");
    //如果为常数复杂度 或者n^复杂度相同 即为yes 否则为no
    }
    return 0;
    }

  • 0
    @ 2017-12-07 20:44:50

    代码短小精悍,易于理解
    利用了快读的思想

    #include<bits/stdc++.h>
    using namespace std;
    bool use[256];
    stack<char>q;stack<bool>p;
    inline int getnum(){
        char ch=getchar();
        int x=0;
        while((ch<'0'||ch>'9')&&ch!='n') ch=getchar();
        if(ch=='n') return 100;
        while(ch>='0'&&ch<='9') x=x*10-48+ch,ch=getchar();
        return x;
    }
    inline char get(){
        char ch=getchar();
        while(ch==' '||ch=='\n') ch=getchar();
        return ch;
    }
    inline int getn(){
        if(getnum()==100) return 1;
        return 0;
    }
    int main(){
        int t=getnum();
        while(t--){
            memset(use,0,sizeof(use));
            int n=getnum(),f=getn(),err=0,s=0,bre=0,ans=0;
            if(f) f=getnum();
            while(n--)
                if(get()=='F'){
                    int ch=get();
                    q.push(ch);
                    if(use[ch]) err=1;
                    use[ch]=1;
                    int l=getnum(),r=getnum();
                    if(l>r) bre++;
                    else if(bre) bre++;
                    if(l<=r&&r==100&&l!=100&&!bre){
                        s++,p.push(1);
                        ans=max(s,ans);
                    }
                    else p.push(0);
                }
                else{
                    if(!p.empty()&&p.top()) s--;
                    if(!p.empty()) p.pop();
                    if(bre) bre--;
                    if(!q.empty()) use[q.top()]=0,q.pop();
                    else err=1;
                }
            while(!q.empty()) err=1,q.pop(),p.pop();
            if(err) printf("ERR\n");
            else if(ans==f) printf("Yes\n");
            else printf("No\n");
        }
        return 0;
    }
    
  • 0
    @ 2017-11-12 17:49:52

    记录: Accepted.
    用栈模拟即可.

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        ios::sync_with_stdio(false);
        int T;
        cin >> T;
        while (T--) {
            bool error = false;
            int len, tmp = 0, _max = 0;
            string str;
            cin >> len >> str;
            if (str != "O(1)") {
                int pos = 4;
                while (isdigit(str[pos])) {
                    tmp = tmp * 10 + str[pos++] - '0';
                }
            }
            map<string, bool> used;
            stack<pair<string, int> > st;
            while (len--) {
                char op;
                cin >> op;
                if (op == 'E') {
                    if (st.empty()) {
                        error = true;
                    } else {
                        used[st.top().first] = false;
                        _max = max(_max, st.top().second);
                        st.pop();
                    }
                } else {
                    string var, str1, str2;
                    cin >> var >> str1 >> str2;
                    if (used[var]) {
                        error = true;
                    }
                    used[var] = true;
                    int x = 0, y = 0, cur;
                    if (str1 != "n") {
                        for (int i = 0; i < str1.length(); i++) {
                            x = x * 10 + str1[i] - '0';
                        }
                    }
                    if (str2 != "n") {
                        for (int i = 0; i < str2.length(); i++) {
                            y = y * 10 + str2[i] - '0';
                        }
                    }
                    if (str1 == "n" && str2 == "n") {
                        cur = 0;
                    } else if (str1 == "n") {
                        cur = -1;
                    } else if (str2 == "n") {
                        cur = 1;
                    } else {
                        if (x <= y) {
                            cur = 0;
                        } else {
                            cur = -1;
                        }
                    }
                    if (cur == -1) {
                        st.push(make_pair(var, -1));
                    } else if (!st.empty()) {
                        if (st.top().second == -1) {
                            st.push(make_pair(var, -1));
                        } else {
                            st.push(make_pair(var, cur + st.top().second));
                        }
                    } else {
                        st.push(make_pair(var, cur));
                    }
                }
            }
            if (error) {
                cout << "ERR" << endl;
            } else if (tmp == _max) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }
        return 0;
    }
    
  • -8
    @ 2017-12-18 15:19:48

    完全不想说什么。。。
    此题水的一匹,考场上却调了近一个半小时
    然后因为Yes和No的大小写搞错完美零分
    给大家当一个教训吧。。。

  • 1

信息

ID
2029
难度
5
分类
(无)
标签
递交数
786
已通过
174
通过率
22%
被复制
8
上传者