题目分析与解题思路

问题核心

给定 Tomato 程序的源代码（由 ifgo、jump、pass、loop、die 五种命令组成），需计算程序在任意输入序列下能生成的最大输出序列长度（即打印的行号数量）。若存在无限循环的可能，则输出 infinity。

关键约束解析

1. 命令语义与执行规则：
   • ifgo L：读入一个输入位（0/1），为1则跳转到行 L，否则执行下一行。
   • jump L：无条件跳转到行 L。
   • pass：继续下一行。
   • die：终止程序（不能在循环内使用）。
   • loop L K：循环执行从行 L 到当前行的代码块 K 次（包括首次执行）。
2. 控制流限制：
   • 跳转目标（ifgo/jump）必须在当前最内层循环体内。
   • 循环必须严格嵌套（无重叠，起始行唯一）。
   • 程序最后一行非 die 时，执行完会回到第一行（类似循环）。
3. 输出长度计算：
   • 若存在输入序列使程序进入不含 die 的无限循环，输出 infinity。
   • 否则，计算所有路径中的最大输出长度（不超过 (10^9)）。

算法设计

1. 无限循环检测（Tarjan 强连通分量算法）

目标：判断程序是否存在可无限执行的循环（不含 die）。
步骤：

1. 构建控制流图：
   • 每个命令行视为节点。
   • 根据命令类型添加边：
     • ifgo L → 两条边：下一行和跳转目标 L。
     • jump L → 一条边：跳转目标 L。
     • pass → 一条边：下一行（最后一行则指向第一行）。
     • loop L K → 两条边：循环起始行 L 和下一行。
     • die → 无后继节点。
2. 检测环：
   • 使用 Tarjan 算法 求强连通分量（SCC）。
   • 若 SCC 大小 > 1 且不含 die 命令，则为可无限循环的环。

2. 动态规划计算最大长度

目标：若无无限循环，计算最大输出长度。
状态定义：dp[i] 表示从行 i 开始执行的最大输出长度。
状态转移：

• die 命令：dp[i] = 1（终止）。
• pass 命令：dp[i] = 1 + dp[i+1]（下一行）。
• jump L 命令：dp[i] = 1 + dp[L]。
• ifgo L 命令：dp[i] = 1 + \max(dp[i+1], dp[L])（选择更长路径）。
• loop L K 命令：
  1. 计算循环体单次长度 cycle_len（从行 L 到当前行前一行）。
  2. 总长度 = 当前行 + (K-1) × cycle_len + 后续长度 dp[i+1]。

循环体长度计算：

• 递归遍历循环体内命令，累加输出长度（需处理嵌套循环）。
• 示例：loop 2 2（从行2开始循环2次），若循环体长度为5，则贡献 1 + (2-1)×5 = 6。

3. 代码实现关键点

1. 输入解析：
   • 使用自定义 str_icmp 处理命令大小写不敏感问题（如 Ifgo 与 ifgo 等价）。
   • 解析命令参数（如 loop 需读取起始行和循环次数）。
2. 环检测优化：
   • Tarjan 算法中记录每个节点的 dfs 序和 low 值。
   • 若发现 SCC 大小 > 1 且不含 die，立即返回 infinity。
3. 动态规划递归：
   • 记忆化搜索避免重复计算（pre[i] 标记已计算）。
   • 循环体长度通过 loop(i, j) 函数递归计算（从行 i 到行 j）。

代码示例

#include <iostream>
#include <cstring>
#include <cctype> // 添加 cctype 头文件
using namespace std;

// 自定义不区分大小写的字符串比较函数
inline int str_icmp(const char* s1, const char* s2) {
    while (*s1 && *s2) {
        int diff = tolower(static_cast<unsigned char>(*s1))
            - tolower(static_cast<unsigned char>(*s2));
        if (diff != 0) return diff;
        ++s1;
        ++s2;
    }
    return tolower(static_cast<unsigned char>(*s1))
        - tolower(static_cast<unsigned char>(*s2));
}

#define N 100010
struct { int c, a, b; } cmds[N]; int g[N][2], c[N], s[N], sn[N], low[N], pre[N], clk, n, p; char t[5];

bool read() {
    n = clk = p = 0;
    while (cin >> t) {
        c[++n] = 0; pre[n] = sn[n] = 0;
        // 使用自定义函数替换 _stricmp
        cmds[n].c = !str_icmp(t, "ifgo") ? 0 :
            (!str_icmp(t, "jump") ? 1 : (!str_icmp(t, "pass") ? 2 : (!str_icmp(t, "loop") ? 3 : 4)));
        if (cmds[n].c < 2) cin >> cmds[n].a;
        else if (cmds[n].c == 3) {
            cin >> cmds[n].a >> cmds[n].b;
            if (cmds[n].b == 1) cmds[n].c = 2;
        }
        while (cin.get() == ' ');
        if (cin.peek() == '\n') return true;
        if (cin.eof()) return false;
    }
    return true;
}


bool dfs(int u) {
    low[u] = pre[u] = ++clk; s[p++] = u;
    for (int i = 0, v; i < c[u]; ++i) {
        if ((v = g[u][i]) == u) return true;
        if (!pre[v]) {
            if (dfs(v)) return true;
            low[u] = min(low[u], low[v]);
        }
        else if (!sn[v]) low[u] = min(low[u], pre[v]);
    }
    if (low[u] == pre[u]) {
        int cc = 0;
        while (true) {
            ++cc; sn[s[--p]] = 1;
            if (s[p] == u) break;
        }
        return cc > 1;
    }
    return false;
}

bool cycle() {
    for (int i = 1; i <= n; ++i) if (cmds[i].c < 4) {
        g[i][c[i]++] = cmds[i].c == 1 ? cmds[i].a : (i < n ? i + 1 : 1);
        if (cmds[i].c == 0) g[i][c[i]++] = cmds[i].a;
    }
    return dfs(1);
}

int loop(int i, int j) {
    if (low[i]) return sn[i];
    if (c[i] && c[i] != j) return loop(i, c[i]) + loop(c[i] + 1, j);
    int& r = sn[i] = low[i] = 1;
    if (i == j) return c[i] ? r *= cmds[j].b : r;
    r += loop(cmds[i].c == 1 ? cmds[i].a : i + 1, j);
    if (cmds[i].c == 0) r = max(r, 1 + loop(cmds[i].a, j));
    return c[i] ? r *= cmds[j].b : r;
}

int get(int i) {
    if (cmds[i].c == 4) return 1;
    if (pre[i]) return s[i];
    pre[i] = 1; s[i] = c[i] ? loop(i, c[i]) + get(c[i] + 1) : 1 + get(cmds[i].c == 1 ? cmds[i].a : i + 1);
    if (cmds[i].c == 0) s[i] = max(s[i], 1 + get(cmds[i].a));
    return s[i];
}

void solve() {
    if (!cycle()) {
        for (int i = 1; i <= n; ++i) {
            low[i] = pre[i] = c[i] = 0;
            if (cmds[i].c == 3) c[cmds[i].a] = i;
        }
        cout << get(1) << endl;
    }
    else cout << "infinity" << endl;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    while (read()) solve();
    solve();
    return 0;
}

复杂度分析

• 时间：
  • 环检测（Tarjan）：(O(N + E))（(N) 为行数，(E) 为边数，每行最多2条边）。
  • 动态规划：(O(N))（每行状态计算最多两次）。
• 空间：(O(N))（存储图、DP状态等）。