题解 - Vijos

3

用栈模拟，模拟时记下所有未被销毁的名字集合，以及当前层的复杂度的维数。
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

WBS LV 8 @ 5 年前

#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

2351599120 LV 9 @ 7 年前

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

#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

larryzhong LV 9 @ 7 年前

记录: 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

猫粮寸断 LV 10 @ 7 年前

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

题解

5 条题解

时间复杂度

信息

状态

开发

支持

题解

5 条题解

时间复杂度

信息

状态

开发

支持

还没有账户？

登录