洛谷P3952【时间复杂度】题解

发表于 更新于 分类于 Waline： 本文字数： 773 阅读时长 ≈ 3 分钟

P3952【时间复杂度】

1
2
3
4
5
4 O(n^2)
F x 1 n
F x 1 10
E
E

这道题卡了我好久😵，现在来简单复盘一下~

拿到这道题，我们首先要考虑下面几个点：

  • 需要分离出给定时间复杂度，变量名，循环的起始终止数字
  • 判断是否合法
    1. 变量名是否重复使用
    2. F、E是否对应
  • 判断给定程序的时间复杂度
    1. 循环嵌套
    2. 遇到$l\gt r$时，后面的程序无法正常进行

遇到的问题：

  1. 举个例子

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    F a 1 n
    F b 1 n
    F c 1 n
    F d 1 n
    E 
    E 
    E
    F e 1 n
    E
    E

在这里，第一行的F在最后才退出

解决方案： 使用stack<>，通过FIFO的规则，只需统计栈中符合$C至n$的个数（注意如果遇到$l\gt r$的循环，那么后面的循环不再进行统计），其最大值即为时间复杂度

  1. 注意尽管有些数据中F、E不匹配，但是我们仍然需要完整的接受数据，这里我们就需要注意数组越界问题。

完整代码奉上：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<iostream>
#include<map>
#include<stack>
using namespace std;
int T;
const int MAX=2147483647;
map<char,int> Map; 
stack<pair<char,int>> st;
int lr[105][3];//1 l，2 r
int turnum(int l,int r,string S)
{

    int pow=1,sum=0;
    for(int i=r;i>=l;i--)
    {
        sum+=(S[i]-'0')*pow;
        pow*=10;
    }
    return sum;
}
int main()
{
    cin>>T;
    for(int i=1;i<=T;i++)
    {
        int len;
        string time;
        cin>>len>>time;//输入
        getchar();

        bool time_n=false;
        int tloc=0;
        for(tloc;time[tloc]<'0'||time[tloc]>'9';tloc++)
        {
            if(time[tloc]=='n') time_n=true;
        }
        int O_time=turnum(tloc,time.length()-2,time);//拆分时间复杂度
        // cout<<O_time<<endl;


        int FE=0;
        bool judge=true,Stop=false;
        int N=-MAX,num=0;
        for(int j=1;j<=len;j++)
        {
            // cout<<j<<":\n";
            if(FE==0) num=0;
            string S="";
            getline(cin,S);
            if(judge==false) continue;
            if(S[0]=='F') 
            {
                // cout<<"*F*\n";
                FE++;
                int loc=4;//分离出l
                bool is_n=false;
                for(loc;S[loc]=='n'||(S[loc]>='0'&&S[loc]<='9');loc++)
                {
                    if(S[loc]=='n') {is_n=true;break;}
                }
                if(is_n==false)
                    lr[FE][1]=turnum(4,loc-1,S);
                else 
                {
                    lr[FE][1]=MAX;
                }
                if(is_n==true) loc++;
                int tloc=++loc;//分离出r
                is_n=false;
                for(loc;S[loc]=='n'||(S[loc]>='0'&&S[loc]<='9');loc++)
                {
                    if(S[loc]=='n') {is_n=true;break;}
                }
                if(is_n==false)
                    lr[FE][2]=turnum(tloc,loc-1,S);
                else 
                {
                    lr[FE][2]=MAX;
                }
                


                if(Map[S[2]]==1) {judge=false;}
                else 
                {
                    Map[S[2]]=1;
                    if(lr[FE][1]!=MAX&&lr[FE][2]==MAX)//小~n
                    {
                        pair<char,int> p;
                        p.first=S[2];
                        p.second=2;//n
                        st.push(p);
                        if(Stop==false) num++;
                    }
                    else if(lr[FE][1]>lr[FE][2])//大~小
                    {
                        Stop=true;
                        pair<char,int> p;
                        p.first=S[2];
                        p.second=3;
                        st.push(p);
                    }
                    else //小~大
                    {
                        pair<char,int> p;
                        p.first=S[2];
                        p.second=1;
                        st.push(p);
                    }
                }//变量名

            }
            else if(S[0]=='E') //FE匹配
            {
                FE--;
                if(FE<0) {judge=false;FE+=MAX;continue;}
                N=max(num,N);
                Map[st.top().first]=0;
                if(st.top().second==3) Stop=false;
                else if(st.top().second==2) num--;
                st.pop();
            }
            // cout<<"J:"<<j<<"FE:"<<FE<<endl;
            //  cout<<l<<" "<<r<<endl;
            
            // cout<<"Stop"<<Stop<<endl<<"num:"<<num<<endl<<"N:"<<N<<endl;
        }
        while(!st.empty()) st.pop();
        Map.clear();
        // cout<<"N:"<<N<<endl<<"FE:"<<FE<<endl;
        // cout<<N<<endl;
        // cout<<"judge:"<<judge<<endl;
        // cout<<"FE:"<<FE<<endl;
        // cout<<"n:"<<n<<endl<<time_n<<endl;
        if(FE!=0) judge=false;
        if(judge==false) {cout<<"ERR"<<endl;continue;}
        judge=true;//现在用来判断正误
        if(time_n==true)
        {
            if(O_time!=N) judge=false; 
        }
        if(N==0&&time_n==true) judge=false;
        if(judge==true) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}