一个极为玄学的错误

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

mkx2023275 @ 2024-10-17 18:49:44

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

#define x first
#define y second

using namespace std;

typedef pair<int, pair<int, int>> PII;

const int N = 110;

bool st[30];
PII stk[N];

int get_num(char s[])
{
    int len = strlen(s);
    int tmp = 0;
    for (int i = 0; i < len; i ++ )
        tmp = tmp * 10 + s[i] - '0';
    return tmp;
}

int calc(int top)
{
    int t = 0;
    for (int i = 1; i <= top; i ++ )
    {
        int st = stk[i].y.x, ed = stk[i].y.y;
        if (st && ed && st > ed) return t;
        if (!st && ed) return t;
        if (st && !ed) t ++ ;
    }
    return t;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        int n;
        char s[100];
        scanf("%d%s", &n, s);
        int t = 0;
        if (s[2] == 'n' && s[3] == ')') t = 1;
        else if (s[2] == 'n')
        {
            int pos = 4;
            while (s[pos] != ')')
                t = t * 10 + s[pos] - '0', pos ++ ;
        }

        memset(st, 0, sizeof st);
        int top = 0;
        int res = 0;
        bool success = true;
        while (n -- )
        {
            char op[2];
            scanf("%s", op);
            if (*op == 'F')
            {
                char s1[5], s2[5], s3[5];
                scanf("%s%s%s", s1, s2, s3);
                if (st[s1[0] - 'a'])
                {
                    success = false;
                    break;
                }
                else
                {
                    st[s1[0] - 'a'] = true;
                    int a1 = 0, a2 = 0;
                    if (s2[0] != 'n') a1 = get_num(s2);
                    if (s3[0] != 'n') a2 = get_num(s3);
                    stk[ ++ top] = {s1[0] - 'a', {a1, a2}};
                    //cout << calc(top) << '\n';
                    res = max(res, calc(top));
                }
            }
            else
            {
                if (!top)
                {
                    success = false;
                    break;
                }
                PII t = stk[top -- ];
                st[t.x] = false;
                res = max(res, calc(top));
            }
        }
        if (top) success = false;

        if (!success) puts("ERR");
        else if (res == t) puts("Yes");
        else puts("No");
    }
    return 0;
}

总是读入错描述时间复杂度的字符串,把 O(n^11) 读成 O(n^12)


by weigui0472 @ 2024-10-31 17:28:07

printf不就好啦


by weigui0472 @ 2024-10-31 19:00:00

@weigui0472 应该是scanf


by mkx2023275 @ 2024-11-20 18:43:12

感谢


by mkx2023275 @ 2024-11-20 18:43:54

但是我用scanf了


|