洛谷 5698:[CTSC1998] 算法复杂度

给出仅含基本操作(op)及循环语句(loopendcontinuebreak)之程序,求出所含基本操作次数之多项式。基本操作与循环次数可能取正整数或 n。

由于无条件语句,事实上 continue 相当于 end loop 0break 亦然,惟循环次数须设为 1,由此即可得解。

可惜,简单模拟我仍交了四回。其原因在 continuebreak 时保留原循环以匹配其对应 end,同时循环次数置 0 从而忽略此后语句,但若此后再有 break 时如前所述又会置 1,从而出错。修改 (1) 处,在已置 0 时不再置 1,从而通过。

#include <cstring>
#include <cstdio>
const int oxis = 51;
struct status {
    int loop;
    int coe[oxis];
} zhan[oxis];

int get_num()
{
    char now[oxis];
    int result = -1;
    scanf("%s", now);
    if (strcmp(now, "n"))
        sscanf(now, "%d", &result);
    return result == 0 ? -1 : result;    // 此处为修正数据错误
}

int main()
{
    scanf("%*s");
    int top = 0;
    zhan[0].loop = 1;
    while (true) {
        char now[oxis];
        scanf("%s", now);
        if (strcmp(now, "loop") == 0) {
            ++top;
            zhan[top].loop = get_num();
            memset(zhan[top].coe, 0, sizeof(zhan[top].coe));
        } else if (strcmp(now, "op") == 0) {
            int cishu = get_num();
            if (cishu == -1)
                ++zhan[top].coe[1];
            else
                zhan[top].coe[0] += cishu;
        } else {
            bool is_end = (strcmp(now, "end") == 0);    
            bool is_break = (strcmp(now, "break") == 0);
            if (top == 0) {
                if (is_end)
                    break;
                else
                    continue;
            }
            if (is_break && zhan[top].loop != 0)    // (1)
                zhan[top].loop = 1;
            int xin = top - 1, duo = zhan[top].loop;
            if (duo == -1)
                for (int i = 0; i < oxis - 1; ++i)
                    zhan[xin].coe[1 + i] += zhan[top].coe[i];
            else
                for (int i = 0; i < oxis; ++i)
                    zhan[xin].coe[i] += zhan[top].coe[i] * duo; 
            if (is_end)
                top = xin;
            else
                zhan[top].loop = 0;
        }
    }
    bool first = true;
    for (int i = oxis - 1; i > 1; --i) {
        int xs = zhan->coe[i];
        if (xs == 0)
            continue;
        if (!first)
            putchar('+');
        if (xs != 1)
            printf("%d", xs);
        printf("n^%d", i);
        first = false;
    }
    int xs = zhan->coe[1];
    if (xs != 0) {
        if (!first)
            putchar('+');
        if (xs != 1)
            printf("%d", xs);
        putchar('n');
        first = false;
    }
    xs = zhan->coe[0];
    if (xs != 0) {
        if (!first)
            putchar('+');
        printf("%d", xs);
    } else if (first)
        putchar('0');
    puts("");
    return 0;
}