求条

P3952 [NOIP2017 提高组] 时间复杂度

jJHZ @ 2025-01-04 21:18:12

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#define TLE  ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long

using namespace std;
stack<int> s;
map<char, int> mp;
int main()
{
    int T;
    TLE;
    cin >> T;
    while(T--){
        int n;
        int m = 0;
        cin >> n;
        string standard;
        cin >> standard;
        for (int i = 1; i <= n;i++){
            char kind, var, start, end;
            cin >> kind;
            int size = s.size();
            m = max(m, size);
            if(kind=='F'){
                cin >> var >> start >> end;
                if(mp[var]==1){
                    cout << "ERR" << '\n';
                    break;

                }
                else{
                    mp[var]=1;
                    s.push(var);
                }
                if(start=='n'){
                    break;
                }
                if(end=='n'){
                    m++;
                }
                if(start>end){
                    break;
                }
            }else{
                if(s.empty()){
                    cout << "ERR"<<'\n';
                    break;
                }
                mp[s.top()] = 0;
            }
        }
        if(!s.empty()){
            cout << "ERR" << '\n';
            break;
        }
        if(m==0){
            if(standard=="O(1)"){
                cout << "Yes" << '\n';
            }
            else{
                cout << "No" << '\n';
            }
        }
        else{
            string ans = "O(n^m)";
            ans[4] = (m + '0');
            if(ans==standard){
                cout << "Yes" << '\n';
            }
            else{
                cout << "No" << '\n';
            }
        }

    }
    return 0;
}

by ZJ_lzz @ 2025-01-04 21:49:12

循环的时间复杂度取决于最内层的计算次数，即嵌套最深的一层循环的计算次数。

循环的嵌套和括号序列的嵌套类似，所以我们可以借助栈来遍历整个代码序列。

当遇到FOR语句时，将该循环压入栈顶，当遇到END语句时，将栈顶的循环弹出。那么栈中从底到顶的序列就是当前循环从外到内嵌套的序列。

对于每层循环FOR i x y，我们先判断它的计算次数 cmp：

$y$ 也是 $n$，那么循环次数是 $O(1)$; $y$ 是正整数，由于 $n$ 远大于 $100$ ，且 $x,y$ 在 $100$ 以内，所以这个循环一次也不执行； $x$ 是正整数时： $y$ 是 $n$ ,那么会循环 $O(n)$ 次； $y$ 是正整数，如果 $x≤y$，那么会循环 $O(1)$ 次，如果 $x>y$，那么一次也不执行； 然后判断整个循环嵌套序列的计算次数： 如果外层循环中的某一层执行次数是 $0$ 或者当前循环的执行次数是 $0$ ，那么当前这层的计算次数就是 $0$ ； 否则当前这层的循环次数就是上一层循环的执行次数乘以前面判断出的循环次数 $cmp$； 时间复杂度分析: 总共有 $T$ 个测试数据，对于每个测试数据，每个循环会进栈一次，出栈一次，每次进栈之前会循环一遍栈中所有元素，判断是否存在变量重名的情况，所以总时间复杂度是 $O(TL^2)$。 学学万能头吧！ 代码： ```cpp #include <bits/stdc++.h> using namespace std; typedef pair <char, int> PCI; const int N=110; int tt; PCI stk[N]; // 栈中存储当前嵌套的所有循环 // first存储每一层的变量名 // second存储到当前这层总共的计算量，如果为-1，表示当前这层无法到达 int get_number(string str) // 将字符串转化成整数 { int res=0; for(auto c:str) { res=res*10+c-'0'; } return res; } int get_time(string str) // 提取出str中n的次数 { if(str=="O(1)") { return 0; } int t=str.find('^'); string num=str.substr(t+1); num.pop_back(); return get_number(num); } bool has(char c) // 判断当前栈中是否已经存在变量c { for(int i=1;i<=tt;i++) { if(stk[i].first==c) { return true; } } return false; } int get_cmp(string x, string y) // 判断 for (int i = x; i <= y; i ++) 的循环次数是n的多少次方 { if(x=="n") { if(y=="n") { return 0; } return -1; } if(y=="n") { return 1; } int a=get_number(x),b=get_number(y); if(a<= b) { return 0; } return -1; } int main() { int T; scanf("%d",&T); while(T--) { int n; string str; cin>>n>>str; int tm=get_time(str); int max_cmp=0; bool error=false; tt=0; string line; getline(cin,line); for(int i=0;i<n;i++) { getline(cin,line); if(!error) { if(line=="E") { if(tt) { tt--; } else { error=true; } } else { stringstream sin(line); string F,i,x,y; sin>>F>>i>>x>>y; if(has(i[0])) { error=true; } else { int cmp=get_cmp(x,y); if(!tt) { stk[++tt]={i[0],cmp}; } else { int computation=-1; // -1表示当前这层无法到达 if(stk[tt].second>=0&&cmp>=0) { computation=stk[tt].second+cmp; } stk[++tt]={i[0],computation}; } max_cmp = max(max_cmp, stk[tt].second); } } } } if(tt) { error=true; } if(error) { puts("ERR"); } else if(tm==max_cmp) { puts("Yes"); } else { puts("No"); } } return 0; } ```

by jJHZ @ 2025-01-04 21:51:19

@ZJ_lzz

谢谢

|