Znzryb's Blog

\section{错误六：答案计算缺少 $+\infty$ 守卫}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
ll lans = INF;
for (int num1 = 0; num1 < 2; ++num1) {
    if (d[num1][1] == INF) continue;
    ll val = d[num1][1] + 1;
    lans = min(lans, val);
}
// 缺少：if (lans == INF) continue;
ans += lans % mod * dp[status] % mod;
ans %= mod;
\end{minted}

\subsection*{错误分析}
当某个自动机状态 $D$ 的 $d_{01}$ 和 $d_{11}$ 均为 $+\infty$ 时，意味着落在该状态的子序列无法完成合法划分，其 $f$ 值为 $0$，不应对答案有任何贡献。

但如果缺少 \texttt{if (lans == INF) continue;}，\texttt{lans} 仍为初始值 \texttt{INF}（$= 2^{61} - 1$），这个巨大的数值会被乘以 \texttt{dp[status]} 后加入答案，导致结果完全错误。

\subsection*{修复}
\begin{minted}{cpp}
if (lans == INF) continue;   // f=0 的状态不贡献答案
\end{minted}

\subsection*{教训}
使用哨兵值（如 \texttt{INF}）初始化 \texttt{min} 变量时，计算结束后必须检查结果是否仍为哨兵值。如果是，说明没有任何有效候选，必须跳过后续计算，否则哨兵值会作为"正常数值"参与运算。

\section{错误七（TLE）：循环内 \texttt{vector} 拷贝构造导致 $10^7$ 次堆分配}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
for (int i = 0; i < N; ++i) {
    ll ch = s[i] - '0';
    vector<ll> ndp = dp;   // 拷贝构造：每次都 new 一块内存
    for (int status = 0; status <= 45; ++status) {
        // ...
    }
    swap(ndp, dp);
}   // ndp 析构：每次都 delete 一块内存
\end{minted}

\subsection*{错误分析}
\texttt{vector<ll> ndp = dp;} 是拷贝构造，每次调用都会在堆上分配 $50 \times 8 = 400$ 字节的新内存，循环结束时 \texttt{ndp} 析构又将其释放。$N$ 最大为 $10^7$，因此总共触发 $10^7$ 次 \texttt{malloc} + $10^7$ 次 \texttt{free}，系统调用开销远超 DP 本身的计算量。

\subsection*{修复}
将 \texttt{ndp} 的声明提到循环外部，循环内用赋值代替构造：

\begin{minted}{cpp}
vector<ll> ndp;              // 提到循环外
for (int i = 0; i < N; ++i) {
    ll ch = s[i] - '0';
    ndp = dp;                // 赋值：size 相同时不会重新分配内存
    for (int status = 0; status <= 45; ++status) {
        // ...
    }
    dp.swap(ndp);            // O(1)，只交换内部指针
}
\end{minted}

\section{错误三：BFS 建自动机时 \texttt{nxt} 表不完整}
%======================================================================

\subsection*{错误代码}
\begin{minted}{cpp}
for (int i = 0; i < 2; ++i) {
    auto v = u.next_state(i);
    if (mp.contains(v)) {
        continue;   // 错误：跳过了，但没有记录转移边
    }
    mp[v] = idx;
    nxt[mp[u]][i] = idx;
    ++idx;
    q.push(v);
}
\end{minted}

\subsection*{错误分析}
当目标状态 \texttt{v} 已经在 BFS 中被访问过时，代码直接 \texttt{continue}，\textbf{没有设置 \texttt{nxt[mp[u]][i] = mp[v]}}。这导致所有"转移到已访问状态"的边全部留为初始值 $-1$。

自动机共 $40$ 个状态、$80$ 条有向边，但其中只有 $39$ 条（BFS 树边）被正确记录，剩下 $41$ 条（回边和交叉边）全部丢失。后续的子序列 DP 在遇到这些 $-1$ 的转移时会直接跳过，导致大量合法的子序列转移被忽略。

\subsection*{修复}
\begin{minted}{cpp}
 for (int i = 0; i < 2; ++i) {
    auto v = u.next_state(i);
    if (mp.contains(v)) {
        nxt[mp[u]][i] = mp[v];
        continue;
    }
    mp[v] = idx;
    idx_state[idx] = v;
    nxt[mp[u]][i] = idx;
    ++idx;
    q.push(v);
}
\end{minted}

\subsection*{教训}
BFS 建图时，"发现新节点"和"记录边"是两个独立的操作。即使目标节点已经在队列中，从当前节点到它的\textbf{转移边}仍然必须被记录。这是 BFS 建自动机的经典易错点。