UVa 12804 The Necronomicon of Computing-平芜编程栈

题目描述

给定一个黑暗程序，它包含三类指令：

A：算术 / 赋值指令，执行后总是进入下一条指令。
J N：无条件跳转指令，执行后总是跳转到第NNN条指令。
C N：条件跳转指令，执行后可能跳转到第NNN条指令，也可能继续执行下一条指令，具体选择不可预测。

指令从111开始顺序编号。程序从第111条指令开始执行，当执行到超过最后一条指令（即虚拟位置L+1L + 1L+1）时终止。

需要判断该程序在所有可能执行路径下的终止行为：

若所有执行路径都最终终止，输出ALWAYS。
若所有执行路径都永不终止（即不存在任何路径能到达终止状态），输出NEVER。
若存在终止的路径也存在不终止的路径，输出SOMETIMES。

输入格式

第一行一个整数TTT，表示测试用例数。
每个测试用例第一行一个整数LLL（1≤L≤10001 \le L \le 10001≤L≤1000），表示指令条数。
接下来LLL行，每行表示一条指令：

A
J N（1≤N≤L1 \le N \le L1≤N≤L）
C N（1≤N≤L1 \le N \le L1≤N≤L）

输出格式

对于每个测试用例，输出一行：

ALWAYS
NEVER
SOMETIMES

样例

输入

3 3 A A J 1 5 A J 4 J 5 C 3 A 3 A A C 2 A

输出

NEVER ALWAYS SOMETIMES

（样例中第一个测试用例三条指令为A、A、J 1，会无限循环；第二个用例所有路径最终终止；第三个用例条件跳转导致不确定性。）

题目分析

将程序视为一个有向图，指令编号1…L1 \dots L1…L是节点，再添加一个虚拟节点L+1L + 1L+1表示“终止”。每条指令对应一条或多条有向边：

A：唯一出边指向i+1i + 1i+1。
J N：唯一出边指向NNN。
C N：两条出边分别指向NNN和i+1i + 1i+1。

执行过程就是从节点111出发，沿着图中的有向边前进，最终可能到达L+1L + 1L+1，也可能陷入无限循环。

由于C指令的非确定性，程序的所有可能执行对应于从111出发的所有有向路径。我们需要判断这些路径的终止性质：

所有路径都终止：等价于节点111是“好”节点，定义为从该节点出发的所有路径最终都能到达L+1L + 1L+1。
不存在任何终止路径：等价于从111出发无法到达L+1L + 1L+1。
其他情况：既有终止路径又有无限路径。

因此，核心在于：

计算哪些节点是“必然终止”的（好节点）。
判断从111出发能否到达L+1L + 1L+1。

必然终止节点的判定

令good[u]\textit{good}[u]good[u]表示从节点uuu出发的所有路径都终止。显然，good[L+1]=true\textit{good}[L + 1] = \text{true}good[L+1]=true。对于其他节点uuu：

若uuu的出度为111（即A或J），则good[u]=good[v]\textit{good}[u] = \textit{good}[v]good[u]=good[v]，其中vvv是唯一后继。
若uuu的出度为222（即C），则good[u]=good[v1]∧good[v2]\textit{good}[u] = \textit{good}[v_1] \land \textit{good}[v_2]good[u]=good[v1]∧good[v2]，即两个后继都必须是好节点。

我们可以反向拓扑求解：初始已知good[L+1]\textit{good}[L + 1]good[L+1]为真。对于每个节点uuu，记录其尚未确定为真的后继数量（即出度）。当某个后继被确定为真时，该计数减一。当计数减为零时，说明uuu的所有后继都是好节点，则uuu也是好节点，入队。如此迭代，最终得到所有好节点。

可达性

从节点111出发进行DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS遍历，若能到达L+1L + 1L+1，则存在终止路径，否则不存在。

分类逻辑

如果good[1]\textit{good}[1]good[1]为真，则所有路径终止 →ALWAYS。
否则，如果L+1L + 1L+1不可达，则不存在任何终止路径 →NEVER。
否则，存在终止路径，但并非所有路径终止（因为good[1]\textit{good}[1]good[1]为假）→SOMETIMES。

解题思路

读入指令，构建有向图，记录出边和入边（前驱），同时记录每个节点的出度。
初始化good\textit{good}good数组为false，cnt[u]=outDeg[u]\textit{cnt}[u] = \text{outDeg}[u]cnt[u]=outDeg[u]。
将虚拟节点L+1L + 1L+1标记为好节点，入队。
执行反向拓扑：
- 取出队首节点vvv，遍历其所有前驱uuu。
- 对于每个前驱uuu，若uuu尚未被标记为好节点，则cnt[u]−−\textit{cnt}[u]--cnt[u]−−。
- 如果cnt[u]\textit{cnt}[u]cnt[u]变为000，则uuu是好节点，入队。
最终判断good[1]\textit{good}[1]good[1]。
若good[1]\textit{good}[1]good[1]为假，则从节点111进行DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS检查是否可到达L+1L + 1L+1。
根据结果输出相应字符串。

该算法的时间复杂度为O(L)O(L)O(L)（每个节点和边访问常数次），空间复杂度为O(L)O(L)O(L)，满足L≤1000L \le 1000L≤1000的限制。

代码实现

// The Necronomicon of Computing// UVa ID: 12804// Verdict: Accepted// Submission Date: 2026-07-12// UVa Run Time: 0.020s//// 版权所有（C）2026，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cin>>T;while(T--){intL;cin>>L;inttotalNodes=L+1;// 节点 1..L，L+1 为终止状态vector<vector<int>>adj(totalNodes+1);// 出边vector<vector<int>>pred(totalNodes+1);// 入边（前驱）vector<int>outDeg(totalNodes+1,0);// 出度for(inti=1;i<=L;++i){string op;cin>>op;if(op=="A"){intnxt=i+1;adj[i].push_back(nxt);pred[nxt].push_back(i);outDeg[i]=1;}elseif(op=="J"){intN;cin>>N;adj[i].push_back(N);pred[N].push_back(i);outDeg[i]=1;}else{// "C"intN;cin>>N;intnxt1=N;intnxt2=i+1;adj[i].push_back(nxt1);pred[nxt1].push_back(i);adj[i].push_back(nxt2);pred[nxt2].push_back(i);outDeg[i]=2;}}// 计算所有“必然终止”的节点（good）vector<bool>good(totalNodes+1,false);vector<int>cnt=outDeg;// 剩余未确定为 good 的后继数量queue<int>q;good[L+1]=true;q.push(L+1);while(!q.empty()){intv=q.front();q.pop();for(intu:pred[v]){if(!good[u]){--cnt[u];if(cnt[u]==0){good[u]=true;q.push(u);}}}}if(good[1])cout<<"ALWAYS\n";else{// 检查是否存在路径到达 L+1（可达性）vector<bool>visited(totalNodes+1,false);stack<int>st;st.push(1);visited[1]=true;boolreachable=false;while(!st.empty()){intu=st.top();st.pop();if(u==L+1){reachable=true;break;}for(intnxt:adj[u]){if(!visited[nxt]){visited[nxt]=true;st.push(nxt);}}}if(!reachable)cout<<"NEVER\n";elsecout<<"SOMETIMES\n";}}return0;}