求调 调成100 给5 rmb 不能面向数据编程

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

Bruce20130509 @ 2024-08-19 20:39:11

求调 洛谷82pts

include <iostream>

include <cstring>

include <algorithm>

include <unordered_map>

using namespace std; const int N = 110; int top;

int T, n; string s; string stk[N]; unordered_map <string, int> mp; int get (string a, string b) { if (b == "n") return 1; return 0; } int main() { cin >> T; while (T -- ) {

    mp.clear ();
    top = 0;
    cin >> n >> s;
    getchar ();
    int t = 0;
    int cnt = 0;
    bool f = 0;
    int flag = -1;
    int last = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if (top == 0) cnt = 0;
        t = max (t, cnt);
        char op;
        cin >> op;
        if (op == 'F')
        {
            string a, b, c;
            cin >> a >> b >> c;
            if (mp[a]) f = 1;
            mp[a] = 1;
            stk[ ++ top] = a;
            if (b == "n" || b != "n" && c != "n"  && stoi (b) > stoi (c) && flag == -1) flag = top, last = i;
            if (top < flag && flag != -1 || flag == -1) cnt += get (b, c);
            if (top == flag && i != last) flag = -1, last = 0;
        }

        else
        {

            if (!top) f = 1;
            string t = stk[top -- ];
            mp[t] = 0;
            cnt -- ;
        }
        t = max (t, cnt);
    }
    t = max (t, cnt);
    if (top || f == 1) cout << "ERR\n";
    else
    {
        string ans = "";
        if (t == 0)
        {
            ans = "O(1)";
        }
        else
        {
            ans = "O(n^" + to_string(t) + ")";
        }
        if (ans == s) cout << "Yes\n";
        else cout << "No\n";
    }
}

}

by Milky_Cat @ 2024-08-19 20:40:14

艹

有 bug

by donnieguo @ 2024-08-19 20:47:18

@Bruce20130509 cin 改成 getline

by Finner_forgeter @ 2024-08-19 20:49:38

@Bruce20130509 富二代wq

by Bruce20130509 @ 2024-08-20 11:47:41

@donnieguo 咋改 给行代码行吗， 球球了

by donnieguo @ 2024-08-20 11:56:52

@Bruce20130509 你markdown炸了，而且我也只是看了一下题目，那题一行字符串之间有空格

by cat_lover1 @ 2024-08-20 21:21:42

过了。注意可能没有输入语句就 E。这时候栈为空，访问会 RE。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>

using namespace std;
const int N = 500010;

struct node
{
    string a, b;
};
int top;

int T, n;
string s;
char stk[N];
node stk2[N];
unordered_map <char, int> mp;
int stoi1 (string str3)
{
    int sum = 0;
    for (int i = 0; i < str3.size (); i ++ )
    {
        sum = sum * 10 + str3[i] - '0';
    }
    return sum;
}
bool is_num (string a)
{
    if (a == "n") return 0;
    else return 1;
}
int get (string a, string b)
{
    if (is_num (a) && !is_num (b)) return 1;
    return 0;
}

bool cmp (string a, string b)//a>b return 1
{
    if (is_num (a) && is_num (b)) return stoi1 (a) > stoi1(b);
    if (is_num (a) && !is_num (b)) return 0;
    if (!is_num (a) && is_num (b)) return 1;    
    if (!is_num (a) && !is_num (b)) return 0;
}

int main()
{
    cin >> T;
    while (T -- )
    {

        mp.clear ();
        top = 0;
        cin >> n >> s;
        getchar ();
        int t = 0, cnt = 0, n_1 = 0;
        bool f = 0;
        for (int i = 1; i <= n; i ++ )
        {
            if (top == 0) cnt = 0;
            t = max (t, cnt);
            char op[2];
            cin >> op;
            if (*op == 'F')
            {
                char a;
                string b, c;
                cin >> a >> b >> c;
                if (mp[a]) f = 1;
                mp[a] = 1;
                stk[ ++ top] = a;
                stk2[top] = {b, c};

                if (cmp (b, c)) n_1 ++ ;
                if (!n_1) cnt += get (b, c);
            }

            else
            {
                if (!top){ f = 1; continue; }
                char tmp = stk[top -- ];
                node tmp2 = stk2[top + 1];
                mp[tmp] = 0;
                if (n_1 == 0) cnt -- ;
                if (cmp (tmp2.a, tmp2.b)) n_1 -- ;

            }
            t = max (t, cnt);

        }
        t = max (t, cnt);
        if (top || f == 1) cout << "ERR\n";
        else
        {
            string ans = "";
            if (t == 0)
            {
                ans = "O(1)";
            }
            else
            {
                ans = "O(n^" + to_string(t) + ")";
            }
            if (ans == s) cout << "Yes\n";
            else cout << "No\n";
        }
    }
}

by cat_lover1 @ 2024-08-20 21:22:31

@Bruce20130509

|