题目描述给定一个黑暗程序它包含三类指令A算术 / 赋值指令执行后总是进入下一条指令。J N无条件跳转指令执行后总是跳转到第NNN条指令。C N条件跳转指令执行后可能跳转到第NNN条指令也可能继续执行下一条指令具体选择不可预测。指令从111开始顺序编号。程序从第111条指令开始执行当执行到超过最后一条指令即虚拟位置L1L 1L1时终止。需要判断该程序在所有可能执行路径下的终止行为若所有执行路径都最终终止输出ALWAYS。若所有执行路径都永不终止即不存在任何路径能到达终止状态输出NEVER。若存在终止的路径也存在不终止的路径输出SOMETIMES。输入格式第一行一个整数TTT表示测试用例数。每个测试用例第一行一个整数LLL1≤L≤10001 \le L \le 10001≤L≤1000表示指令条数。接下来LLL行每行表示一条指令AJ N1≤N≤L1 \le N \le L1≤N≤LC N1≤N≤L1 \le N \le L1≤N≤L输出格式对于每个测试用例输出一行ALWAYSNEVERSOMETIMES样例输入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是节点再添加一个虚拟节点L1L 1L1表示“终止”。每条指令对应一条或多条有向边A唯一出边指向i1i 1i1。J N唯一出边指向NNN。C N两条出边分别指向NNN和i1i 1i1。执行过程就是从节点111出发沿着图中的有向边前进最终可能到达L1L 1L1也可能陷入无限循环。由于C指令的非确定性程序的所有可能执行对应于从111出发的所有有向路径。我们需要判断这些路径的终止性质所有路径都终止等价于节点111是“好”节点定义为从该节点出发的所有路径最终都能到达L1L 1L1。不存在任何终止路径等价于从111出发无法到达L1L 1L1。其他情况既有终止路径又有无限路径。因此核心在于计算哪些节点是“必然终止”的好节点。判断从111出发能否到达L1L 1L1。必然终止节点的判定令good[u]\textit{good}[u]good[u]表示从节点uuu出发的所有路径都终止。显然good[L1]true\textit{good}[L 1] \text{true}good[L1]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[L1]\textit{good}[L 1]good[L1]为真。对于每个节点uuu记录其尚未确定为真的后继数量即出度。当某个后继被确定为真时该计数减一。当计数减为零时说明uuu的所有后继都是好节点则uuu也是好节点入队。如此迭代最终得到所有好节点。可达性从节点111出发进行DFS\texttt{DFS}DFS或BFS\texttt{BFS}BFS遍历若能到达L1L 1L1则存在终止路径否则不存在。分类逻辑如果good[1]\textit{good}[1]good[1]为真则所有路径终止 →ALWAYS。否则如果L1L 1L1不可达则不存在任何终止路径 →NEVER。否则存在终止路径但并非所有路径终止因为good[1]\textit{good}[1]good[1]为假→SOMETIMES。解题思路读入指令构建有向图记录出边和入边前驱同时记录每个节点的出度。初始化good\textit{good}good数组为falsecnt[u]outDeg[u]\textit{cnt}[u] \text{outDeg}[u]cnt[u]outDeg[u]。将虚拟节点L1L 1L1标记为好节点入队。执行反向拓扑取出队首节点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检查是否可到达L1L 1L1。根据结果输出相应字符串。该算法的时间复杂度为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//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intT;cinT;while(T--){intL;cinL;inttotalNodesL1;// 节点 1..LL1 为终止状态vectorvectorintadj(totalNodes1);// 出边vectorvectorintpred(totalNodes1);// 入边前驱vectorintoutDeg(totalNodes1,0);// 出度for(inti1;iL;i){string op;cinop;if(opA){intnxti1;adj[i].push_back(nxt);pred[nxt].push_back(i);outDeg[i]1;}elseif(opJ){intN;cinN;adj[i].push_back(N);pred[N].push_back(i);outDeg[i]1;}else{// CintN;cinN;intnxt1N;intnxt2i1;adj[i].push_back(nxt1);pred[nxt1].push_back(i);adj[i].push_back(nxt2);pred[nxt2].push_back(i);outDeg[i]2;}}// 计算所有“必然终止”的节点goodvectorboolgood(totalNodes1,false);vectorintcntoutDeg;// 剩余未确定为 good 的后继数量queueintq;good[L1]true;q.push(L1);while(!q.empty()){intvq.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])coutALWAYS\n;else{// 检查是否存在路径到达 L1可达性vectorboolvisited(totalNodes1,false);stackintst;st.push(1);visited[1]true;boolreachablefalse;while(!st.empty()){intust.top();st.pop();if(uL1){reachabletrue;break;}for(intnxt:adj[u]){if(!visited[nxt]){visited[nxt]true;st.push(nxt);}}}if(!reachable)coutNEVER\n;elsecoutSOMETIMES\n;}}return0;}总结本题的关键是将程序执行抽象为有向图上的路径问题。“必然终止”的性质可以通过反向拓扑递推求解相当于计算所有路径均满足某个条件的节点集。结合可达性检查即可完整分类三种终止行为。该解法充分利用了有向图的拓扑特性时间复杂度为线性对于L≤1000L \le 1000L≤1000足够高效。类似地此类非确定性系统分析常用于程序验证、模型检测等领域核心是可达性分析和全路径性质推理。